Clarification of the certainty factor in isProbablePrime

Question

My question concerns the the "certainty" factor for the isProbablePrime() method for the BigInteger. The Java API states that this is:

"a measure of the uncertainty that the caller is willing to tolerate"

Is this a percentage of uncertainty or some other factor. I need 2 prime number of 512 bit.

Answer 1

From the Javadocs for BigInteger's isProbablePrime method:

certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2^certainty)

So, the higher the certainty number you pass, the more certain you can be, i.e. 100 means it's prime with probability 1 - (1/2)¹⁰⁰, which is extremely close to 1.

Java accomplishes this by performing Miller-Rabin primality tests, the number of which is based on certainty (and a Lucas-Lehmer test).