THE GARDEN

Miller-Rabin Primality Test

Updated 13 Sep 2026

• •

  What it is

  • •

    A probabilistic primality test — the practical, industry-standard way essentially every cryptography library decides "is this number prime?" — built on a stronger version of Fermat's little theorem. Write $n-1 = 2^r d$ with $d$ odd. For a candidate "witness" base $a$, compute $x_0 = a^d \bmod n$; if $x_0 \ne 1$, repeatedly square it up to $r-1$ times looking for it to hit $n-1$. If neither $x_0=1$ nor any squared value equals $n-1$, $a$ is a definitive witness that $n$ is composite. Crucially, this catches numbers that fool the plain Fermat test entirely — Carmichael numbers like 561 pass Fermat's test ($a^{n-1}\equiv 1$) for the overwhelming majority of bases, but Miller-Rabin's stronger structural check (looking for a non-trivial square root of unity along the way, not just the final result) exposes most of them as composite anyway. No single witness base can be trusted 100% of the time (a "strong liar" base exists for every composite), but at most 1/4 of all bases can be strong liars for any given composite — so testing a handful of random bases drives the false-positive rate down to effectively zero for practical purposes.

• •

  When to apply

  • •

    Whenever you need to determine (or exploit an implementation's method of determining) whether a large number is prime — and specifically whenever a challenge's primality check tests against a small, fixed, disclosed set of bases rather than random ones, since that's a very different (and much weaker) trust model.

• •

  Symbols and assumptions

  • •

    $n>2$ is an odd candidate; write $n-1=2^s d$ with odd $d$. A tested base $a$ satisfies $1<a<n-1$. Passing a base means probable prime for that test, not a proof of primality.

• •

  Math — step by step

  • •
    1. If $\gcd(a,n)>1$, a factor is already found. Otherwise compute $x=a^d\bmod n$. Accept this base if $x=1$ or $x=n-1$.
  • •
    2. Otherwise square at most $s-1$ times, accepting if any result is $n-1$. If none is, reject $n$ as composite.
  • •
    3. Why this is valid for primes: Fermat forces the squaring chain to end at 1, and the only square roots of 1 in a field are ±1. A chain that reaches 1 without a preceding −1 exposes composite behavior.
  • •
    4. For an odd composite, at most one quarter of admissible bases are strong liars. The $4^{-k}$ bound requires independent suitably random bases; fixed adversarially known bases are a different assumption.
• •

  Worked example

  • •

    Test $n=21$ with $a=2$. Since $20=2^2\cdot5$, start at $2^5\bmod21=11$; this is neither 1 nor 20.

  • •

    Square once: $11^2\bmod21=16$, still not 20. There are no more allowed squarings, so base 2 proves 21 composite.

  • •

    Compare prime $n=13$: $12=2^2\cdot3$, $2^3=8$, then $8^2\bmod13=12=-1$. This base passes.

• •

  Python

  • •

    def miller_rabin_round(n, a):
            d, r = n - 1, 0
            while d % 2 == 0:
                d //= 2; r += 1
            x = pow(a, d, n)
            if x == 1 or x == n - 1:
                return True   # probably prime, relative to this witness
            for _ in range(r - 1):
                x = pow(x, 2, n)
                if x == n - 1:
                    return True
            return False       # definitely composite; a is a witness
    

• •

  SageMath

  • •

    is_prime(n) already runs a robust primality test internally — no need to hand-roll Miller-Rabin unless specifically simulating or defeating a particular implementation's fixed-basis check:

  • •

    is_prime(n)
    

• •

  Related

  • •

    Fooling Fixed-Basis Miller-Rabin (Arnault Strong Pseudoprimes)

  • •

    RSA Factorization from Known (N, e, d)

  • •

    Roots of Unity mod N (Non-Trivial Roots Reveal Factors)

• •

  Cards

  • •

    What's the key structural check Miller-Rabin adds beyond the plain Fermat test?

    • •

      It examines the sequence of values while repeatedly squaring a^d, looking for a non-trivial square root of unity (not just checking the final result equals 1) — catching many Carmichael-number-style Fermat liars.

  • •

    What fraction of bases can be "strong liars" for any given composite number, at most?

    • •

      At most 1/4 — which is why testing several random bases drives the overall false-positive probability down exponentially.

◌ Explore connections in Graph view