Miller-Rabin Primality Test

Purpose: Decide whether $n$ is prime in $O(k{\log }^{3}n)$ (or $O(k{\log }^{2}n)$ with fast multiplication), where $k$ is the number of bases tested. With a fixed set of bases it is deterministic for all 64-bit $n$.

Algorithm

1. Handle small cases: $n<2$ composite; $n\in \{2,3\}$ prime; $n$ even composite.
2. Write $n-1=d\cdot 2^s$ with $d$ odd.
3. For each base $a$:
   • Compute $x=a^d\mathrm{mod}n$. If $x=1$ or $x=n-1$, this base gives no evidence — continue to the next base.
   • Repeat $s-1$ times: $x\leftarrow x^2\mathrm{mod}n$. If $x=n-1$, break out and continue to the next base.
   • If the loop finishes without ever hitting $n-1$, then $n$ is composite — stop.
4. If every base passes, report probably prime (certainly prime for the fixed base sets below).

Code

using u64 = unsigned long long;
using u128 = __uint128_t;
 
u64 mulmod(u64 a, u64 b, u64 m) { return (u128)a * b % m; }
 
u64 powmod(u64 a, u64 e, u64 m) {
    u64 r = 1; a %= m;
    while (e) { if (e & 1) r = mulmod(r, a, m); a = mulmod(a, a, m); e >>= 1; }
    return r;
}
 
bool witness(u64 a, u64 d, u64 n, int s) {
    u64 x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return false;      // not a witness
    for (int i = 1; i < s; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return false;
    }
    return true;                                  // a proves n composite
}
 
bool isPrime(u64 n) {
    if (n < 2) return false;
    for (u64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
        if (n % p == 0) return n == p;
    u64 d = n - 1; int s = 0;
    while ((d & 1) == 0) { d >>= 1; s++; }
    for (u64 a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
        if (witness(a, d, n, s)) return false;
    return true;
}

Deterministic base sets

• $n<3,215,031,751$: bases $\{2,3,5,7\}$
• $n<3.4\cdot 10^{14}$: bases $\{2,3,5,7,11,13,17\}$
• all 64-bit $n$: the first twelve primes $\{2,\dots ,37\}$
• all 64-bit $n$ (fewer bases): $\{2,325,9375,28178,450775,9780504,1795265022\}$

Paradigm

Randomized (Monte Carlo), made deterministic. Each base is an independent one-sided test: it can prove compositeness but never proves primality.

Complexity

• Time: $O(k{\log }^{3}n)$ with schoolbook modmul; each base costs one modpow plus $s$ squarings
• Space: $O(1)$

Why It Works

If $n$ is an odd prime, ${\mathbb{Z}}_n^{\ast }$ is a field, so $x^2=1$ has only the roots $x=\pm 1$. Writing $a^{n-1}=(a^d{)}^{2^s}$ and applying Fermat’s little theorem, the sequence $a^d,a^{2d},\dots ,a^{2^{s}d}$ must end at $1$, and the step before the first $1$ must be $-1$. If the algorithm sees a value that jumps to $1$ without passing through $n-1$, it has found a non-trivial square root of 1, which is impossible modulo a prime. Hence $n$ is composite.

For composite $n$, at least $3/4$ of the bases in $[2,n-2]$ are witnesses (Rabin), so $k$ random bases err with probability $\le 4^{-k}$. The fixed base sets above were found by exhaustive verification against the known pseudoprime tables.

Fermat's test is not enough

The plain Fermat test $a^{n-1}\equiv 1$ is fooled by Carmichael numbers (561, 1105, 1729, …) for every coprime base. Miller-Rabin’s square-root check is exactly what fixes this.

Variants / Use Cases

• Pollard’s Rho — pair with Miller-Rabin to factor 64-bit integers fast
• Baillie-PSW — one Miller-Rabin base 2 test plus a Lucas test; no known counterexample
• AKS — deterministic polynomial time without unproven hypotheses, but far slower in practice
• Lucas-Lehmer — specialised, much faster, for Mersenne numbers
• Generating random primes — test random odd candidates until one passes
• Montgomery reduction — speeds up the inner modmul by 2-3× when $n$ is fixed