Why 561 Passes Fermat's Test

Published December 17, 2024 · Revised July 24, 2026

Is 561 prime? Trial division says no ($3 \times 11 \times 17$). But check $2^{560} \bmod 561$: you get 1, exactly what a prime would give. Try $5^{560} \bmod 561$: also 1. Try any base coprime to 561: always 1. Every test of this form says 561 is prime.

561 is the smallest number with this property. It passes Fermat’s congruence for every base coprime to it, so repeating that test cannot resolve the error.

The path is: Fermat explains why 561 looks prime; Carmichael numbers show why repeating that test cannot work; the special way squares reach 1 modulo a prime supplies the missing evidence for Miller–Rabin. The final sections separate Baillie–PSW’s remarkable empirical record from a certificate, which is an actual proof of primality.

# Background

Given an arbitrary integer $n$, how do you decide whether it’s prime?

The stakes are not abstract. RSA key generation requires finding two large primes $p$ and $q$, often 1024 bits each for a 2048-bit modulus. Finite-field Diffie–Hellman systems also rely on suitable primes. Most deployed elliptic-curve systems use standardized fields instead of generating fresh primes per key, so primality testing is therefore part of key and parameter generation rather than every public-key operation.

# Trial division

The oldest approach: to test whether $n$ is prime, try dividing it by every integer from 2 up to $\sqrt{n}$. If none divide evenly, $n$ is prime.

This works because if $n = ab$ with $a \le b$, then $a \le \sqrt{n}$. So we only need to check potential factors up to the square root. After checking 2, even divisors can be skipped. Testing only primes removes more work; the Sieve of Eratosthenes can generate them for moderate bounds.

The complexity is $O(\sqrt{n})$ divisions. For a 10-digit number, that is roughly 100,000 divisions – fast on current hardware. For a 300-digit number (a typical RSA prime), $\sqrt{n}$ has 150 digits. There are approximately $10^{150}$ candidate divisors. At $10^{12}$ divisions per second, this would take about $10^{138}$ seconds. The universe is approximately $4 \times 10^{17}$ seconds old.

The issue is that $O(\sqrt{n})$ is exponential in the bit-length of $n$. If $n$ has $b$ bits, then $\sqrt{n} = 2^{b/2}$, and we need $2^{b/2}$ divisions. A polynomial-time algorithm would need $O(b^c)$ operations for some constant $c$. Trial division is correct and deterministic, but for cryptographic sizes it is computationally infeasible. This is not a constant-factor problem that faster hardware will solve. The gap is exponential.

# The probabilistic trade

The gap between cryptographic input sizes and trial division motivates randomized testing: accept a bounded probability of a false-prime answer.

A probabilistic primality test gives one of two answers: “definitely composite” or “probably prime.” In the language of randomized algorithms, this is a Monte Carlo algorithm: it always terminates in bounded time, but the answer might be wrong.The contrast is a Las Vegas algorithm, which always gives the correct answer but whose runtime is a random variable. ECPP (discussed below) is closer to the Las Vegas model: it always produces a correct certificate, but finding one can take unpredictable time. The naming is a gambling joke from the 1970s. The “probably” comes with a quantifiable error bound. An engineering system may accept a bound such as $2^{-128}$ as negligible, but it remains different from a proof.

There are several probability spaces here:

• for one fixed odd composite, at most $1/4$ of Miller–Rabin bases are strong liars;
• choosing $k$ independent uniform bases therefore gives worst-case error at most $4^{-k}$ for that candidate;
• drawing candidates from a random key-generation process supports sharper average-case bounds, but those depend on that distribution;
• a primality certificate is deterministic evidence and has no randomized false-prime probability.

The challenge is building a test with: (1) an error probability that decreases exponentially with the number of iterations, and (2) no blind spots: no class of composites that always fools the test regardless of how many iterations you run.

The first condition is achievable: run the test multiple times with independent random choices, and error probabilities multiply (shrinking exponentially). The Fermat test fails the second condition because Carmichael numbers form a universal blind spot for coprime bases.

# The modular setting

The tests below work with remainders rather than the full integers. The notation

$$x\equiv y\pmod n$$

means that $n$ divides $x-y$, so $x$ and $y$ have the same remainder after division by $n$. Addition and multiplication preserve this equivalence, which lets an implementation reduce after every operation instead of constructing an enormous power first.

