Algorithm used by BigInteger prime generator?

[Andrew Haley]

> From: Alexandre Oliva <oliva at dcc.unicamp.br>
> Date: 22 Apr 1999 06:36:42 -0300
>
> Alexandre Oliva <oliva at dcc.unicamp.br> writes:
>> Does anybody know what algorithm the constructor
>> java.math.BigInteger.BigInteger(int bitLength, int certainty, Random
>> rnd) is supposed to use?
> 
> The problem is that there's no specification about what to do after
> generating a random number, nor does it talk about ``adjusting'' a
> randomly-generated number so that it passes a primality test.

The specification seems to me to be adequate: generate a random prime
_bitLength_ bits long which passes a Fermat test or somesuch
_certainty_ times.  In cryptographic usage, the most significant bit
of an n-bit number is always assumed to be set: that's what defines it
to be an n-bit number.

As far as I can see, what is intended is something like this:

  static BigInteger newPrime (int bitLength, int certainty, Random rnd) 
  {	
    BigInteger candidate = new BigInteger (bitLength, rnd);
    candidate = candidate.setBit (bitLength-1).setBit (0);

    for (;;)
      {
	boolean prime = true;

	if (candidate.isProbablePrime (certainty))
	  return candidate;
	else
	  candidate = candidate.add (BigInteger.valueOf (2));
      }
  }

I haven't tested this, and a real version should check for overflows,
but I don't think that much more is needed.

Andrew.