Geek Answers Handbook

Java BigInteger Primes

I am trying to create a random prime number of type BigInteger, that is, between the minimum and maximum value that I will set.

I know about BigInteger.probablePrime (int bitlength, random), but I'm not sure how or even if the length of the bit goes into the maximum / maximum value of the displayed prime number.

Thanks Steven1350

+7
java biginteger primes
source share
2 answers

BigInteger.probablePrime(bitLength, random) will return the (probable) amount of the given bit length. This translates to a maximum value of 2 ^ bit-length - 1 and a minimum of 2 ^ (bit-1 length). As much as I hate this as an answer, this is probably your best bet if you don't want to start thinking about number theory.

What you need to do is figure out the length of the bits your range requires and then pass them to probablePrime() until you return a stroke that is in the correct range.

+2
source share

The answer to jprete is excellent if your max / min ratio is not close to 1.

If you have a limited range, it is best 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 prime density is pretty high overall, it's basically 1 in log (x), so you don't have to repeat too many times to find a prime. (As an example: for numbers around 10 23, each of 52 integers on average is a prime number. The above code only bothers 2 out of every 6 numbers, so you end up looping an average of 17 times for numbers around 10 23. )

Just make sure you have a good conformance test, and Java BigInteger is one.

As an exercise for the reader, extend the function above to filter out more complex numbers in advance using 30k + x (modulo 30, there are 22 modules that are always composite, only 8 remaining, which can be simple), or 210k + x.

edit: see also US Patent No. 7149763 (OMFG !!!)

+3
source share

More articles:


All Articles