The distinction between prime and composite moduli is structural. If $p$ is prime, every nonzero residue modulo $p$ has a multiplicative inverse; the residues form the field $\mathbb F_p$. For composite $n$, some nonzero residues have no inverse and zero divisors can appear. The condition $\gcd(a,n)=1$ says that the chosen base $a$ is invertible modulo $n$. Fermat, Miller–Rabin, and Lucas tests probe increasingly specific consequences of that prime-field structure.

# Fermat’s Little Theorem

In 1640, Pierre de Fermat stated a theorem that later became a basis for primality tests:

$$a^{p-1} \equiv 1 \pmod{p}$$

for any prime $p$ and integer $a$ not divisible by $p$.

Consider the $p-1$ nonzero residues $\{1, 2, \ldots, p-1\}$ modulo $p$. Multiplying each by $a$ (with $\gcd(a, p) = 1$) permutes this set: the map $x \mapsto ax \bmod p$ is a bijection on $\{1, \ldots, p-1\}$. Therefore:

$$\prod_{i=1}^{p-1} (a \cdot i) \equiv \prod_{i=1}^{p-1} i \pmod{p}$$

The left side is $a^{p-1} \cdot (p-1)!$ and the right side is $(p-1)!$. Since $p$ is prime, $(p-1)!$ is invertible mod $p$, giving $a^{p-1} \equiv 1$.

The contrapositive gives us a primality test: if $a^{n-1} \not\equiv 1 \pmod{n}$ for some $a$ coprime to $n$, then $n$ is definitely composite.

# The Fermat Primality Test

This observation leads to a probabilistic test:

1. Pick a random base $a$ with $1 < a < n-1$
2. Compute $a^{n-1} \mod n$
3. If the result is not 1, $n$ is composite
4. If the result is 1, $n$ is probably prime

Step 2 uses modular exponentiation by repeated squaring, which runs in $O(\log n)$ multiplications mod $n$, each costing $O((\log n)^2)$ with schoolbook multiplication. Total: $O((\log n)^3)$. The running time is polynomial in the bit length rather than exponential in it.

Note an asymmetry: the test can prove compositeness (if $a^{n-1} \not\equiv 1$, $n$ is definitely composite) but can only suggest primality (if $a^{n-1} \equiv 1$, $n$ might be prime). The test has no false-composite answers; its one-sided error is a false probable-prime answer.

The limitation is that some composite numbers pass this test.

# Pseudoprimes

A composite number $n$ is called a Fermat pseudoprime to base $a$ if $a^{n-1} \equiv 1 \pmod{n}$.

For example, $341 = 11 \times 31$ is a pseudoprime to base 2:

$$2^{340} \equiv 1 \pmod{341}$$

Why does this happen? The order of 2 modulo 11 is 10 (by Fermat’s little theorem, $2^{10} \equiv 1 \pmod{11}$), and the order of 2 modulo 31 is 5 (since $2^5 = 32 \equiv 1 \pmod{31}$). Since $10 \mid 340$ and $5 \mid 340$, we get $2^{340} \equiv 1$ modulo both 11 and 31, hence modulo $341$ by the Chinese Remainder Theorem.

This means the Fermat test with base 2 incorrectly identifies 341 as “probably prime.”

The base-2 pseudoprimes below 1000 are 341, 561, and 645. There are 245 below $10^6$, but their rarity is deceptive.12 It might suggest that testing multiple bases would catch all composites: if $n$ is a pseudoprime to base 2, surely it fails for base 3? Often yes. 341 fails for base 3. But 561, as the opening promised, does not fail for any base coprime to it.

# Carmichael Numbers

A composite number that is a pseudoprime to every base coprime to it is called a Carmichael number – and 561 is the smallest.15Vaclav Simerka found several examples in 1885, publishing in Casopis pro pestovani mathematiky a fysiky, a Czech-language journal with limited circulation outside Bohemia. His priority was recovered over a century later by Kral, Loebl, and Matousek (2001). In 1899, Alwin Korselt characterized them: a composite $n$ is a Carmichael number if and only if:

1. The number $n$ is square-free (no repeated prime factors)
2. For every prime $p$ dividing $n$, we have $(p-1) \mid (n-1)$

Korselt knew of no examples. In 1910, Robert D. Carmichael independently discovered 561. Why does it work? $561 - 1 = 560 = 2^4 \times 5 \times 7$, and:

