Algorithm used by BigInteger prime generator?
aph at pasanda.cygnus.co.uk
Thu Apr 22 08:12:43 PDT 1999
> 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
Mm. It would be a very bad implementation of isProbablePrime that
took constant time for a constant bitLength.
More information about the kaffe