Why Pseudoprime Tests Work So Well

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 10¹⁵, 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/.