31.8 Primality Testing

Fermat's test (CLRS Theorem 31.31). For a prime p and a coprime to p, a^(p−1) ≡ 1 (mod p). Consequently, if some a coprime to n satisfies a^(n−1) ≢ 1 (mod n), then n is not prime.

n is a Fermat pseudoprime to base a: it is composite yet passes the Fermat test a^(n−1) ≡ 1 (mod n).

PSEUDOPRIME (CLRS §31.8). The executable test: n passes when 2^(n−1) ≡ 1 (mod n).

PSEUDOPRIME is correct on odd primes: every prime n ≠ 2 passes the test. (The base case n = 2 is a known special case handled separately.)

n is a Carmichael number if it is composite and passes the Fermat test a^(n−1) ≡ 1 (mod n) for every a coprime to n (CLRS §31.8). Such numbers fool the Fermat primality test for every base, so the test alone cannot certify primality.

A Carmichael number is composite.

A Carmichael number is larger than one.

A Carmichael number passes the Fermat test for every base coprime to it.

A Carmichael number is a Fermat pseudoprime to every base coprime to it.

Combining congruences under coprime moduli. If a ≡ b (mod m) and a ≡ b (mod n) with m, n coprime, then a ≡ b (mod m·n). This is the "glue" needed to lift a congruence from pairwise-coprime prime factors to their product (used to verify that 561 is a Carmichael number).

561 is a Carmichael number. The smallest Carmichael number (CLRS §31.8). It shows the Fermat test can be fooled by a composite integer for every base coprime to it, so PSEUDOPRIME cannot certify primality.

STRONG-PSEUDOPRIME parameters (CLRS §31.8). Write n−1 = 2^s · d with d odd: s is the exponent of 2 in the prime factorization of n−1, and d is the odd part.

STRONG-PSEUDOPRIME (CLRS §31.8). n is a strong probable prime to base a if, writing n−1 = 2^s·d with d odd, either a^d ≡ 1 (mod n) or a^(2^i·d) ≡ −1 (mod n) for some i < s.

WITNESS (CLRS §31.8). A base a witnesses that n is composite when n fails the strong-pseudoprime test to base a. A witness certifies ¬ Nat.Prime n.

MILLER-RABIN (single base, CLRS §31.8). The executable decision procedure returning whether n is a strong probable prime to base a.

STRONG-PSEUDOPRIME decomposition (CLRS §31.8). For n ≠ 0, n = 2^s · (n / 2^s) where s is the exponent of 2 in n — i.e. the odd part of n times 2^s recovers n.

Roots of unity modulo a prime. If b^2 ≡ 1 (mod p) for a prime p and b ≢ 1 (mod p), then b ≡ −1 (mod p). This is the only fact about prime moduli needed by the Miller-Rabin correctness proof: repeatedly squaring a root of unity can only reach 1 through −1.

Miller-Rabin correctness, prime direction. If n is prime and a is coprime to n, then n is a strong probable prime to base a — i.e. a prime has no witness. Writing n−1 = 2^s·d, the sequence a^d, a^{2d}, …, a^{2^s·d} ends at 1 (Fermat); at the first index where it reaches 1, the previous value is a square root of 1 that is not 1, hence −1 (mod a prime).

A prime has no witness: for n prime and a coprime to n, a does not witness compositeness of n.

A witness certifies compositeness: for n and a coprime base a, if a is a witness then n is not prime.

(n−1)² ≡ 1 (mod n) for n ≠ 0: n divides (n−1)² − 1 = n·(n−2).

A strong probable prime satisfies Fermat's congruence. If n is a strong pseudoprime to base a, then a^(n−1) ≡ 1 (mod n). Indeed n−1 = 2^s·d, and either a^d ≡ 1 or a^(2^i·d) ≡ −1 for some i < s; in the second case a^(n−1) = (a^(2^i·d))^(2^(s−i)) ≡ (−1)^even = 1. This is the first step of the Miller-Rabin error-bound proof: every strong liar lies in the kernel of a ↦ a^(n−1).

The reduction (ZMod n)ˣ → (ZMod p)ˣ of units when p ∣ n.

The unit group of ZMod n has φ(n) elements.

For a prime p, the unit group of ZMod p has p − 1 elements.

The subgroup {1, −1} of the units modulo n.

The power homomorphism x ↦ x^m on the units modulo n.

The good set S_m = {x ∈ (ZMod n)ˣ : x^m ∈ {1, −1}}, a subgroup of the units (the preimage of {1, −1} under the power map x ↦ x^m).

Membership in goodSet as a power-of-a-unit condition.

Membership in goodSet as a power condition in ZMod n.

ν(n): the minimum over prime factors p of n of v₂(p − 1), the 2-adic valuation of p − 1. This is the index bound used to define the good subgroup for the Miller-Rabin error bound.

For every prime factor p | n, ν(n) ≤ v₂(p − 1).

2^ν(n) divides p − 1 for every prime factor p | n.

ν(n) ≥ 1 for odd n > 1: every prime factor is odd, so p − 1 is even.

The odd part a / 2^(v₂(a)) of a nonzero a is odd.

The odd part t = (n−1)/2^(v₂(n−1)) of n−1 is odd.

The good subgroup S(n) (Rabin–Monier). Writing n−1 = 2^s·t with t odd and ν = ν(n), S(n) = {x ∈ (ZMod n)ˣ : x^(2^(ν−1)·t) ∈ {1, −1}}. Every strong liar lies in S(n), and |S(n)| ≤ (n−1)/4.

Parity lemma. If a^(2^i·d) has order 2 in a finite group and d is odd, then 2^(i+1) divides the order of a. Indeed orderOf a = 2·gcd(orderOf a, 2^i·d), whose 2-adic valuation forces v₂(orderOf a) = i+1.