A quarter of the bases at most

The numbers that fool every base counted the Carmichael numbers: composites $n$ for which $a^{n-1} \equiv 1 \pmod n$ holds for every base $a$ that shares no factor with $n$, exactly as it would if $n$ were prime. There are infinitely many, 20,138,200 of them below $10^{21}$, and each one is a permanent hole in Fermat’s test. That essay ended by naming the refinement that closes the hole — the strong test that Gary Miller and Michael Rabin made into the standard way of recognising primes — and the question it raises: how many bases can a composite fool then?

The answer is a theorem with a sharp number in it. Louis Monier and Rabin proved independently in 1980 that every odd composite other than 9 passes the strong test for at most a quarter of its bases. So no composite can hide behind every base, or even behind most; a base chosen at random exposes it with probability at least three in four, and forty independent bases leave a chance below $10^{-24}$ of being fooled. This essay counts the bases that lie, composite by composite, checks the quarter against every odd composite below 100,000, and finds the smallest composites that survive the first few prime bases.

What a prime allows the squarings to do #

Fermat’s test computes $a^{n-1} \bmod n$ and checks for 1. The strong test computes the same number by a particular route and checks the route. Write $n - 1 = 2^s d$ with $d$ odd; then $a^{n-1}$ is $a^d$ squared $s$ times, and the test looks at the whole chain

$$a^d,\ a^{2d},\ a^{4d},\ \ldots,\ a^{2^s d} = a^{n-1}.$$

If $n$ is prime the chain is constrained by one fact: the only numbers whose square is 1 modulo a prime are $1$ and $-1$, because $x^2 - 1 = (x - 1)(x + 1)$ and a prime that divides a product divides a factor — or, in the language of every element is a power of one of them, because the units modulo a prime form a cyclic group, and a cyclic group of even order has exactly one element of order two. So each time the chain reaches 1, the number before it was $1$ or $-1$. A prime therefore allows exactly two shapes: the chain starts at 1, or it reaches $-1$ at some point and is 1 from then on. A base for which the chain has one of these shapes passes; a composite that a base passes is a strong pseudoprime to that base, and the base is a strong liar.

For a composite the chain can reach 1 from a number that is neither $1$ nor $-1$, a nontrivial square root of 1, and that is a certificate of compositeness — it even yields a factor, since $\gcd(x - 1, n)$ is then a proper divisor. Composites have plenty of such square roots. Two dials at once showed that arithmetic modulo $n = pq$ is arithmetic modulo $p$ and modulo $q$ run side by side, and a number that is $1$ on one dial and $-1$ on the other squares to 1 on both: for $n$ with $k$ distinct odd prime factors there are $2^k$ square roots of 1, and all but two are nontrivial.

The hero shows what this does to 561. Here $561 - 1 = 2^4 \cdot 35$. Every base coprime to 561 has $a^{560} \equiv 1$, so Fermat’s test passes all 320 of them, which is what makes 561 a Carmichael number. But for 310 of those bases the chain reaches 1 through a nontrivial square root, and only 10 — including the trivial 1 and 560 — follow one of the two patterns a prime would allow. The strong test catches 561 with 310 bases out of 320, 97% of the time.

Never more than a quarter #

Monier went further than the bound and counted the liars exactly. If $n$ has $k$ distinct prime factors $p_1, \ldots, p_k$, if $n - 1 = 2^s d$ with $d$ odd, and if $\nu$ is the smallest power of 2 dividing any of the $p_i - 1$, then the number of strong liars is

$$\left(1 + \frac{2^{k\nu} - 1}{2^k - 1}\right)\prod_{i=1}^{k} \gcd(d,\ p_i - 1).$$

The formula comes straight from the two-dials picture: a base is a liar when its chain on every dial reaches $-1$ at the same step, or starts at 1 on every dial, and counting how many bases do that on each dial and requiring agreement gives the product. The figure checks the formula against a base-by-base count for every odd composite below 3,000, where both can be computed, and they agree in every case; it then uses the formula for every one of the 40,408 odd composites below 100,000.

The shares lie under a quarter, and the plot shows the structure under the bound. The dots form falling bands, one for each value of the product of gcds, which makes the share fall like one over $n$ for numbers with the same gcd pattern. The composites that reach the bound exactly are a thin family at the top, nine of them below 100,000: $15 = 3 \cdot 5$, $91 = 7 \cdot 13$, $703 = 19 \cdot 37$ and $1{,}891 = 31 \cdot 61$, products of a prime $p$ and $2p - 1$ with $p$ leaving 3 on division by 4, and then $8{,}911 = 7 \cdot 19 \cdot 67$, a Carmichael number whose three prime factors all leave 3 on division by 4. For them exactly a quarter of the bases lie, and the bound cannot be improved. The one exception is 9, where 1 and 8 are two liars among the six bases coprime to it — a third — because a prime power has only the trivial square roots of 1 and the argument for the quarter needs at least one nontrivial one.

