25 Lines Deterministic Miller–Rabin Using The First 12 Primes

Revision en1, by Sangiiko, 2026-11-21 15:34:50
using u64 = uint64_t;
using u128 = __uint128_t;

u64 power(u64 a, u64 b, u64 m) {
    u64 res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (u128)res * a % m;
        a = (u128)a * a % m;
        b >>= 1;
    }
    return res;
}

bool isPrime(u64 n) {
    if (n < 2) return false;
    u64 d = n - 1;
    int s = 0;
    while (d % 2 == 0) d /= 2, s++;

    for (u64 a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n % a == 0) return n == a;
        u64 x = power(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool ok = false;
        for (int r = 1; r < s; r++) {
            x = (u128)x * x % n;
            if (x == n - 1) { ok = true; break; }
        }
        if (!ok) return false;
    }
    return true;
}
Tags number theory, primes, miller-rabin, c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Sangiiko 2026-11-21 15:34:50 865 Initial revision (published)