17 Dec
2003
17 Dec
'03
11:17 p.m.
What estimates exist for the density of large Carmichael numbers, say 1000 bits long? I.e., what's the probability of running into one by accident when generating primes by the usual technique of picking a random starting point and searching up until you find a number that passes seive or small factor tests and a few iterations of Fermat's test? Are other probability tests like Miller-Rabin any more provably likely to detect these? I'm currently playing with the Miller-Rabin test. Boy, is modular exponentiation a pig (at least the routine in RSAREF). Phil