Miller-Rabin for 64-Bit Integers

Intuition, Vocabulary and Foundations

Miller–Rabin tests whether an odd integer behaves like a prime under carefully chosen modular exponentiations. Think of each base as an independent checkpoint: a composite may imitate a prime at one checkpoint, but a suitable witness exposes the imitation.

For an odd candidate $n\gt2$, factor all powers of two from $n-1$ to obtain $n-1=2^s d$ with $d$ odd. For a base $a$, compute $x_0\equiv a^d\pmod n$ and repeatedly square, obtaining $x_r\equiv a^{2^r d}\pmod n$.

If $n$ is prime and $a\not\equiv0\pmod n$, Fermat’s theorem gives $a^{n-1}\equiv1\pmod n$. In a prime field, the only square roots of $1$ are $1$ and $-1$. A prime must therefore begin with $x_0=1$, begin with $x_0=-1$, or reach $-1$ before the final square reaches $1$.

A composite that violates this pattern is exposed by base $a$, called a witness. A composite that passes is a strong probable prime to that base. Passing arbitrary bases is usually probabilistic evidence; for unsigned 64-bit inputs, a proven finite base set covers the whole domain and makes the algorithm deterministic.

Step-by-Step Derivations and Algorithms

Reject values below $2$, accept small known primes, and reject even values. Trial division by a short list of small primes removes many composites and prevents a small prime from being rejected as divisible by itself.

For the remaining odd candidate, decompose $n-1=2^s d$. For each deterministic base, reduce it modulo $n$. If the result is zero, continue because that base supplies no contrary information.

Compute $x=a^d\bmod n$. If $x=1$ or $x=n-1$, the base passes. Otherwise square at most $s-1$ times. Reaching $n-1$ passes; reaching $1$ first exposes a nontrivial square root of $1$; and ending without $n-1$ makes the base a witness.

For a prime, the final chain value is $a^{2^s d}=a^{n-1}\equiv1\pmod n$. Moving backward, the preceding value must be a square root of $1$. If the chain did not start at $1$, its first transition into $1$ must come from $-1$. Failure to exhibit that pattern contradicts primality.

flowchart TD
    A["Receive unsigned 64-bit n"] --> B{"n below 4?"}
    B -->|Yes| C["Return whether n is 2 or 3"]
    B -->|No| D{"Even or small-prime divisible?"}
    D -->|Yes| E["Return composite unless equal to divisor"]
    D -->|No| F["Write n minus 1 as 2^s times d"]
    F --> G["Select next deterministic base"]
    G --> H["Compute x = a^d mod n"]
    H --> I{"x is 1 or n minus 1?"}
    I -->|Yes| J{"More bases?"}
    I -->|No| K["Repeatedly square x"]
    K --> L{"Reached n minus 1?"}
    L -->|Yes| J
    L -->|No and chain ended| M["Return composite"]
    J -->|Yes| G
    J -->|No| N["Return prime"]

Implementation, Complexity and Engineering

Python’s arbitrary-precision integers make multiplication safe, and three-argument pow performs modular exponentiation efficiently. In C or C++, an unsigned 128-bit intermediate is usual when available. Portable alternatives include add-and-double multiplication, Barrett reduction, or Montgomery reduction; wrapped 64-bit multiplication is invalid.

The implementation enforces the unsigned 64-bit domain, handles tiny and even values before decomposition, filters small primes, and uses the deterministic seven-base set. A trace helper exposes one witness chain for teaching and debugging.

from math import isqrt


UINT64_MAX = (1 << 64) - 1
DETERMINISTIC_BASES_64 = (
    2, 325, 9_375, 28_178, 450_775, 9_780_504, 1_795_265_022,
)
SMALL_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)


def decompose_minus_one(n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d //= 2
    return s, d


def witness_trace(n, base):
    if n <= 2 or n % 2 == 0:
        raise ValueError("trace requires an odd n greater than 2")
    s, d = decompose_minus_one(n)
    chain = [pow(base % n, d, n)]
    for _ in range(s - 1):
        chain.append(chain[-1] * chain[-1] % n)
    return s, d, chain


def passes_strong_test(n, base, s, d):
    base %= n
    if base == 0:
        return True
    value = pow(base, d, n)
    if value == 1 or value == n - 1:
        return True
    for _ in range(s - 1):
        value = value * value % n
        if value == n - 1:
            return True
        if value == 1:
            return False
    return False


def is_prime_u64(n):
    if not isinstance(n, int):
        raise TypeError("n must be an integer")
    if not 0 <= n <= UINT64_MAX:
        raise ValueError("n must be an unsigned 64-bit integer")
    if n < 2:
        return False
    for prime in SMALL_PRIMES:
        if n == prime:
            return True
        if n % prime == 0:
            return False
    s, d = decompose_minus_one(n)
    return all(
        passes_strong_test(n, base, s, d)
        for base in DETERMINISTIC_BASES_64
    )


def trial_is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for divisor in range(3, isqrt(n) + 1, 2):
        if n % divisor == 0:
            return False
    return True


assert [n for n in range(20) if is_prime_u64(n)] == [
    2, 3, 5, 7, 11, 13, 17, 19
]

for n in range(100_000):
    assert is_prime_u64(n) == trial_is_prime(n)

s, d, chain = witness_trace(2047, 2)
assert (s, d) == (1, 1023)
assert chain == [1]
assert passes_strong_test(2047, 2, s, d)

s, d = decompose_minus_one(2047)
assert not passes_strong_test(2047, 3, s, d)
assert not is_prime_u64(2047)

assert not is_prime_u64(3_215_031_751)
assert not is_prime_u64(341_550_071_728_321)
assert not is_prime_u64(3_825_123_056_546_413_051)
assert is_prime_u64(18_446_744_073_709_551_557)
assert not is_prime_u64(UINT64_MAX)

try:
    is_prime_u64(-1)
    raise AssertionError("negative input was accepted")
except ValueError:
    pass

try:
    is_prime_u64(1 << 64)
    raise AssertionError("out-of-range input was accepted")
except ValueError:
    pass

print("all tests passed")

Applications, Case Studies and Exercises

A primality checker is often a gate inside factorization, key generation, hash-table sizing, or arithmetic software. Its production quality depends as much on domain enforcement and modular multiplication as on the witness rule.