发表于 2022-9-19 16:33:12
Why does PGP still use the Fermat primality test? What if it hits one of the Carmichael numbers？|
https://crypto.stackexchange.com ... hits-one-of-the-car
The quote from the last;
The Carmichael Numbers
Unfortunately, there are some numbers which are not prime and which do satisfy the equation bn−1modn
. 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 109. The chance of PGP generating a Carmichael Number is less than 1 in 1050
So, even there are other alternatives to Fermat Test, they still use it.