Re: Idle curiosity re RSA key generation

[Mouse <mouse%Rodents-Montreal.ORG@localhost>]

> [When generating RSA keys,] I typically see from dozens to hundreds
> of candidates pass the wheel but then fail the Little Theorem.  But
> don't think I have _ever_ seen a candidate pass the Little Theorem
> and then fail Miller-Rabin.  This leads me to wonder why this is.

I've been corresponding off-list with someone about this, and there are
plausible, albeit heuristic, reasons to think the density of base-2
Fermat pseudoprimes (composite numbers that pass the Fermat test in
question) is close to one in 2^600, whereas the density of primes is
more like one in 700.  (All figures are when generating 1024-bit
primes, as for a 2048-bit RSA key.)  So passing the Fermat test is
overwhelmingly likely to indicate a true prime (at least, in a
non-adversarial situation, which my scenario is; an adversarial
situation, of course, is quite another story.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		mouse%rodents-montreal.org@localhost
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B