CODEWITHSUNDEEP
javabiginteger
User_67128
User_67128

Reputation: 1250

How Java BigInteger nextProbablePrime method works?

I'm working with Java BigInteger Class and curious about the Algorithm behind nextProbablePrime method. I know about some efficient primality testing algorithm like Miller-Rabin but not sure about which algorithm was implemented here.

Trying the following code for a good time and still no response.

BigInteger number = BigInteger.ZERO;
number = number.setBit(82589933);
number = number.nextProbablePrime();

Upvotes: 3

Views: 739

Answers (2)

not-just-yeti
not-just-yeti

Reputation: 17923

Why your example runs and runs without returning:

Your number is 82million bits long, and (by prime number th'm) such primes are ab out 82million / log_e(2) numbers apart. So you're asking Miller-Rabin to test about 15million-ish candidates, where each candidate involves 82million bits, and each check is non-trivial. So yeah, even efficient algorithms like Miller-Rabin will take a while on such beyond-mind-bogglingly-big inputs.

(I remember once running raising one number to another, having it take too long, and complaining to the language-developer that they should use repeated squaring for faster exponentiation ... before I stepped back and realized that my test-number also had millions of digits.)

Upvotes: 1

Chandra Shekhar Paatni
Chandra Shekhar Paatni

Reputation: 91

I have gone through with the source code of BigInteger. It is internally using the MillerRabin algorithm for the nextProbablePrime method.

Upvotes: 4

Related Questions