From: danisch@ira.uka.de (Hadmut Danisch)
Rabin-Miller would be better. It would be instructive to examine the conditional probability that a composite number which fails Rabin-Miller passes Fermat. I understand it's vanishingly small.
What is "vanishingly small" ? Small enough to ignore for the practice of "pretty good" security. There are algorithms to prove primality. See Cohen's excellent _A Course in Computational Algebraic Number Theory_, from Springer. Does anyone know how many Carmichael-Numbers exist? An infinite number. This was just proven in the last two years. The density of Carmichael numbers is very small. As I recall, this paper also included Pomerance, but I don't remember if he did the bulk of the work or not. If you found a Carmichael-Number consisting of primes bigger than the primes in your small-numbers-sieve, the Fermat-test won't detect it as a non-prime. Miller-Rabin will, however. Since most of the time generating a modulus has to do with testing composites, the added time for a few more modexp's to do M-R is small. The large effort is that of the authors of the crypto package to implement and debug it. Eric