Re: BigInteger Prime Generation

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.