Miller–Rabin Primality Test (C++ – Template)

A header-only, C++20 implementation of the Miller–Rabin probabilistic primality test.
It automatically chooses deterministic sets of bases for 32‑bit and 64‑bit integers, making it both blazing fast and reliable for all numbers up to $2^{64}$.

Features

• Templated – works with any unsigned integer type (uint32_t, uint64_t, unsigned __int128, Boost multiprecision, etc.)
• Deterministic for small integers
  • $\leqslant 2^{32}$: bases ${2, 7, 61}$
  • $\leqslant 2^{64}$: bases ${2, 325, 9375, 28178, 450775, 9780504, 1795265022}$
• Probabilistic fallback for larger arbitrary‑precision numbers (error $\leqslant 4^{-k}$)
• Overflow‑safe modular multiplication (uses __int128 when available, otherwise binary method)
• Header‑only – just drop the file into your project
• C++20 – requires std::unsigned_integral concept (easily back‑portable to C++17)

How It Works

1. Factor odd $n-1$ as $d\times 2^s$ with $d$ odd.
2. For a chosen base $a$, compute $x \equiv a^d \pmod{n}$.
3. If $x \equiv 1 \pmod{n}$ or $x \equiv -1 \pmod{n}$, the number passes for this base.
4. Otherwise, repeatedly square $x$ ($x \equiv x^2 \pmod{n}$).
   If $x \equiv -1 \pmod{n}$ appears at some step $\to$ probable prime.
   If no such value appears $\to$ composite (definitively).
5. Repeat with multiple bases to drive the error probability arbitrarily low.

Usage

#include "miller-rabin.h"
#include <iostream>

int main() {
    std::cout << std::boolalpha;

    // Small numbers – fully deterministic
    std::cout << "13 prime? " << is_prime(13u) << '\n';
    std::cout << "10007 prime? " << is_prime(10007ull) << '\n';

    // 64‑bit numbers – still deterministic and instant
    uint64_t big = 1234567890123456789ull;
    std::cout << big << " prime? " << is_prime(big) << '\n';

    // For wider types (e.g., __int128 or Boost) you can specify the number
    // of random bases (default 20)
    unsigned __int128 huge = (unsigned __int128)1 << 100;
    std::cout << "2^100 + 277 prime? "
              << is_prime(huge + 277, 30) << '\n';

    return 0;
}

Compilation

Any C++20 compiler will work:

g++ -std=c++20 -O2 example.cpp -o example

Deterministic Base Sets

Max n size	Bases	Reference
32‑bit	${2, 7, 61}$	Jaeschke $1993$
64‑bit	${2, 325, 9375, 28178, 450775, 9780504, 1795265022}$	Jim Sinclair, $2011$ (proved by Jan Feitsma)

Using these bases guarantees a correct answer with no false positives for all numbers in the range.

API

template <std::unsigned_integral T>
bool is_prime(T n, unsigned k = 20);

• $n$ – the integer to test (must be unsigned; concept std::unsigned_integral)
• $k$ – number of random bases to try (only used for types wider than 64‑bit; ignored for built‑in 32/64‑bit types)
• Returns true if $n$ is (probably) prime, false if definitely composite.

Extending to Big‑Integer Libraries

To use the template with types like boost::multiprecision::cpp_int:

#include <boost/multiprecision/cpp_int.hpp>
using big_int = boost::multiprecision::cpp_int;

// Provide own mul_mod to avoid overflow (or rely on the portable version)
// The test method itself works unchanged.
std::cout << is_prime(big_int("1234567890123456789"), 25) << '\n';

License

This project is provided under the MIT License. See the full license text in the source file.