# Probable-primes: How Probable?

An integer *n* > 1 for which *a*^{n-1} ≡ 1 (mod *n*) is called a **probable-prime base a** (an

**). By Fermat's Little Theorem all primes are PRP for every base**

*a*-PRP*a*not divisible by

*p*. For every base

*a*there are also infinitely many composites that are

*a*-PRP's (see our pages on primality proving). Nevertheless, PRP's are so often prime that Henri Cohen suggested they are "industrial grade primes" (not proven primes, but good enough for RSA encryption and similar tasks). What's good enough?

Su Hee Kim and Carl Pomerance [KP89] considered the probability
p(*x*) that a PRP less than *x* is composite. More specifically,
let *x* be a positive number and **define p( x) to be
the probability that an an odd number n is composite** given:

- the integer
*n*is chosen at random with 1 <*n*≤*x* - the integer
*a*is chosen at random with 1 <*a*<*n*-1, - and
*a*^{n-1}≡ 1 (mod*n*) (that is,*n*is a PRP base*a*).

Digits in x |
Upper bound for p(x) |
Digits in x |
Upper bound for p(x) |
Digits in x |
Upper bound for p(x) |
||
---|---|---|---|---|---|---|---|

60 | 0.0716 | 80 | 0.0000846 | 100 | 0.0000000277 | ||

120 | 5.28*10^{-12} |
150 | 1.49*10^{-17} |
200 | 3.85*10^{-27} |
||

300 | 5.8*10^{-29} |
400 | 5.7*10^{-42} |
500 | 2.3*10^{-55} |
||

700 | 1.8*10^{-82} |
1000 | 1.2*10^{-123} |
2000 | 8.6*10^{-262} |
||

5000 | 7.6*10^{-680} |
10000 | 1.6*10^{-1331} |
100000 | 1.3*10^{-10584} |

For example, if you pick a random 120 digit odd number *n*, pick
a smaller random base *a*, then if *n* is an *a*-PRP, the
probability that *n* is composite is less than 0.00000000000528!
If you use a strong PRP
test you can divide this bound at least in half. If you perform *k* strong PRP tests (with randomly chosen bases), then the probability
is at most

4^{1-k} p(*x*) / (1-p(*x*)).

For better estimates inthe strong PRP case see [Burthe1996] and [DLP1993].

Finally, it seems obvious that the probability bounds given in Table
1 are heading toward zero as *x* approaches infinity, this was first
shown by Paul Erdös and Carl Pomerance in 1986 [EP86].