Why Pseudoprime Tests Work So Well

Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
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.
Contributed by: Robert Baillie (May 2011)
Open content licensed under CC BY-NC-SA
Snapshots
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 , 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.
[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