Why does PGP still use the Fermat primality test? What if it hits one of the Carmichael numbers？

Question

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?

Answer 1

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

• sci.crypt: 1994 - Why Fermat test for PGP primes

• Critique of PGP Key Generation

• and PGP Attack FAQ: The asymmetric cipher

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.

• 1993, Atkin and Morain, Elliptic Curve and Primality Proving which can also provide a primality certificate for rapid verification which is not possible with AKS in which the number itself considered as the self-certificate for its primality.
• 1983,1984, Adleman–Pomerance–Rumely primality test

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.