Hello,
First, I want to thank the creators of the classpath project for the wonderful
work.
I stumbled over the following code block in the class java.math.BigInteger and
it is not clear to me how it works:
public BigInteger(int bitLength, int certainty, Random rnd)
237: {
238: this(bitLength, rnd);
239:
240: // Keep going until we find a probable prime.
241: BigInteger result;
242: while (true)
243: {
244: // ...but first ensure that BI has bitLength bits
245: result = setBit(bitLength - 1);
246: this.ival = result.ival;
247: this.words = result.words;
248: if (isProbablePrime(certainty))
249: return;
250:
251: init(bitLength, rnd);
252: }
253: }
I suppose the contract says that the returned number is prime with given
probability 1 - 1/2^certainty, but if the routine isProbablePrime(certainty)
does only test with the given certainty this might not work. The reason is
that the failure probability is not independent from the number of previous
trials. If we ignore the prime number theorem for a while and assume that
primes are very rare, lets say there density is much lower than 1/2^certainty,
then the loop is likely to run until the test returns a wrong result and we
almost never generate a prime number!
Of course the prime number theorem tells us that the above algorithm will
work somehow, but unless further comments can clarify what the routine
actually does, I suggest to increase the certainty by one before entering
the loop (see Gathen/Gerhard "Modern Computer Algebra").
Cheers,
Oliver
