Probable-primes: How Probable? 
(Another of the Prime Pages' resources)
 GIMPS found two new primes: 243112609-1 (about 12.9 million digits, Aug 08) and 237156667-1 (only 11.1 million digits, Sept 08).


Home
Search Site

Largest
The 5000
Top 20
Finding
How Many?
Mersenne

Glossary
Prime Curios!
Prime Lists

FAQ
e-mail list
Titans

Prime Links
Submit primes

An integer n>1 for which an-1 = 1 (mod n) is called a probable-prime base a (an a-PRP).  By Fermat's Little Theorem all primes are PRP for every base 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:

  1. n is chosen at random with 1 < n <= x
  2. a is chosen at random with 1 < a < n-1, and
  3. an-1 = 1 (mod n) (that is, n is a PRP base a).
Here is part of what they found [KP89 table 1, p723]:

Table 1. Probability that a random PRP is composite
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

41-kP(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].

The Prime Pages
Another prime page by Chris K. Caldwell <caldwell@utm.edu>