BigInteger.isProbablePrime

Question

I just want to confirm my intuition about this method. Consider the code below.

long knownPrime = // some large known prime
int certainty = // some integer greater than 0

BigInteger b = BigInteger.valueOf(knownPrime);
boolean isPrime = b.isProbablePrime(certainty);

For a large known prime, and for any certainty > 0, is it accurate to say that b.isProbablePrime(certainty) will always return true?

Or are there any cases where the method "guesses" that a known prime number is composite?

Answer 1

For a large known prime, and for any certainty > 0, is it accurate to say that b.isProbablePrime(certainty) will always return true?

Yes. The documentation says it will return false only if it is certain that the number is composite.

Returns: true if this BigInteger is probably prime, false if it's definitely composite.

So the certainty parameter will influence only on the chance of a false-positive: saying a composite number is prime, when it really is not.

Answer 2

For a large known prime b, and for any certainty, b.isProbablePrime(certainty) returns true.

isProbablePrime can only err by returning true when the input is not prime (an example is b=6, certainty=0, which returns true), never the other way (because the Rabin-Miller test, which isProbablePrime uses, can only fail in this direction).