Java BigInteger prime numbers

Question

I a m trying to generate a random prime number of type BigInteger, that is between an min and max value which I supply.

I am aware of the BigInteger.probablePrime(int bitlength, random), but I am not sure how or even if the bitlength translates into a max/min value of the outputted prime.

Thanks, Steven1350

Answer 1

BitInteger.probablePrime(bitLength, random) is going to return a (probable) prime of the specified bit length. That translates into a maximum value of 2^bitlength - 1 and a minimum of 2^(bitlength - 1). As much as I hate it as an answer, it's probably your best bet unless you want to start delving into number theory.

What you would have to do is figure out the bit lengths that your range calls for, then pass them to probablePrime() until you get back a prime that's in the right range.

Answer 2

jprete's answer is fine if your ratio max/min is not close to 1.

If you have a narrow range, your best bet is probably just to do something like the following:

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

The density of primes is fairly high overall, it's basically 1 in log(x), so you shouldn't have to repeat too many times to find a prime number. (just as an example: for numbers around 10²³, one in every 52 integers on average is a prime number. The above code only bothers with 2 out of every 6 numbers, so you'd end up looping an average of 17 times for numbers around 10²³.)

Just make sure you have a good primality test, and the Java BigInteger has one.

As an exercise for the reader, extend the above function so it filters out more composite numbers ahead of time by using 30k + x (modulo 30, there are 22 moduli that are always composite, only 8 remaining that could be prime), or 210k + x.

edit: see also US patent #7149763 (OMFG!!!)