決定的Miller-Rabin法による素数判定（C++）

概要

$0\leq N<2^{64}$ を満たす整数 $N$ に対し， $N$ が素数ならtrueを，さもなくばfalseを返す関数です．時間計算量は $O\left(\log N\right)$ です（計算量は厳密には微妙）．

bool miller_rabin_64(unsigned long long n){
    if(n == 2) return true;
    if(n == 1 || n % 2 == 0) return false;
    int s = 0;
    unsigned long long d = n - 1;
    while(d % 2 == 0) s++, d >>= 1;
    unsigned long long as[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for(auto a: as){
        if(a >= n) break;
        __uint128_t x = 1, y = a;
        unsigned long long d_ = d;
        while(d_){
            if(d_ & 1) x *= y, x %= n;
            y *= y, y %= n;
            d_ >>= 1;
        }
        if(x == 1) continue;
        int r = 0;
        for(; r < s; r++){
            if(x + 1 == n) break;
            x *= x, x %= n;
        }
        if(r == s) return false;
    }
    return true;
}

Verify

Library Checker – Primality Test Submission