This is the mail archive of the java-discuss@sourceware.cygnus.com mailing list for the GCJ project. See the GCJ home page for more information.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
> From: Alexandre Oliva <oliva@dcc.unicamp.br> > Date: 22 Apr 1999 11:09:10 -0300 > > On Apr 22, 1999, Andrew Haley <aph@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.