Arithmetic on numbers too large to fit in a word, and the one problem whose difficulty is the entire point — factoring, on which public-key cryptography rests.
This is the chapter where input size means bits, not items. An algorithm on a β-bit number is efficient if it is polynomial in β, which means polynomial in lg n — a far stricter standard than elsewhere in the book. The chapter builds up from gcd through modular arithmetic to RSA, and its most interesting feature is that it needs both a problem that is easy (primality testing) and a closely related one that is hard (factoring), with security resting on the gap between them.
n for primality in O(√n) operations, which sounds fast. But n has β = lg n bits, so √n = 2β/2 — exponential in the input size. For a 2048-bit RSA modulus that is 21024 operations. An algorithm here is efficient only if it is polynomial in the number of digits.CLRS also notes that arithmetic on β-bit numbers is no longer O(1): addition is Θ(β) and schoolbook multiplication is Θ(β²). The RAM model’s constant-time arithmetic assumption from Chapter 2 is explicitly suspended.
gcd(a, b) = gcd(b, a mod b).EUCLID(a, b)
1 if b == 0
2 return a
3 else return EUCLID(b, a mod b)a > b ≥ 0 and EUCLID(a,b) performs k ≥ 1 recursive calls, then a ≥ Fk+2, the (k+2)nd Fibonacci number. Since Fibonacci numbers grow exponentially, the number of calls is O(lg b) — and consecutive Fibonacci numbers are the worst case, a satisfying connection back to Chapter 3.With β-bit inputs, the running time is O(β) arithmetic operations, or O(β³) bit operations with schoolbook division.
The same recursion, additionally producing coefficients that express the gcd as a combination of the inputs.
EXTENDED-EUCLID(a, b)
1 if b == 0
2 return (a, 1, 0)
3 (d′, x′, y′) = EXTENDED-EUCLID(b, a mod b)
4 (d, x, y) = (d′, y′, x′ - ⌊a/b⌋·y′)
5 return (d, x, y)Returns (d, x, y) with d = gcd(a,b) = ax + by. Same O(lg b) cost.
gcd(a,b) = ax + by is Bézout’s identity, and its algorithmic payoff is modular inverses. If gcd(a,n) = 1 then ax + ny = 1, so ax ≡ 1 (mod n) and x is the multiplicative inverse of a modulo n. That single computation is what makes RSA decryption possible.Two groups matter:
| Group | Elements | Operation | Size |
|---|---|---|---|
(ℤₙ, +ₙ) | {0, 1, …, n-1} | Addition mod n | n |
(ℤₙ*, ·ₙ) | Elements coprime to n | Multiplication mod n | φ(n) |
φ(n) is Euler’s totient, the count of integers in [1,n] coprime to n. For a prime p, φ(p) = p - 1; for a product of two distinct primes, φ(pq) = (p-1)(q-1) — the value RSA is built on.
p is prime and gcd(a,p) = 1, then ap-1 ≡ 1 (mod p).gcd(a,n) = 1, then aφ(n) ≡ 1 (mod n).
Both say exponents can be reduced modulo the group order, and both are used directly in the sections below.
Computing aᵇ mod n by multiplying b times is exponential in the bit length. Repeated squaring fixes it.
MODULAR-EXPONENTIATION(a, b, n)
1 c = 0; d = 1
2 let ⟨bₖ, bₖ₋₁, …, b₀⟩ be the binary representation of b
3 for i = k downto 0
4 c = 2c
5 d = (d · d) mod n // square
6 if bᵢ == 1
7 c = c + 1
8 d = (d · a) mod n // multiply
9 return dO(β) squarings and multiplications for a β-bit exponent, so O(β³) bit operations. Reducing mod n at every step keeps the intermediate values small, which is essential — without it the numbers grow astronomically.
n = n₁n₂⋯nₖ with the nᵢ pairwise coprime, then ℤₙ is isomorphic to ℤn₁ × ⋯ × ℤnₖ. A number mod n is completely determined by its residues modulo each factor, and arithmetic can be done independently in each component.Practically: to compute modulo a large composite whose factorisation you know, work separately modulo each small factor and recombine. RSA implementations use this to make decryption roughly four times faster by working mod p and mod q instead of mod pq.
Deciding whether a number is prime, without factoring it.
| Method | Cost | Verdict |
|---|---|---|
| Trial division | O(√n) = O(2β/2) | Exponential in bit length |
| Pseudoprime test (Fermat) | O(β³) | Fooled by Carmichael numbers |
| Miller-Rabin | O(sβ³) | Randomized, error ≤ 2-s. What everyone uses. |
| AKS (2002) | Polynomial | Deterministic, but too slow in practice |
The pseudoprime test applies Fermat’s little theorem: if an-1 ≢ 1 (mod n) then n is definitely composite. The converse fails — a composite passing the test is a base-a pseudoprime, and Carmichael numbers such as 561 pass for every base coprime to them.
n - 1 = 2ᵤu with u odd. While computing an-1 by repeated squaring, watch for a non-trivial square root of 1 — a value x with x² ≡ 1 (mod n) but x ≢ ±1. Modulo a prime only ±1 square to 1, so finding another proves n composite. This catches Carmichael numbers, which the plain Fermat test cannot.Error probability of MILLER-RABIN with s random bases: ≤ 2-s
With s = 50, that is below 1 in 10¹⁵ — far less likely than a
hardware failure during the computation.This is Chapter 1’s point about useful incorrect algorithms, made concrete: Miller-Rabin can be wrong, the error is bounded and drivable to nothing, and it is what generates the keys protecting internet traffic.
Public-key cryptography solves a problem that looks impossible: communicating securely with someone you have never met and share no secret with.
RSA key generation
1. Choose two large random primes p and q (Miller-Rabin).
2. n = p · q
3. φ(n) = (p-1)(q-1)
4. Choose small odd e with gcd(e, φ(n)) = 1 ← public exponent
5. d = e⁻¹ mod φ(n) via EXTENDED-EUCLID ← private exponent
Public key: P = (e, n) Secret key: S = (d, n)Encrypt: P(M) = Mᵉ mod n
Decrypt: S(C) = Cᵈ mod n
Correctness: Med ≡ M (mod n), because ed ≡ 1 (mod φ(n))
and Euler's theorem.n into p and q can compute φ(n) and then d, breaking the system. Nobody knows an efficient factoring algorithm — but nobody has proved one does not exist. RSA is not proven secure; it is unbroken. And Shor’s algorithm factors in polynomial time on a quantum computer, which is why post-quantum cryptography is an active field.The chapter closes with Pollard’s rho heuristic, which finds a factor p of n in expected O(∜n) arithmetic operations, or O(√p) — good for small factors, hopeless for the balanced semiprimes RSA uses.
It works by iterating x ← x² - 1 mod n and looking for a repetition modulo an unknown factor, detected by computing gcd(xᵢ - xⱼ, n). By the birthday paradox from Chapter 5, a collision modulo p appears after about √p steps — the same square-root threshold as hash collisions, used here deliberately.
n-bit number in roughly exp(O(n1/3 lg2/3 n)) — sub-exponential but super-polynomial. RSA-768 (232 digits) fell in 2009; 2048-bit keys are considered safe against classical attack for the foreseeable future. The asymmetry between easy primality testing and hard factoring is the entire foundation, and it is empirical rather than proven.O(√n) trial division is exponential in the bit length. Efficiency here means polynomial in lg n.gcd(a,b) = gcd(b, a mod b), O(lg b) calls, worst case at consecutive Fibonacci numbers.d = ax + by, and therefore modular inverses whenever gcd(a,n) = 1.ap-1 ≡ 1 (mod p). Euler: aφ(n) ≡ 1 (mod n). Exponents reduce modulo the group order.O(β) multiplications, reducing mod n at every step.≤ 2-s. It beats the plain Fermat test by detecting non-trivial square roots of 1, which is what catches Carmichael numbers.d, repeated squaring for encryption, CRT for speed, Euler for correctness.p in O(√p) via the birthday paradox; the number field sieve is sub-exponential; Shor’s algorithm is polynomial on a quantum computer.Chapter 32 covers string matching: finding a pattern inside a text. The naive method is O((n-m+1)m), and three better algorithms — Rabin-Karp, finite automata, and Knuth-Morris-Pratt — each reach O(n + m) by never re-examining a character they have already ruled out.