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 [EMAIL PROTECTED]