CODEWITHSUNDEEP
javarsabiginteger
Delete My Account
Delete My Account

Reputation: 785

Clarification of the certainty factor in isProbablePrime

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.

Upvotes: 16

Views: 9414

Answers (1)

rgettman
rgettman

Reputation: 178253

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

Upvotes: 24

Related Questions