10182

# Why Pseudoprime Tests Work So Well

If is prime and has no factor in common with , then . But if is composite, this congruence is false for most values of . This leads to tests that distinguish prime numbers from composites.

### DETAILS

Snapshot 1: for each , the graph and tooltip show the number of bases such that is a pseudoprime base
Snapshot 2: the number of such bases is usually small compared to ; an exception is
Snapshot 3: for each , the graph shows the smallest pseudoprime base (if any) that is greater than 1
If is prime and has no factor in common with , then Fermat's little theorem says that .
The converse is very often, but not always, true: given , you choose at random; if , then is very likely to be prime.
The congruence condition is called a pseudoprime test. If is composite and , then is called a pseudoprime to base . The only pseudoprimes base 2 that are less than 1000 are 341, 561, and 645: these are the only composite numbers less than 1000 for which . In other words, if you designed a primality test that said, "if then is prime", then for , your test would fail only for ,, and . Your test would falsely claim that these three numbers are prime.
Although there are three pseudoprimes base 2 less than 1000, pseudoprimes become quite rare. For example, up to 1015, there are only 1,801,533 pseudoprimes base 2 (see [4]), which is about two pseudoprimes per billion integers. So, if is a large number such that , then has a very high probability of being prime.
Pseudoprime tests work so well because if is composite, there are relatively few values of for which . So, if is composite and you pick base at random (or always use ), that value of is unlikely to be a pseudoprime base for because is usually some value other than .
For example, the graph shows that for , there are just four values of between 1 and 339 such that .
By contrast, the graph shows that for , there are 100 pseudoprime bases between and . This is nearly 30% of all possible values of in this range.
Some bases are "trivial", that is, useless for primality testing. If is odd, then and always satisfy , so every odd always has these two trivial pseudoprime bases. (Also, if is a power of 3, then and are the only such bases; see corollary 1 of theorem 1 in [1].) If is even, then is a trivial pseudoprime base for . So, there are only two nontrivial pseudoprime bases for , and 98 nontrivial bases for .
The graph also displays, for each , the smallest pseudoprime base (if any) that is greater than 1. For , there are just four pseudoprime bases. There are the two trivial bases, and . The smallest nontrivial base is . The other nontrivial base is . For , the smallest nontrivial pseudoprime base is .
Here is an algorithm to count the number of pseudoprime bases between 1 and for any given . First, factor into primes. Then, for each distinct prime that divides , compute . Finally, multiply these gcd values together. This gives the number of pseudoprime bases for . For example, suppose . The number of pseudoprime bases for 341 is . This algorithm comes from theorem 1 of [1] and from [2].
As noted above, the primality test fails occasionally, as with . This test can be made more powerful (i.e. less likely to fail) by combining it with other tests. For example, by Fermat's little theorem, if is any prime other than 2 or 17, then both congruences and are true. But the smallest composite number for which both congruences are true is . So, for every , if both of these congruences are true, then is prime; if at least one of them fails (and is neither 2 nor 17), then is composite. In other words, checking both of these congruences gives a primality test that works until . This extension, and other much more powerful ones, are discussed in [1], [2], [3], and [5].
The exponentiation can be done quickly. For example, can be computed in only four steps: , , , and . In Mathematica, is efficiently computed with PowerMod[b, n-1, n].
Note: Prime values of are excluded from the graphs. This is because, if is prime, the number of pseudoprime bases is ; and this would make the scale on the vertical axis so large that it would be difficult to read the values for composite .
References
[1] R. Baillie and S. S. Wagstaff, Jr., "Lucas Pseudoprimes," Mathematics of Computation, 35(152), 1980 pp. 1391–1417. http://mpqs.free.fr/LucasPseudoprimes.pdf.
[2] L. Monier, "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms," Theoretical Computer Science, 12(1), 1980 pp. 97–108.
[3] C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., "The Pseudoprimes to 25 · ," Mathematics of Computation, 35(151), 1980 pp. 1003–1026. http://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.
[4] The On-Line Encyclopedia of Integer Sequences, Sequence A055550. http://oeis.org/A055550.
[5] Z. Zhang and M. Tang, "Finding Strong Pseudoprimes to Several Bases II," Mathematics of Computation, 72(144), 2003 pp. 2085–2097. http://www.ams.org/journals/mcom/2003-72-244/S0025-5718-03-01545-X/.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.