Primality Tests

Every TLS certificate holds an RSA or ECDSA key built from random primes. Chrome verifies a 617-digit number before trusting a server. Behind that verification: Miller-Rabin-40 rounds, each a single pow() call-completing in microseconds. How does it guarantee no composite slips through? That's exactly what this lesson answers.

• **OpenSSL RSA:** BN_generate_prime_ex() sieves with small primes, then runs Miller-Rabin 64 rounds; a 2048-bit key takes ~100 ms
• **Python sympy.isprime:** deterministic for n < 3.3·10²⁴ (fixed bases), probabilistic (Miller-Rabin) for larger numbers
• **Java BigInteger.isProbablePrime(k):** k Miller-Rabin rounds; used internally whenever Java generates HTTPS keys

Предварительные знания

• Distribution of Prime Numbers

Trial Division and the Fermat Test

Primality testing is one of the most practically important problems in cryptography. Naive trial division-checking all primes up to √n-runs in O(√n), which is completely infeasible for 1024-bit numbers. The Fermat test speeds things up dramatically but has a fatal flaw.

**Trial division:** check divisibility by all p ≤ √n. - Complexity: O(√n). For a 512-bit n, that's 2²⁵⁶ operations. Hopeless. **Fermat test:** if aⁿ⁻¹ ≢ 1 (mod n) for some a-n is definitely composite. - If aⁿ⁻¹ ≡ 1 for many a-n is 'probably prime' - Complexity: O(log² n)-fast - Fatal flaw: Carmichael numbers pass for ALL a with gcd(a, n) = 1

561 = 3 × 11 × 17 is the smallest Carmichael number. For every a coprime to 561, aⁿ⁻¹ ≡ 1 (mod 561). Never use the Fermat test alone in cryptographic code-it will accept Carmichael numbers as prime.

The Miller-Rabin Test

Miller-Rabin is the gold standard for primality testing in cryptography. It eliminates the Carmichael vulnerability by adding an extra condition: the only square roots of 1 modulo a prime are ±1.

**Miller-Rabin idea:** if n is prime and n−1 = 2ˢ·d, then for any base a: 1. a^d ≡ 1 (mod n), OR 2. a^(2ʲ·d) ≡ −1 (mod n) for some j ∈ {0,...,s−1} If neither holds-n is composite and a is a 'witness'. **Probabilistic:** for a random base, error probability ≤ 1/4 per round. After k rounds: ≤ 4⁻ᵏ. **Deterministic:** for n < 3.3·10²⁴, testing only a ∈ {2,3,5,7,11,13,17,19,23,29,31,37} is sufficient.

AKS and Deterministic Tests

Until 2002 no polynomial-time deterministic primality algorithm was known. The AKS algorithm (Agrawal-Kayal-Saxena) settled this theoretical question-but it is far slower than Miller-Rabin in practice.

**AKS theorem (2002):** PRIMES ∈ P-primality is decidable in polynomial time. Criterion: n is prime iff (X + a)ⁿ ≡ Xⁿ + a (mod Xʳ − 1, n) for suitable r and all a ≤ √φ(r)·log n. **Complexity:** O(log^{7.5}(n))-polynomial, but slow in practice. **Lucas primality test:** n is prime iff there exists a such that: - aⁿ⁻¹ ≡ 1 (mod n), AND - a^{(n-1)/q} ≢ 1 (mod n) for every prime q dividing n−1. Requires knowing the factorization of n−1. **In practice:** - Miller-Rabin with 40 rounds: sufficient for RSA - OpenSSL, Python, Java: all use Miller-Rabin - AKS: theoretically important, practically too slow

How TLS key generation actually works: OpenSSL calls BN_generate_prime_ex(), which generates random odd numbers, quickly sieves with small primes up to 2000 (eliminating ~80% of composites cheaply), then applies Miller-Rabin with 64 rounds. A 2048-bit key takes about 100 ms on a modern CPU.

Key Ideas

• **Trial division:** O(√n)-infeasible for 512+ bits; Fermat test is fast but fails on Carmichael numbers
• **Miller-Rabin:** O(k·log³ n); error ≤ 4⁻ᵏ per run; deterministic for n < 3.3·10²⁴ with 12 fixed bases
• **AKS (2002):** proved PRIMES ∈ P; theoretically polynomial but slower than Miller-Rabin in practice by orders of magnitude
• **Production:** OpenSSL, Python, Java use Miller-Rabin with 20-64 rounds for all prime generation

Related Topics

Primality tests draw on the full preceding theory:

• Fermat's and Euler's Theorems — Miller-Rabin is a strengthened Fermat test that also checks square roots of 1
• Distribution of Primes — PNT determines how many candidates to expect when generating RSA primes
• Number Theory in Cryptography — Prime generation in OpenSSL is the direct application of everything

Вопросы для размышления

• Carmichael numbers bypass the Fermat test for all coprime bases. Why does Miller-Rabin's square-root check catch them?
• AKS proves PRIMES ∈ P. Does that imply integer factorization is also polynomial-time? Why or why not?
• If a quantum computer runs Shor's algorithm, how does that affect the search for large primes-and does Miller-Rabin remain useful?

Связанные уроки

• prob-05-independence