Most composites have almost no liars #

The quarter is a worst case, and it is rarely approached. Every odd composite has at least two strong liars, 1 and $n - 1$, which pass the test for every $n$ whatever its factors. Of the 40,408 odd composites below 100,000, 25,954 — 64.2% — have no others: every base from 2 to $n - 2$ exposes them. Another 6,268 have between three and ten liars, and only 181 have more than a thousand. In all, 98.0% have fewer than one liar per hundred bases.

That is why the test is so effective in practice, well beyond what the bound says. Ivan Damgård, Peter Landrock and Carl Pomerance showed in 1993 that for a randomly chosen large odd number, the chance that it is composite and passes even a single strong test is far smaller than a quarter — for numbers of a few hundred digits, smaller by many powers of ten — because random composites are overwhelmingly of the kind with almost no liars. The quarter is what an adversary who chooses the number can achieve; nature, choosing at random, does far worse.

The first composites to pass the first bases #

The test can also be made deterministic, by fixing the bases in advance and knowing how far they suffice. The smallest odd composite that passes the strong test to base 2 is $2{,}047 = 23 \cdot 89$ — a number, incidentally, that is $2^{11} - 1$, the first Mersenne number with a prime exponent that is not itself prime. The figure finds it, and continues the search through every odd number: the smallest composite passing both 2 and 3 is $1{,}373{,}653 = 829 \cdot 1657$, and the smallest passing 2, 3 and 5 is $25{,}326{,}001 = 2251 \cdot 11251$. The fourth, the smallest passing 2, 3, 5 and 7, is $3{,}215{,}031{,}751 = 151 \cdot 751 \cdot 28{,}351$, found by Carl Pomerance, John Selfridge and Samuel Wagstaff in 1980; the figure does not search that far but checks that it passes those four bases and fails 11.

So a number below 3,215,031,751 that passes the strong test to 2, 3, 5 and 7 is prime: not probably prime, but certainly, because every composite below that bound fails one of the four. Each further base pushes the first failure roughly a hundredfold. Jonathan Sorenson and Jonathan Webster showed in 2015 that the first twelve prime bases, 2 to 37, suffice for every number below $3.18 \times 10^{23}$, which covers every 64-bit integer with a wide margin. A computer checking whether a 64-bit number is prime therefore needs at most twelve modular exponentiations and no randomness at all, and the same twelve bases certified the primes of the constant that holds the primes as far as they reach. Above that range, a number that passes many random bases is called a probable prime, and when an actual proof is wanted it is supplied by a different kind of test that works for primality rather than against it — the certificates of an order that proves a prime, built from the factorisation of $n - 1$, or elliptic-curve certificates for numbers where that factorisation is out of reach. The strong test finds the primes; the certificates prove them.

How fast these thresholds grow is the open part. If the generalised Riemann hypothesis is true, Eric Bach proved, every composite fails the strong test for some base below $2(\ln n)^2$, which makes the test deterministic and polynomial in the number of digits — Miller’s original 1976 version. Without the hypothesis nobody can prove anything comparable, and the deterministic polynomial test that does exist unconditionally, the row that proves a prime that Agrawal, Kayal and Saxena found in 2002, is much slower in practice.

Strong pseudoprimes are rarer still #

Restrict to one base, 2, and compare the two tests. Below ten thousand there are 22 composites that satisfy $2^{n-1} \equiv 1 \pmod n$ and only 5 of them pass the strong test; below a million, 245 against 46; below ten million, 750 against 162. Both counts are a vanishing share of the 4,335,421 odd composites below ten million — the strong pseudoprimes to base 2 are 0.0037% of them — and the strong ones are about a fifth of the ordinary ones at every scale.

That ratio is not an accident of small numbers. A Fermat pseudoprime to base 2 has $2^{n-1} \equiv 1$, which says the order of 2 divides $n - 1$ on every dial; a strong one needs, in addition, that the chains on every dial reach $-1$ at the same step, which is a coincidence of the powers of 2 in the orders. The order of 2 modulo each prime factor, which the exponent that is smaller than Euler’s studied as the Carmichael function’s ingredients, decides both, and the extra synchronisation is what the strong test pays for.

Why the bound is a quarter #

