How probable is a probable prime?

A probable prime is a number that passes a test that all primes pass and that most composite numbers fail. Specifically, a Fermat probable prime is a number that passes Fermat's primality test. Fermat's test is the most commonly used, so that's nearly always what anyone means by probable prime unless they're more specific.

A number n is a Fermat probable prime for base b if

b^n-1 = 1 (mod n).

This test isn't conclusive, but it can be implemented efficiently and it weeds out most composite numbers. To read more on probable primes, see this post.

If a number is a probable prime, how probable is it that it really is prime? This post will briefly summarize some results from a paper [1] that makes this precise. From that paper:

... let P(x) denote the probability that an integer n is composite given that

1. 1. n is chosen at random with 1 < n x, n odd,
   2. b is chosen at random with 1 < b < n - 1, and
   3. n is a probable prime to the base b.

The authors give upper bounds on P(x) for x equal to various powers of 2. In particular they report

P(2²⁵⁰) 5.876 * 10^-6

and

P(2²⁶⁰) 3.412 * 10^-6

and so a the chances that a 256-bit probable prime is composite are in the neighborhood of 4 in a million. In practice, one would test with multiple bs. The tests for various bs aren't entirely independent, but running the tests for multiple bases does mean that fewer composite numbers slip through. There are a few pesky numbers, the Carmichael numbers, that are Fermat probable primes for nearly all bases (see footnote [2] here for more details), but these are rare.

I looked through the paper for results for larger powers of 2 to get results that would be applicable to, for example, RSA keys. The largest result explicit in the paper is

P(2³³⁰) 8.713 * 10^-8

though I would like to know P(2¹⁰²⁴) and P(2¹⁵³⁶) since RSA keys are the products of (probable) primes this large. Presumably the results in [1] could be used to compute P(x) for larger values of x, but I haven't read the paper closely enough to how much personal effort or computational effort that would require. I imagine it would be difficult or else the authors would have reported results for probable primes of the size frequently used in applications.

• Various kinds of pseudoprimes
• RSA with pseudoprimes
• Recommended cryptographic key sizes

[1] Jared Ducker Lichtman and Carl Pomerance. Improved error bounds for the Fermat primality test on random inputs. Mathematics of Computation. Volume 87, Number 314, November 2018, pages 2871-2890.