Where Primes Come From: The Fermat Test, Carmichael Numbers and Miller–Rabin

This article has three layers:

1. The intuition: why primality can be decided without factoring, and the idea of "random spot checks"
2. Real-world use: RSA key generation, OpenSSL and accidents in prime generation
3. The mathematics: the Fermat test, Carmichael numbers, why Miller–Rabin is correct and a worked example with $561$

Layer 1: The Intuition

1.1 Deciding primality is far easier than factoring

"Is $N$ prime?" and "which two numbers multiply to $N$?" sound like the same question, but their difficulty is worlds apart:

• Deciding whether a 1000-digit number is prime: under a second on a laptop;
• Factoring a 600-digit (2048-bit) RSA modulus: beyond all the world's computers put together today.

The remarkable part is that a primality test can declare a number composite without finding any factor. It is like a counterfeit detector: it doesn't need to know who printed the fake, only that some feature is wrong.

1.2 Are there enough primes?

The prime number theorem says that near $N$, about one number in $\ln N$ is prime. For a 1024-bit number, $\ln 2^{1024} \approx 710$; picking only odd numbers, you hit a prime after about 355 tries on average. Each test is fast, so generating primes isn't slow.

1.3 The "spot check" idea

Primes always satisfy certain properties (such as Fermat's little theorem). We pick some random bases $a$ and check:

• If the check fails even once, the number is definitely composite;
• If it passes every time, the number is very likely prime.

The key is designing a check where a composite's chance of slipping through is low enough. Each round of Miller–Rabin is fooled with probability at most $1/4$. After 40 rounds, the chance of being fooled is at most $4^{-40} = 2^{-80}$, lower than the chance of a hardware fault.

Layer 2: Real-World Use

• RSA key generation: OpenSSL, BoringSSL and hardware security modules all use a combination of "trial division by small primes + Miller–Rabin". Trial division by the first few hundred small primes quickly eliminates most candidates.
• Diffie–Hellman parameters: generating a "safe prime" $p = 2q + 1$ requires both $p$ and $q$ to be prime.
• Standards: US FIPS 186-5 specifies the number of Miller–Rabin rounds for key generation, sometimes adding a Lucas test (the combination is called Baillie–PSW, and no composite that fools it has been found so far).

Layer 3: The Mathematics

3.1 The Fermat test

Fermat's little theorem: if $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod p$. (This is Lagrange's theorem for $\mathbb{Z}_p^\times$, whose order is $p-1$.)

The test: pick a random $a$ and compute $a^{N-1} \bmod N$. If it isn't $1$, $N$ is definitely composite.

Most composites fail right here. For example with $N = 15$, $2^{14} = 16384 \equiv 4 \pmod{15}$, and it is exposed at once.

3.2 Carmichael numbers

There is a class of composites satisfying $a^{N-1} \equiv 1$ for every $a$ coprime to them, called Carmichael numbers.

Korselt's criterion: a composite $N$ is a Carmichael number if and only if $N$ is squarefree and $(p - 1) \mid (N - 1)$ for every prime factor $p \mid N$.

The smallest example is $561 = 3 \times 11 \times 17$: $560$ is divisible by $2$, $10$ and $16$. By the Chinese Remainder Theorem, $a^{560}$ is $1$ modulo each of $3$, $11$ and $17$, and so also $1$ modulo $561$.

In 1994 Alford, Granville and Pomerance proved there are infinitely many Carmichael numbers. So the Fermat test alone won't do.

3.3 The key lemma: modulo a prime, $1$ has only two square roots

If $p$ is an odd prime and $x^2 \equiv 1 \pmod p$, then $p \mid (x-1)(x+1)$. Because $\mathbb{Z}_p$ is a field (it has no zero divisors), either $x \equiv 1$ or $x \equiv -1$.

Conversely, if you find $x \not\equiv \pm 1$ with $x^2 \equiv 1 \pmod N$, then $\mathbb{Z}_N$ has zero divisors and $N$ must be composite (and $\gcd(x - 1, N)$ is a nontrivial factor).

3.4 Miller–Rabin

Write $N - 1$ as $2^s \cdot d$ with $d$ odd. Pick a random $a$ and look at this sequence:

$$a^d,\ a^{2d},\ a^{4d},\ \dots,\ a^{2^s d} = a^{N-1} \pmod N.$$

Each term is the square of the previous one. If $N$ is prime, the last term is $1$ by Fermat's little theorem; and by the lemma in 3.3, taking square roots backwards, the first departure from $1$ must be $-1$. So a prime always satisfies:

Either $a^d \equiv 1$, or some term of the sequence equals $-1$.

If this fails, the number is declared composite. Rabin proved that for a composite $N$, at most $1/4$ of the bases $a$ can fool this test.

3.5 A worked example: exposing $561$

3.6 Deterministic algorithms

In 2002 Agrawal, Kayal and Saxena gave the AKS algorithm, the first proof that primality can be tested in deterministic polynomial time (the paper is titled PRIMES is in P). It is much slower than Miller–Rabin, though, so probabilistic algorithms are still used in practice.

Summary