Prime Generation

Peter Gutmann pgut001 at
Tue Nov 16 08:58:38 CET 1999

Pete Chown <Pete.Chown at> writes:

>My question is, doesn't this use up more random data than is necessary?  
>Suppose instead of step 5, you just tested the next odd number for 
>primality rather than starting again.
>Of course this would bias the algorithm towards primes which are preceded 
>by a lot of composite numbers.  I don't know how significant the bias would 
>be, since we know that prime numbers are fairly evenly spread.

This has been discussed to death (or at least near-death... maybe beaten to
death is a better term :-) in sci.crypt at various times, for example check
the thread "PGP probability of choosing primes" from earlier this year.  It
seems to be a matter of personal preference, SSLeay and GPG use a new random
number, I use the current one + delta in order to avoid draining entropy but
there's no overwhelming reason to favour one over the other.


More information about the Gnupg-devel mailing list