Algorithm used by BigInteger prime generator?

[Andrew Haley]

> From: Alexandre Oliva <oliva at dcc.unicamp.br>
> Date: 22 Apr 1999 11:55:44 -0300
> 
> On Apr 22, 1999, Andrew Haley <aph at pasanda.cygnus.co.uk> wrote:
> 
> > The technique of simply adding 2 until a prime is reached is pretty
> > much standard in crypto, and with crypto-sized BigIntegers the
> > deviation from a uniform distribution is insignificantly small.
> 
> But we're not talking about crypto-sized BigIntegers, we're talking
> about the BigInteger class.  It's supposed to be general-purpose, not
> exclusive for use for cryptography.

I think that's the heart of this disagreement.  I think that
BigInteger is a crypto library in disguise, intended so that Java may
be used for Internet commerce.  I think that's why the exact method
for generating random primes isn't exactly specified, so that
implementors may do the most efficient thing.  I accept that's not
what the standard actually says.  ;-)

> assuming that isProbablePrime takes constant time for a constant
> bitLength.

Mm.  It would be a very bad implementation of isProbablePrime that
took constant time for a constant bitLength.

Andrew.