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.