There was a paper in the last seven or eight years on this. I believe Pomerance was one of the authors. Ask on sci.crypt for details.

Meanwhile I found the Rivest-Article "Finding Four Million Large Random Primes". It is in Proceedings of Crypto 90, not 91. It references some papers of Pomerance.

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" ? The chance to break a 1024-bit-key is also vanishingly small. And the keylength is increased to 2048 bit. Does anyone know how many Carmichael-Numbers exist? A Carmichael-Number m is a number where foreach a : gcd(a,m)=1 => a^(m-1) = 1 mod m e.g. 561 = 3*11*17 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. Since Carmichael-Numbers have at least three prime factors, a 2048-bit n would consist of one ~1024-prime and at least three other primes. At least one of them would be smaller than ~340 bit, probably significant smaller. Hadmut