• $3 - 1 = 2$ divides 560
• $11 - 1 = 10$ divides 560
• $17 - 1 = 16$ divides 560

The Fermat test fails completely on Carmichael numbers: no choice of base (coprime to $n$) will reveal their compositeness. For the Fermat test, Carmichael numbers are an unconditional blind spot. No amount of repetition helps.

Reproduce this figure

witness_table.pylockfilefigure_quality.pyuv run --locked witness_table.py

Korselt’s criterion has an intuitive interpretation: it says that $n$ “pretends” to be prime by having its prime factors’ orders all divide $n - 1$. The Chinese Remainder Theorem then forces $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ coprime to $n$. The deception is structural, not coincidental.

# How many exist?

For decades, mathematicians wondered whether there are infinitely many Carmichael numbers. In 1994, Alford, Granville, and Pomerance proved there are:6 for sufficiently large $x$, the count up to $x$ exceeds $x^{2/7}$. That exponent is a proved lower bound, not an estimate of the true density.

# Solovay-Strassen: The First Probabilistic Test

Carmichael numbers force a choice: find a stronger necessary condition for primality, or accept that the Fermat test has an unconditional blind spot. In 1977, Robert Solovay and Volker Strassen found one.1 Their test compares modular exponentiation with quadratic-residue information through the Euler criterion.

Lemma (Euler criterion). For an odd prime $p$ and $\gcd(a, p) = 1$:

$$a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod{p}$$

where $\left(\frac{a}{p}\right)$ is the Legendre symbol ($+1$ if $a$ is a quadratic residue mod $p$, $-1$ otherwise).

Proof sketch. Since $\mathbb{F}_p^\times$ is cyclic of order $p-1$, we have $a^{p-1} \equiv 1$, so $a^{(p-1)/2}$ is a square root of 1, hence $\pm 1$. Write $a = g^j$ for a generator $g$. Then $a^{(p-1)/2} = g^{j(p-1)/2}$. When $j$ is even, this is $(g^{p-1})^{j/2} = 1$, so $a$ is a quadratic residue. When $j$ is odd, $g^{j(p-1)/2} = g^{(p-1)/2} = -1$ (the unique element of order 2), so $a$ is a non-residue.

The Solovay-Strassen test: pick a random $a$, compute both $a^{(n-1)/2} \bmod n$ and the Jacobi symbol $\left(\frac{a}{n}\right)$ (which can be computed in $O(\log^2 n)$ by reciprocity, without knowing the factorization of $n$). If they disagree, $n$ is composite.

Why this breaks the Carmichael barrier: a Carmichael number $n$ satisfies $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ coprime to $n$, but this does not force $a^{(n-1)/2} \equiv \left(\frac{a}{n}\right)$. The Jacobi symbol factors multiplicatively over the prime factors of $n$, while the power $a^{(n-1)/2}$ does not decompose the same way. Solovay and Strassen proved that for any composite $n$, at least half of all bases $a$ in $\{1, \ldots, n-1\}$ are witnesses – the Euler criterion fails for them. This gives a $1/2$ error bound per round, worse than Miller-Rabin’s $1/4$ but sufficient to bypass Carmichael numbers entirely.

# Why Primes Are Algebraically Special

The Fermat test checks one property of primes: $a^{p-1} \equiv 1$. Miller’s test checks additional structure in the squaring chain: not just what the final value is, but how it got there. Fermat asks “is the answer 1?” Miller asks “what is the square root of that 1?” In a prime field, the only square roots of 1 are $\pm 1$. In a composite ring, there can be others, and finding one proves compositeness. To understand why, we need a fact about the multiplicative group modulo a prime.

When $p$ is prime, $\mathbb{F}_p^\times = \{1, 2, \ldots, p-1\}$ under multiplication is a cyclic group of order $p-1$. Every element is a power of some generator $g$. A consequence: the equation $x^2 \equiv 1 \pmod{p}$ has exactly two solutions: $x = 1$ and $x = -1$. This is because $x^2 - 1 = (x-1)(x+1)$, and in a field, each factor has at most one root.

For composite $n$, $(\mathbb{Z}/n\mathbb{Z})^\times$ is not cyclic in general – by the Chinese Remainder Theorem, it decomposes as a product of the groups for each prime factor. This product structure creates extra square roots of unity: elements $x$ with $x^2 \equiv 1 \pmod{n}$ but $x \not\equiv \pm 1 \pmod{n}$. For example, $4^2 = 16 \equiv 1 \pmod{15}$, but $4 \not\equiv \pm 1$.

