What is a possible use case of BigInteger's .isProbablePrime()?

Question

The method BigInteger.isProbablePrime() is quite strange; from the documentation, this will tell whether a number is prime with a probability of 1 - 1 / 2^arg, where arg is the integer argument.

It has been present in the JDK for quite a long time, so it means it must have uses. My limited knowledge in computer science and algorithms (and maths) tells me that it does not really make sense to know whether a number is "probably" a prime but not exactly a prime.

So, what is a possible scenario where one would want to use this method? Cryptography?

Answer 1

Yes, this method can be used in cryptography. RSA encryption involves the finding of huge prime numbers, sometimes on the order of 1024 bits (about 300 digits). The security of RSA depends on the fact that factoring a number that consists of 2 of these prime numbers multiplied together is extremely difficult and time consuming. But for it to work, they must be prime.

It turns out that proving these numbers prime is difficult too. But the Miller-Rabin primality test, one of the primality tests uses by isProbablePrime, either detects that a number is composite or gives no conclusion. Running this test n times allows you to conclude that there is a 1 in 2ⁿ odds that this number is really composite. Running it 100 times yields the acceptable risk of 1 in 2¹⁰⁰ that this number is composite.

Answer 2

If the test tells you an integer is not prime, you can certainly believe that 100%.

It is only the other side of the question, if the test tells you an integer is "a probable prime", that you may entertain doubt. Repeating the test with varying "bases" allows the probability of falsely succeeding at "imitating" a prime (being a strong pseudo-prime with respect to multiple bases) to be made as small as desired.

The usefulness of the test lies in its speed and simplicity. One would not necessarily be satisfied with the status of "probable prime" as a final answer, but one would definitely avoid wasting time on almost all composite numbers by using this routine before bringing in the big guns of primality testing.

The comparison to the difficulty of factoring integers is something of a red herring. It is known that the primality of an integer can be determined in polynomial time, and indeed there is a proof that an extension of Miller-Rabin test to sufficiently many bases is definitive (in detecting primes, as opposed to probable primes), but this assumes the Generalized Riemann Hypothesis, so it is not quite so certain as the (more expensive) AKS primality test.