Algorithm used by BigInteger prime generator?

Alexandre Oliva oliva at
Thu Apr 22 07:09:10 PDT 1999

On Apr 22, 1999, Andrew Haley <aph at> 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

Alexandre Oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}  aoliva@{,}
*** E-mail about software projects will be forwarded to mailing lists

More information about the kaffe mailing list