Algorithm used by BigInteger prime generator?

[Alexandre Oliva]

On Apr 22, 1999, Andrew Haley <aph at pasanda.cygnus.co.uk> wrote:

> As far as I can see, what is intended is something like this:

> 	if (candidate.isProbablePrime (certainty))
> 	  return candidate;
> 	else
> 	  candidate = candidate.add (BigInteger.valueOf (2));

Except that this may generate a prime with more than bitLength bits,
depending on the initial random number and on the number of failures
you get, so you may have to retry if it overflows.  Furthermore, it
doesn't generate randomly distributed primes, and I'm not sure this
meets the requirement of O(certainty).  Anyway, I've just committed a
version that does it.  But it could be made much more efficient by
using a sieve, since isProbablePrime is quite expensive.

Nevertheless, the specification leaves room for a lot of different
implementations, particularly in the use of rnd, which is unacceptable 
for WORA.  Theoretically, given the same implementation of Random,
with the same seed, one should get the same sequence of random primes, 
regardless of the JVM used.

Also note that your implementation will never generate 2 for
bitLength==2.

-- 
Alexandre Oliva http://www.dcc.unicamp.br/~oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}@dcc.unicamp.br  aoliva@{acm.org,computer.org}
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
*** E-mail about software projects will be forwarded to mailing lists