Re: number theory

[Phil Karn <karn@qualcomm.com>]

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