guest@cp-base:~/home/number-theory$
templates/miller-rabin.cpp
compilable
$cat templates/miller-rabin

Miller-Rabin Primality Test

Deterministic Miller-Rabin primality test for 64-bit integers using verified witness sets.

[Number Theory]|
Jul 9, 2026
|explanatory_notes.md|
#primality-test#miller-rabin#deterministic#number-theory
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll mulmod(ll a, ll b, ll m) { return (__int128)a * b % m; }

ll powmod(ll a, ll d, ll m) {
    ll res = 1; a %= m;
    while (d > 0) {
        if (d & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        d >>= 1;
    }
    return res;
}

bool millerRabin(ll n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1; int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (a >= n) continue;
        ll x = powmod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool comp = true;
        for (int r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if (x == n - 1) { comp = false; break; }
        }
        if (comp) return false;
    }
    return true;
}
35 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Miller-Rabin Primality Test

Deterministic primality test for all 64-bit integers.

How It Works

  • Factor n−1=d⋅2sn - 1 = d \cdot 2^s

  • For each witness base aa:

    • - Compute x=ad mod nx = a^d \bmod n
    - If x=1x = 1 or x=n−1x = n - 1, this base passes
    - Otherwise, square xx up to s−1s - 1 times looking for n−1n - 1
    - If n−1n - 1 is never found, nn is composite

    Deterministic Witnesses

    The 12-witness set {2,3,5,7,11,13,17,19,23,29,31,37}\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\} is proven sufficient for all n<264n < 2^{64} (Jim Sinclair, 2011).

    Smaller ranges need fewer witnesses:

  • n<2047n < 2047: just {2}\{2\}

  • n<3.2×1018n < 3.2 \times 10^{18}: first 7 primes

    • When to Use

  • Quick primality check for a single large number (up to 2642^{64})

  • Preprocessing step before Pollard's Rho factorization

  • Generating or verifying large primes

    • Complexity

  • Time — O(klog⁡2n)O(k \log^2 n) where k=12k = 12

  • Space — O(1)O(1)

    • Notes

  • Uses __int128 for overflow-safe modular multiplication

  • If you also need factorization, the Pollard's Rho template includes Miller-Rabin internally