Miller-Rabin Primality Test

Number Theory · Axiom Academy

LESSON Miller-Rabin Primality Test The industry-standard probabilistic primality test used in cryptography and computational number theory 1. Decomposing n - 1 = 2 s · d The first step of the Miller-Rabin test is to write n - 1 in the form 2 s · d, where d is odd. We repeatedly divide n - 1 by 2 until we get an odd number. For a number n to test, find the largest power s such that 2 s divides (n - 1), then set d = (n - 1) / 2 s . 2. The Miller-Rabin Test Sequence For a random witness a, we compute the sequence: a d , a 2d , a 4d , ..., a 2 s-1 d , a 2 s d (mod n). If n is prime, this sequence must satisfy specific properties based on Fermat's Little Theorem. Case 2: a 2 r d ≡ -1 (mod n) for some 0 ≤ r < s If neither case holds, n is definitely composite. The test exploits the fact that if n is prime and x² ≡ 1 (mod n), then x ≡ ±1 (mod n). By tracking the sequence of squarings, we can detect composite numbers. 3. Strong Pseudoprimes and Error Probability A composite number n that passes the Miller-Rabin test for a particular witness a is called a strong pseudoprime to base a. The key advantage over Fermat's test is that at most 1/4 of all possible witnesses will fool the test for any composite n. For any composite number n, at least 75% of witnesses will detect that n is composite. After k independent tests with random witnesses: 4. Comparison to Fermat's Primality Test

This is the written version of the interactive lesson above. See the full Number Theory course.