These non-trivial square roots cannot exist modulo a prime but can exist modulo composites. Miller’s test detects such a root when it occurs in the squaring chain.

# Strong Pseudoprimes and Miller’s Test

In 1976, Gary Miller observed that we can strengthen the Fermat test by exploiting the algebraic structure above.2

Write $n - 1 = 2^s \cdot d$ where $d$ is odd. For a prime $p$ and base $a$ coprime to $p$, one of the following must hold:

$$a^d \equiv 1 \pmod{p}$$

or

$$a^{2^r d} \equiv -1 \pmod{p} \quad \text{for some } 0 \le r < s$$

Why must one of these hold? Start from Fermat: $a^{p-1} = a^{2^s d} \equiv 1 \pmod{p}$. Now consider the squaring chain:

$$a^d, \; a^{2d}, \; a^{4d}, \; \ldots, \; a^{2^s d}$$

The last term is 1. Each term is the square of the previous. Working backwards from $a^{2^s d} \equiv 1$: if $a^{2^r d} \equiv 1$, then $a^{2^{r-1} d}$ is a square root of 1 modulo $p$. In a field (which $\mathbb{Z}/p\mathbb{Z}$ is, since $p$ is prime), the polynomial $x^2 - 1$ has at most two roots: $+1$ and $-1$. So either the previous term is also 1 (and we continue backwards) or it is $-1$ (and we stop). Eventually we either reach $a^d \equiv 1$ or find some $a^{2^r d} \equiv -1$.

For composite $n$, the ring $\mathbb{Z}/n\mathbb{Z}$ can contain additional square roots of unity. For example, modulo $n = 15$, we have $4^2 = 16 \equiv 1$, although $4 \not\equiv \pm1$. Miller’s test uses the appearance of such a root as a compositeness witness.

Worked example: $n = 341$, $a = 2$. Recall that 341 passes the Fermat test for base 2. Write $341 - 1 = 340 = 2^2 \times 85$, so $s = 2$ and $d = 85$. The squaring chain is:

$$2^{85} \bmod 341 = 32, \quad 32^2 \bmod 341 = 1024 \bmod 341 = 1$$

Reproduce this figure

squaring_comparison.typ_diagram-style.typtypst compile squaring_comparison.typ squaring_comparison.png --ppi 500 --root ..

The chain went from 32 to 1 in one squaring. But $32 \not\equiv 1$ and $32 \not\equiv -1 \pmod{341}$ (since $-1 \equiv 340$). So 32 is a non-trivial square root of 1 modulo 341, a witness that cannot exist modulo a prime. Miller’s test identifies 341 as composite. The Fermat test missed this because it only checks the final value $2^{340} \bmod 341 = 1$, discarding the information in the intermediate steps.

A composite number that passes this stronger test for base $a$ is called a strong pseudoprime to base $a$. Unlike the Fermat test, there are no “strong Carmichael numbers”: no composite passes for all bases.

# The Miller-Rabin Test

In 1980, Michael Rabin made Miller’s test probabilistic and proved the following bound:3 for any composite $n$, at most $1/4$ of bases $a$ in $\{2, \ldots, n-2\}$ are strong liars (bases for which $n$ passes the strong test). Louis Monier independently proved the same bound the same year.

Theorem (Rabin and Monier, 1980).3 If $n$ is an odd composite, the number of strong liars in $\{1, \ldots, n-1\}$ is at most $\frac{n-1}{4}$.

Proof idea. Write $n-1=2^s d$ and factor $n$ into prime powers. By the Chinese Remainder Theorem, a passing base must make the same squaring-chain condition hold in every prime-power component: either the initial value is 1 everywhere, or all components reach $-1$ at the same stage. Counting the compatible residue classes across those components gives Monier’s exact liar formula and Rabin’s one-quarter bound. The counting is subtler than saying “the strong liars form a subgroup”: in general, the passing set need not be closed under multiplication.

This is the proof boundary used by the rest of the article: the square-root mechanism is derived above, while the exact residue-class count and the one-quarter theorem are imported from Rabin and Monier.

This means:

• Each iteration has at most $1/4$ probability of being fooled
• After $k$ iterations with independent random bases, the error probability is at most $(1/4)^k$
• With 40 iterations, the worst-case bound is $2^{-80}$, about $8.3\times10^{-25}$

