4
$\begingroup$

Since the Fermat primality test is not very reliable, most applications use it for pretesting only. Wikipedia says that PGP still uses it:

Another well known program that relies only on the Fermat test is PGP where it is only used for testing of self-generated large random values (an open source counterpart, GNU Privacy Guard, uses a Fermat pretest followed by Miller–Rabin tests).

I do not understand why PGP still uses it without being followed by the Miller–Rabin test. What if it hits Carmichael numbers?

$\endgroup$
3
  • 4
    $\begingroup$ The Wikipedia article does not state "PGP still uses the Fermat primallity test". The article employs the present tense, but that refers to an old program. PGP is no longer an actively maintained open-source program. GPG is. In gnupg-1.4.23, there is a Fermat test (to base 2) with the comment do a faster Fermat test, but when that test passes it's further performed a Miller-Rabin test. That logic also applies in libgcrypt-1.9.2 possibly used by some version of GPG 2. $\endgroup$ – fgrieu Feb 18 at 9:51
  • $\begingroup$ @fgrieu Doesn't the Miller-Rabin test contain the Fermat test? $\endgroup$ – forest Feb 21 at 22:07
  • 1
    $\begingroup$ @forest: The Miller-Rabin test performs multiple strong pseudoprimes tests to random bases. The strong pseudoprime test to a particular base improves on the Fermat test to that base. Thus it's correct ot state GPG performs a Fermat test (to fixed base 2), then a Miller-Rabin test (multiple stronger tests to random, much likely different bases). $\endgroup$ – fgrieu Feb 21 at 22:32
3
$\begingroup$

It is a choice of the designers of PGP to stick to Fermat test. There are some nice talk since 1994

The quote from the last;

The Carmichael Numbers

Unfortunately, there are some numbers which are not prime and which do satisfy the equation $b^{n-1} \bmod n$. These integers are known as the Carmichael Numbers, and they are quite rare. The reason for this is that a Carmichael Number must not be divisable by the square of any prime and must be the product of at least three primes). The first three Carmichael Numbers are: 561, 1105, and 1729. They are so rare, in fact, there are only 255 of them less than $10^9$. The chance of PGP generating a Carmichael Number is less than 1 in $10^{50}$.

So, even there are other alternatives to Fermat Test, they still use it.

Here the oeis/A002997 for the Carmichael numbers;

  • 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461

If it hits a Carmichael number then it will factor into smaller primes like $512461 =31 \cdot 61 \cdot 271$. But it can still work as a normal RSA and fool us.

Once a fast probable prime obtained then one can use proof methods instead of AKS. We may consider this as modern sieving.

If you want to use the AKS then use the faster variant of AKS test. And note that AKS is a slow and deterministic primality-proving algorithm. Here a quote from DanaJ's great answer in Math.SE Fastest way to find if a given number is prime

Anyone who suggests actually using AKS in practice has never actually run it on numbers larger than 10,000 and should be ignored.

$\endgroup$
5
  • $\begingroup$ Thanks, this does answer my question. One doubt for the probability, you said "only 255 of them less than $10^9$", how come the chance is 1 in $10^{50}$ ? Shouldn't this be $255/10^9$? $\endgroup$ – Zixi Sean Feb 19 at 6:59
  • $\begingroup$ @ZixiSean the answer is not so easy, see from here $\endgroup$ – kelalaka Feb 19 at 11:52
  • 1
    $\begingroup$ You are spot on with the reasoning used. With some math libraries it is faster, while with others such as GMP there really is no performance reason to prefer Fermat vs. Miller-Rabin. AKS is an awful test to recommend, even the Bernstein improvements that are much faster than the old one you link to. Use ECPP or APR-CL for practical primality proving. AKS is far too slow. The others can do proofs for 2048-bit primes in reasonable times, and ECPP is vastly superior in that it gives a certificate. $\endgroup$ – DanaJ Feb 21 at 13:20
  • $\begingroup$ @DanaJ thanks and nice to hear from you. The link I've provided mentions, Bernstein, too. I've checked again and it is a weak mention, I've to provide a better ref. Except for AKS all probabilistic right? $\endgroup$ – kelalaka Feb 21 at 13:31
  • 1
    $\begingroup$ BLS75 (1975), APR-CL, and ECPP are proof methods, not probabilistic. BLS75 methods are based on factoring, so not practically useful for large inputs. In practice, just adding a strong Lucas test, as recommended by NIST as an option, greatly strengthens the probabilistic test for little code and performance cost. The Bernstein paper I was thinking of is cr.yp.to/papers/aks.pdf, which is the best result I'm aware of (theorem 4.1). The polynomial exponent will still be greater than APR-CL and ECPP for all practical inputs. $\endgroup$ – DanaJ Feb 21 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.