Algorithm used by BigInteger prime generator?

[Andrew Haley]

> From: Alexandre Oliva <oliva at dcc.unicamp.br>
> Date: 22 Apr 1999 11:09:10 -0300
> 
> On Apr 22, 1999, Andrew Haley <aph at pasanda.cygnus.co.uk> 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,

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

> Furthermore, it doesn't generate randomly distributed primes

The specification doesn't require it to.

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.

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.

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

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

Andrew.