The candidate-generation probability space admits sharper results. Damgård, Landrock, and Pomerance11 analyze a loop that repeatedly draws uniform odd $k$-bit candidates until one passes $t$ Miller–Rabin rounds, and bound the probability that the returned candidate is composite. Their examples include $p_{600,1}\le 2^{-75}$ and $p_{300,5}\le 2^{-60}$. These are not conditional error bounds for a uniformly drawn odd composite, and they depend on the stated candidate-generation process.

Unlike the Fermat test, Miller-Rabin has no Carmichael-style universal blind spot. For every odd composite, including every Carmichael number, at least three quarters of the candidate bases are witnesses.

# Implementation

Modular exponentiation by repeated squaring makes each round efficient. Here is a complete Miller-Rabin test in Python:

import secrets

def is_probable_prime(n, k=40):
    """Miller-Rabin with k rounds. False = composite, True = probably prime."""
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0: return False
    # Write n - 1 = 2^s * d with d odd
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = 2 + secrets.randbelow(n - 3)
        x = pow(a, d, n)          # a^d mod n
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)      # square mod n
            if x == n - 1:
                break
        else:
            return False           # composite witness found
    return True

Python’s built-in three-argument pow(a, d, n) performs modular exponentiation without first materializing $a^d$, so the example remains practical for large inputs. secrets is used because the worst-case calculation assumes bases are sampled independently and uniformly; random is a deterministic simulation generator, not a cryptographic source. Forty rounds give an 80-bit worst-case bound. Real key-generation standards choose test counts from the candidate size, candidate source, desired strength, and whether a Lucas test follows; 40 is a pedagogical default, not a universal production rule.

The for/else construct is Python-specific: the else clause executes only if the inner for loop completes without break, meaning none of the squarings produced $-1$, so $a$ is a witness to compositeness.

# Deterministic Variants

# Miller’s test under GRH

Miller’s original 1976 test was deterministic, conditional on the extended Riemann hypothesis for relevant Dirichlet $L$-functions.2 Miller established a polynomial witness bound; the explicit statement that a composite has a witness below $2(\ln n)^2$ follows from Bach’s later bounds.16 Testing all bases below that limit gives a deterministic polynomial-time test conditional on the hypothesis.

This form of the extended or generalized Riemann hypothesis remains unproved.

# Known deterministic witness sets

Even without ERH, exhaustive computation has established that specific small sets of bases suffice for bounded ranges. These results turn Miller-Rabin into a deterministic test for numbers below each bound:

The last row is a convenient seven-base result for unsigned 64-bit integers; the entries need not themselves be prime. The set comes from Jim Sinclair’s exhaustive computation, summarized with implementation discussion on MathOverflow. It makes Miller–Rabin deterministic on that bounded domain when the algorithm handles a listed base outside $[2,n-2]$ correctly, including the case where its residue modulo $n$ is zero. It should not be projected onto current library implementations without checking their source: for example, Go’s math/big uses a different combination of small-prime filtering, pseudorandom Miller–Rabin rounds, and a Lucas test.

The smallest strong pseudoprime to base 2 is 2047 – which is why base $\{2\}$ alone suffices below that threshold.

# BPSW: a fixed probable-prime test

Randomized Miller–Rabin can drive a proved error bound down by adding independent rounds. The Baillie–PSW test, introduced through work by Robert Baillie,4 Carl Pomerance, John Selfridge, and Samuel Wagstaff,5 instead fixes two complementary checks:

1. A Miller-Rabin test to base 2
2. A strong Lucas probable prime test (with a specific parameter selection method)

A composite that slips through the base-2 strong test often fails the Lucas test. The two components probe different recurrence structures, but their pseudoprime sets are not proved independent or disjoint. BPSW is therefore a deterministic procedure that returns a probable-prime result, not a randomized algorithm with a bound that can be multiplied across rounds.

The Lucas test works in a different algebraic setting. Given parameters $P$ and $Q$ with discriminant $D=P^2-4Q$, define

$$\begin{aligned} U_0&=0,& U_1&=1,& U_k&=PU_{k-1}-QU_{k-2},\\ V_0&=2,& V_1&=P,& V_k&=PV_{k-1}-QV_{k-2}. \end{aligned}$$

If $\alpha$ and $\beta$ are the roots of $z^2-Pz+Q=0$, then

