Algorithm used by BigInteger prime generator?

[Alexandre Oliva]

On Apr 20, 1999, Paul Fisher <rao@gnu.org> wrote:

> Alexandre Oliva <oliva@dcc.unicamp.br> writes:
>> Does anybody know what algorithm the constructor
>> java.math.BigInteger.BigInteger(int bitLength, int certainty, Random
>> rnd) is supposed to use?

> Sun's java.math implementation uses Colin Plumb's <colin@nyx.net>
> BigNum library <URL: ftp://skip.incog.com/pub/bnlib-1.1.tar.gz >.
> You'll find the prime number generation routines there.

The problem is that there's no specification about what to do after
generating a random number, nor does it talk about ``adjusting'' a
randomly-generated number so that it passes a primality test.  For
example, Plumb's primeGen doesn't provide a mechanism to specify a
`certainty'.

Furthermore, Plumb's implementation accepts a rand function as an
argument, that takes only an unsigned integer as argument, to
randomize the increments to the base random number.  I don't see how
Sun might have written a wrapper function that would call back the
Random generator passed as argument, since it wouldn't be able to
figure out which Random object to invoke...  But then, this is not an
issue, since we wouldn't be using Plumb's implementation anyway.

I'm going to install a very dumb implementation, and improve it when I 
get input from Sun about the actual algorithm that should be used.

-- 
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