Fermat's primality test vs. Miller-Rabin

[Hal Finney]

Ron Rivest reported on some theoretical and practical experimental
work in Crypto 90, "Finding Four Million Large Random Primes",
http://theory.lcs.mit.edu/~rivest/Rivest-FindingFourMillionLargeRandomPrimes.ps

"A number n is a (base two) pseudoprime if it is composite and
satisfies the identity 2^(n-1) = 1 mod n....  How rare are pseudoprimes?
We performed an experiment that attempts to provide an answer...

They tested 718 million random 256-bit values.  First they performed a
small divisor test using divisors up to 10^4.  43,741,404 numbers passed.
These were then tested using the equation above (the Fermat test with
base 2).  4,058,000 passed that further test.  These were then subjected
to 8 iterations of Miller-Rabin to see which were pseudoprimes.

None of them were pseudoprimes.  All of the numbers in this sample which
passed the small divisor and base-2 Fermat test passed all subsequent
MR tests and were presumably all prime.

Rivest goes on and uses a conjecture of Pomerance to argue that the
number of pseudoprimes < 2^256 is at most 4 x 10^52, while the number
of true primes is 6.5 x 10^74.  Hence your chance of running into a
pseudoprime is less than 1 in 10^22.  I'm not sure the role of the
small-divisor tests but I think that may make the odds even better.
The larger primes in use today should also have improved odds.

Based on this kind of result, RSAREF, the free library available from
RSA back in the 90s, did not use MR and did not do multiple tests.
It performed a small divisor test (only testing 3, 5, 7 and 11 as
divisors!) and a single base 2 Fermat test, for its RSA keygen.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com