$$U_k=\frac{\alpha^k-\beta^k}{\alpha-\beta}, \qquad V_k=\alpha^k+\beta^k.$$

These formulas explain why a quadratic extension enters. For an odd prime $p$ not dividing $2QD$, with Jacobi symbol $(D/p)=-1$, the two roots are not in $\mathbb F_p$, but the Frobenius map $x\mapsto x^p$ swaps them in $\mathbb F_{p^2}$. Hence $\alpha^p=\beta$ and $\beta^p=\alpha$, which forces $U_{p+1}\equiv0\pmod p$.

The strong Lucas test keeps the path to that zero. More generally write

$$n-\left(\frac Dn\right)=d\,2^s$$

with $d$ odd. A prime must satisfy

$$U_d\equiv0\pmod n \quad\text{or}\quad V_{d2^r}\equiv0\pmod n \ \text{for some }0\leq r<s.$$

This is the Lucas analogue of retaining Miller–Rabin’s squaring chain rather than checking only its endpoint. Selfridge’s parameter rule tries $D=5,-7,9,-11,13,-15,\ldots$ until $\left(\frac Dn\right)=-1$, then takes $P=1$ and $Q=(1-D)/4$. A nontrivial $\gcd(D,n)$ found during this search is already a factor witness.

The distinct Miller–Rabin and Lucas structures explain why the pair is empirically effective, but do not prove that the fixed pair accepts no composite.

No BPSW counterexample is known. The original 1980 paper offered a $30 reward for one.5 In 2021, Baillie, Fiori, and Wagstaff14 offered $2,000 for a counterexample to a strengthened variant. The bounty and the size of searched ranges are useful empirical evidence, not a correctness theorem.

BPSW requires one base-2 strong test and one Lucas computation, giving it a fixed computational profile. Libraries vary in their exact variant and in whether they add randomized Miller–Rabin rounds.

# Beyond Miller-Rabin

Randomized Miller–Rabin and fixed probable-prime procedures such as BPSW do not produce proofs. For primality certificates, mathematical proofs, or auditable records, we need a test that proves primality unconditionally.

# AKS: unconditional polynomial time

In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena proved that primality is in P:7The preprint circulated in August 2002. The journal publication in Annals of Mathematics appeared in 2004. Dates in citations refer to journal publication; “2002” in prose refers to when the result became known. there exists a deterministic polynomial-time algorithm that decides primality without any unproven hypothesis. AKS was the first test that is simultaneously general (works for all integers), polynomial-time, deterministic, and unconditionally correct. Trial division is deterministic and correct but exponential in input length; Miller–Rabin is fast but randomized unless paired with a bounded-domain witness theorem or an unproved hypothesis; ECPP produces checkable proofs but its practical running-time analysis is heuristic.

Kayal and Saxena were BTech students of Agrawal at IIT Kanpur. The preprint circulated in August 2002 and prompted early variants by Berrizbeitia and Bernstein; later work, including Lenstra–Pomerance, improved the complexity bound.

The original algorithm runs in $\tilde{O}((\log n)^{12})$ time. Lenstra and Pomerance8 improved this to $\tilde{O}((\log n)^6)$ in 2005. The key idea starts from a classical observation: if $n$ is prime, then the polynomial identity

$$(x + a)^n \equiv x^n + a \pmod{n}$$

holds in $\mathbb{Z}_n[x]$ for all $a$ (this is essentially the Frobenius endomorphism). For composite $n$, this identity generally fails. But checking it directly requires working with a polynomial of degree $n$ – which is as expensive as trial division.

AKS’s insight is to choose $r$ such that the multiplicative order $\text{ord}_{r}(n)>(\log n)^2$, then check the identity modulo $x^r-1$: verify $(x + a)^n \equiv x^{n \bmod r} + a$ in $\mathbb{Z}_n[x]/(x^r - 1)$. The polynomials then have degree at most $r$.

The key implication uses all of these conditions: the order bound on $r$; failure of the perfect-power test; absence of a factor at most $r$; and $(x + a)^n \equiv x^n + a \pmod{n, x^r - 1}$ for $a = 1, 2, \ldots, \lfloor\sqrt{\phi(r)} \log n\rfloor$. The proof constructs a group $G$ of residues in $(\mathbb{Z}/n\mathbb{Z})[x]/(x^r - 1)$ generated by $\{x + 1, x + 2, \ldots\}$ and obtains incompatible lower and upper bounds on $|G|$ unless $n$ is prime. The total number of checks is polynomial in $\log n$.

