Algorithm used by BigInteger prime generator?

[Alexandre Oliva]

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

>> Except that this may generate a prime with more than bitLength bits,

> Did you not see my comment that "a real version should check for
> overflows"?

Yup, I should have ack'ed it.

>> Furthermore, it doesn't generate randomly distributed primes

> The specification doesn't require it to.

Indeed.  It doesn't really say much.

> 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.  If it were, it probably wouldn't
be exportable :-)

> If this is really unacceptable, a new random integer could be
> generated with each iteration, which answers such objections, but
> it's an extra run-time overhead.

But then it certainly won't meet the requirement about execution time
proportional to the value of certainty.

>> and I'm not sure this meets the requirement of O(certainty).

> I don't understand this.  Are you saying that isProbablePrime
> (certainty) does not meet the requirement of O(certainty)?

Nope, I'm just unsure whether testing primes sequentially does,
assuming that isProbablePrime takes constant time for a constant
bitLength.

>> Nevertheless, the specification leaves room for a lot of different
>> implementations, particularly in the use of rnd, which is unacceptable 
>> for WORA.

> I see your point.  However, the requirement that all implementations
> return the same result means that implementors are prevented from
> inventing a more efficient prime generator.  In real-world crypto
> applications, where random primes are frequently generated, this is
> very bad news.  In financial applications, it is not uncommon to use
> hardware accelerators to generate random primes: it would be
> impossible to use such hardware if the exact algorithm used to
> generate primes was fixed.

You're free to implement whatever algorithm you want for big prime
generation in your own classes, but
java.lang.BigInteger.BigInteger(int,int,Random) must be completely
specified in order to allow for WORA.  If this means using an
inefficient implementation, so be it.

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