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();
I have gone through with the source code of BigInteger. It is internally using the MillerRabin algorithm for the nextProbablePrime method.
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.)