Clarification of the certainty factor in isProbablePrime

biginteger, java, rsa

Solution

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/2certainty)

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)100, 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).

Problem

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.

Original source