> From: Alexandre Oliva <[EMAIL PROTECTED]>
> Date: 22 Apr 1999 11:09:10 -0300
>
> On Apr 22, 1999, Andrew Haley <[EMAIL PROTECTED]> 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.