The quarter can be read off Monier’s formula. The product $\prod \gcd(d, p_i - 1)$ involves only the odd parts of the $p_i - 1$, while $\varphi(n)$ contains every $p_i - 1$ whole, powers of 2 included, together with the extra factors of any repeated prime; the leading factor $1 + (2^{k\nu} - 1)/(2^k - 1)$ gives back only part of the powers of 2 the product left out. Working through the cases shows the share is at most a quarter, and that it equals a quarter exactly in two situations: $n = p(2p - 1)$ with both factors prime and $p$ leaving 3 on division by 4, or $n$ a Carmichael number with exactly three prime factors, each leaving 3 on division by 4. Both kinds appear in the figure — $91$ and $703$ of the first, $8{,}911 = 7 \cdot 19 \cdot 67$ of the second. Every other odd composite but 9 does strictly better, and most, as the next figure showed, do enormously better.

Fermat’s test has no such bound because its liars form a subgroup of the units modulo $n$ that can be the whole group, as it is for a Carmichael number. The strong liars are not a subgroup in general — the product of two strong liars need not be one — and that loss of structure is exactly what lets the count be held below a quarter. It is the same group of units that the necklaces that prove a theorem used to derive Fermat’s congruence by counting orbits; the strong test asks a finer question about that group, one its structure cannot answer “yes” to for most bases at once.

A quarter is a statement about the bases, not the number #

It is easy to misread what the bound promises. It says that for a fixed composite $n$, at most a quarter of the bases lie, so a base chosen uniformly at random exposes $n$ with probability at least three quarters, and $t$ independent bases all fail to expose it with probability at most $4^{-t}$. That is a statement about the randomness in the bases, which the tester controls, and it holds for every composite whatsoever, including one chosen by an adversary who knows the test. It is not a statement that a number which has passed $t$ tests is composite with probability $4^{-t}$: that would need a probability distribution on the numbers being tested, and the answer depends on it.

For numbers drawn at random from a range, the second probability is in fact far smaller than the first, because most composites have almost no liars and the few that have many are rare — the effect the typical-composite figure shows and that Damgård, Landrock and Pomerance quantified. For numbers chosen by an adversary, only the first is guaranteed, and it is enough: forty random bases leave a chance below $10^{-24}$ of accepting any given composite, smaller than the chance of a hardware error during the computation. Rabin’s 1980 paper is one of the founding examples of an algorithm whose correctness is a probability over its own coin tosses rather than over its inputs, and the quarter is what makes that probability computable.

Exact below 100,000, unknown beyond the fourth threshold #

The liar counts are exact. For 561 every base is tested; below 3,000 every base of every odd composite is tested and agrees with Monier’s formula; below 100,000 the formula is used, with factorisations by trial division. The searches for 2,047, 1,373,653 and 25,326,001 test every odd number in turn with the strong test to base 2 first, then the other bases and a primality check, so each is the smallest of its kind and not merely a small one. The fourth threshold is a quoted value checked in exact integer arithmetic.

None of this proves the quarter for numbers beyond 100,000; Monier’s and Rabin’s theorem does, and the figures show it holding where it can be checked. Nor do the counts say how the thresholds grow: four data points, rising by factors of 670, 18 and 127, suggest roughly exponential growth in the number of bases, but the true rate is unknown, and the computation of the next threshold, for the first five prime bases, took specialised sieving over numbers far beyond any naive search.

Still open: how many bases are enough #

Under the generalised Riemann hypothesis the answer is known: bases up to $2(\ln n)^2$. Unconditionally, it is not known whether the smallest base that exposes a composite $n$ is bounded by any fixed power of $\ln n$ — or even by $n^{\varepsilon}$ for small $\varepsilon$. The best unconditional bounds come from bounds on the least quadratic non-residue, which the first number that is not a square measured, and they are far weaker than what is believed.

The opposite direction is open too. Composites that pass the strong test to many small bases can be constructed — François Arnault built composites hundreds of digits long that pass every prime base up to a few hundred — but nobody knows how slowly the minimal such composites must grow with the number of bases, and the conjecture that the threshold for the first $k$ prime bases grows exponentially in $k$ rests on heuristics and on the dozen values that have been computed.

A test that cannot be fooled for long #

Fermat’s test can be fooled by every base at once, and the strong test, which watches the squarings that lead to $a^{n-1}$ for a square root of 1 other than $\pm 1$, cannot be fooled by more than a quarter of the bases of any odd composite but 9. For 561 it lets through 10 bases of 320; below 100,000 two thirds of the odd composites have no liars but 1 and $n - 1$, and the ones that reach a quarter exactly are the products $p(2p - 1)$. The smallest composites passing the first one, two, three and four prime bases are 2,047, 1,373,653, 25,326,001 and 3,215,031,751, so four fixed bases decide primality below three billion with certainty — and how fast those thresholds grow, which is what a deterministic test with a short list of bases depends on, is known only under the Riemann hypothesis.