The group-size contradiction is an imported correctness result here. The article states the conditions it consumes and the mechanism of the proof, but does not reconstruct the lower and upper bounds on $|G|$.

AKS is not used in ordinary primality-testing pipelines. Bounded deterministic Miller–Rabin, randomized probable-prime tests, and ECPP are much faster on the input sizes engineers actually encounter. AKS is often called a “galactic algorithm”: its polynomial guarantee is theoretically decisive, but not a practical speed claim. Its significance is settling the complexity question.

# ECPP: practical primality certificates

Elliptic Curve Primality Proving (ECPP) was developed by Shafi Goldwasser and Joe Kilian in 1986,10 and refined into a practical algorithm by A. O. L. Atkin and Francois Morain in 1993.9 It runs in $\tilde{O}((\log n)^5)$ heuristic time and produces a primality certificate – a compact proof that anyone can verify much faster than it took to produce.

The core idea uses elliptic curves over $\mathbb{Z}/n\mathbb{Z}$. Given a point $P$ on an elliptic curve $E$ modulo $n$, if we can show that the group order $|E(\mathbb{Z}/n\mathbb{Z})|$ has a large prime factor $q$, and certain conditions hold, then either $n$ is prime or $n$ has a very small factor (which we can check by trial division). The problem then reduces to proving $q$ is prime, a smaller instance of the same problem. This recursive structure terminates quickly.

The certificate is an Atkin–Goldwasser–Kilian–Morain certificate: a chain of elliptic curves and points that witnesses primality at each recursive step. Verification runs in polynomial time and does not require trusting the prover’s computation. This is the key distinction from probable-prime tests: ECPP says “here is a proof; check it yourself.”

The elliptic-curve order criterion and the certificate verifier are imported here rather than derived. The reconstructible claim is the evidence boundary: ECPP emits a deterministic certificate whose verification is separate from the heuristic search used to find it.

ECPP has proved general-form primes with tens of thousands of digits. That is a different task from proving primes of special form: Mersenne numbers, for example, admit the deterministic Lucas–Lehmer test.

# Comparison

These tests exploit progressively more algebraic structure. The Fermat test checks an exponent identity in the multiplicative group. Miller–Rabin retains the repeated-squaring path and checks where it can first reach 1.Writing $n-1=2^s d$ separates the odd part of the exponent from its power-of-two part. The chain $a^d,a^{2d},\ldots,a^{2^s d}$ follows successive squaring inside the subgroup generated by $a$; it is not necessarily the whole Sylow 2-subgroup. The Lucas test uses a second-order recurrence. ECPP uses the group structure of elliptic curves.

# How Real Systems Test Primality

This section is version-stamped July 24, 2026 because library pipelines change.

• Go math/big first filters small factors. ProbablyPrime(n) then performs n+1 pseudorandom Miller–Rabin rounds, including a forced base-2 round, followed by an almost-extra-strong Lucas test. With n=0, it performs the fixed base-2-plus-Lucas screen.
• OpenSSL 3.6.3 sieves generated candidates with small-prime residues, then runs random Miller–Rabin rounds: 64 for candidates through 2048 bits and 128 above that. This path does not add a Lucas test.
• GMP 6.3.0’s mpz_probab_prime_p performs trial divisions and a BPSW screen, then runs reps - 24 Miller–Rabin tests when that number is positive.
• FIPS 186-5 permits either repeated Miller–Rabin alone or Miller–Rabin followed by a Lucas test. Counts depend on candidate type, bit length, target error, and which alternative is used. For uniformly random 1024-bit $p$ and $q$ candidates, Table B.1 specifies four Miller–Rabin-only rounds for a $2^{-100}$ target and five for $2^{-112}$.

Those small FIPS counts are posterior statements under a random-candidate model, not the same quantity as Rabin’s $4^{-t}$ bound conditional on an arbitrary fixed composite.

The prime number theorem also needs the candidate space stated correctly. Near $N=2^{1024}$, an unrestricted integer is prime with probability about $1/\ln N$. If generation has already forced the candidate odd, the probability is about $2/\ln N$, so the expected number of odd candidates is $\ln(2^{1024})/2\approx355$, not 710. Small-prime sieving cheaply rejects most of those before a large modular exponentiation.

The numerical claims above – the pseudoprime counts, the 341 squaring chain, the 40-round bound, and the expected odd-candidate count – are checked together with:

