Oliver Glier wrote:
> 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").
Yes, I can see this makes sense. However, as you say, we know that primes
are not rare at all, and also that
"On average the probability that a composite number is declared probably prime
is significantly smaller than 4 ^ −k. Damgård, Landrock and Pomerance[4]
compute some explicit bounds. Such bounds can, for example, be used to
generate primes..."
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
See also
http://theory.lcs.mit.edu/~rivest/Rivest-FindingFourMillionLargeRandomPrimes.ps
Andrew.
