# What is the correct value for “certainty” in RSA key pair generation?

I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty. This Stack Overflow answer says it is a relative test for how prime the values are.

There is another answer that says this value should be adjusted relative to the key length.

Question

• What are the correct values for certainty relative to key length (how did you determine this?)

• What does it mean to say "certainty of x bits" of a number? (If it's possible to sub-divide a number and certify bits, which bits are being certified?)

-

Certainty of $x$ bits means that the probability that something (in this case $p$ being prime) not being true is smaller than $2^{-x}$. This is the same probability as guessing a random $x$-bit value correctly on the first try, hence the name.
How to select $x$? We want the probability of $p$ (and $q$) not being prime to be small enough that a failure probability in this point is not larger than other ways the system could be broken - like guessing a symmetric key, factoring the modulus etc.
Also, your algorithmic probability of failure is physically bounded by the failure probability of your hardware, so for instance, a $2^{-512}$ probability of failure is quite overkill. –  Thomas Jul 2 '12 at 0:36
As a confirmation, the certainty in the question is traceable to that in a paragraph just above this, reading: "$\mathtt{certainty }$ - a measure of the uncertainty that the caller is willing to tolerate. The probability that the new BigInteger represents a prime number will exceed $(1-1/{2^{\mathtt{certainty}}})$. The execution time of this constructor is proportional to the value of this parameter." –  fgrieu Jul 2 '12 at 7:37