> From: Alexandre Oliva <[EMAIL PROTECTED]>
> Date: 22 Apr 1999 06:36:42 -0300
>
> Alexandre Oliva <[EMAIL PROTECTED]> 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.
