probable prime
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. <caldwell@utm.edu>

Fermat's little theorem gives us a powerful test for compositeness: Given n (greater than one), choose a positive integer a and calculate an-1 modulo n. (There is a very easy way to evaluate this quickly by binary exponentiation.) If the result is not one modulo n, then n is composite. If it is one modulo n, then n might be prime, so n is called a (weak) probable prime base a (or just an a-PRP). (There are many other definitions for probable primes relying on other properties of primes.)

Some of these probable primes are actually composites, we call these numbers pseudoprimes. There are only 1,091,987,405 base two probable primes less than 25,000,000,000; but only 21,853 of these are pseudoprimes, so the probable prime test base two would fail only 0.0000874% of the time in this region. Henri Cohen once joked that 2-PRP's are "industrial grade primes" because they are prime often enough for many purposes.

But still, there are infinitely many composite probable primes for every base.

Below are the odd composite probable primes (pseudoprimes) less than 500 for bases 2, 3, ..., 20.

basecomposite weak-probable primes < 500percentage
2341 0.6%
391, 121 1.2%
415, 85, 91, 341, 435, 451 3.8%
5217 0.6%
635, 185, 217, 301, 481 3.2%
725, 325 1.2%
89, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481 8.3%
991, 121, 205 1.9%
109, 33, 91, 99, 259, 451, 4814.4 %
1115, 133, 259, 305, 4813.2%
1265, 91, 133, 143, 145, 247, 377, 3855.1%
1321, 85, 105, 231, 357, 4273.8%
1415, 39, 65, 195, 4813.2%
15341 0.6%
1615, 51, 85, 91, 255, 341, 435, 4515.1%
179, 45, 91, 145, 261 3.2%
1825, 49, 65, 85, 133, 221, 323, 325, 343, 425, 4517.0%
199, 15, 45, 49, 153, 169, 3434.4%
2021, 57, 133, 231, 3993.2%

Note: some early articles used the name "pseudoprimes" for what we are calling probable primes. But now the term pseudoprime is usually (but not always) properly reserved for composite probable-primes.

See Also: StrongPRP, CarmichaelNumber, Pseudoprime, FrobeniusPseudoprime

Related pages (outside of this work)

References:

PSW80
C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 109," Math. Comp., 35:151 (1980) 1003-1026.  MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].]
Ribenboim95
P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995.  pp. xxiv+541, ISBN 0-387-94457-5. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventy-five pages.]



Chris K. Caldwell © 1999-2014 (all rights reserved)