# Timing side channels

Candidate generation is normally variable-time: standards and implementations allow early rejection of small-factor composites. That alone does not mean total runtime reveals the accepted prime or makes the final modulus easy to factor. The security question is narrower: can an observer measure cache, branch, or arithmetic behavior that depends on secret candidate values closely enough to recover them?

That threat is real in some environments. Co-located cache attacks have recovered RSA keys from secret-dependent GCD and modular-exponentiation code paths during key generation. Defenses therefore belong at the operations and boundaries the threat model exposes: constant-time big-integer primitives where secret operands matter, avoidance of secret-indexed memory access, isolation from hostile co-tenants, and blinding or hardened library routines where appropriate. “Every rejection takes identical wall time” is neither a general requirement nor how OpenSSL’s search loop is structured.13

# Open Problems

# The BPSW question

The central open problem in practical primality testing: does a BPSW counterexample exist?

Heuristics and extensive computation suggest that a counterexample, if one exists, is rare. Neither kind of evidence determines where the first one must occur.

Baillie, Fiori, and Wagstaff offered a $2,000 bounty for a proof or a counterexample.14 If no counterexample exists, proving this would likely require new techniques in analytic number theory. If one exists, finding it would likely require new techniques in constructive algebra.

BPSW is widely used as a fast fixed screen. No counterexample is known, and there is no proof that none exists.

# References

[1] Solovay, R. & Strassen, V. (1977). “A Fast Monte-Carlo Test for Primality.” SIAM Journal on Computing, 6(1), 84-85. ↩

[2] Miller, G. L. (1976). “Riemann’s Hypothesis and Tests for Primality.” Journal of Computer and System Sciences, 13(3), 300-317. ↩

[3] Rabin, M. O. (1980). “Probabilistic Algorithm for Testing Primality.” Journal of Number Theory, 12(1), 128-138. ↩

[4] Baillie, R. & Wagstaff, S. S. (1980). “Lucas Pseudoprimes.” Mathematics of Computation, 35(152), 1391-1417. ↩

[5] Pomerance, C., Selfridge, J. L. & Wagstaff, S. S. (1980). “The Pseudoprimes to 25 x 10^9.” Mathematics of Computation, 35(151), 1003-1026. ↩

[6] Alford, W. R., Granville, A. & Pomerance, C. (1994). “There Are Infinitely Many Carmichael Numbers.” Annals of Mathematics, 139(3), 703-722. ↩

[7] Agrawal, M., Kayal, N. & Saxena, N. (2004). “PRIMES Is in P.” Annals of Mathematics, 160(2), 781-793. ↩

[8] Lenstra, H. W. & Pomerance, C. (2019). “Primality Testing with Gaussian Periods.” Journal of the European Mathematical Society, 21(4), 1229–1269. (Manuscript circulated 2005.) ↩

[9] Atkin, A. O. L. & Morain, F. (1993). “Elliptic Curves and Primality Proving.” Mathematics of Computation, 61(203), 29-68. ↩

[10] Goldwasser, S. & Kilian, J. (1986). “Almost All Primes Can Be Quickly Certified.” Proceedings of the 18th STOC, 316-329. ↩

[11] Damgård, I., Landrock, P. & Pomerance, C. (1993). “Average Case Error Estimates for the Strong Probable Prime Test.” Mathematics of Computation, 61(203), 177-194. ↩

[12] Pomerance, C. (1981). “On the Distribution of Pseudoprimes.” Mathematics of Computation, 37(156), 587-593. ↩

[13] Cabrera Aldaya, A., Pereida García, C., Alvarez Tapia, L. M., & Brumley, B. B. (2019). “Cache-Timing Attacks on RSA Key Generation.” IACR Transactions on Cryptographic Hardware and Embedded Systems 2019(4), 213–242. ↩

[14] Baillie, R., Fiori, A. & Wagstaff, S. S. (2021). “Strengthening the Baillie-PSW Primality Test.” Mathematics of Computation, 90(330), 1931-1955. ↩

[15] Kral, D., Loebl, M. & Matousek, J. (2001). “Simerka as a predecessor of Carmichael.” Expositiones Mathematicae, 19(4), 377–381. ↩

[16] Bach, E. (1990). “Explicit Bounds for Primality Testing and Related Problems.” Mathematics of Computation, 55(191), 355–380. ↩