用于快速判断一个大数是不是素数。时间复杂度\(O(k\log^3(n))\)，\(k\)为测试轮数。如果底数随机，一般取\(k=8\)。

一个很好的博客：素数与素性测试

inline ll qpow(__int128 a, __int128 b, ll m) {
    __int128 res = 1;
    while(b) {
        if(b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b = b >> 1;
    }
    return res;
}

namespace miller_rabin {
    // 2, 7, 61 适用 4e9
    // 2, 3, 5, 7, 11, 13, 17 适用 3e14
    // 2, 3, 7, 61, 24251 适合 1e16 特判 46856248255981
    int primelist[5] = {2, 3, 7, 61, 24251};
    bool ispriem(ll n) {
        if(n < 3 || n % 2 == 0) return n == 2;
        if(n == 46856248255981) return false;
        ll a = n - 1, b = 0;
        while(a % 2 == 0) a /= 2, b++;
        for(int i = 1; i < 5; i++) {
            ll p = primelist[i], v = qpow(p, a, n);
            if(v == 1) continue;
            int j;
            for(j = 0; j < b; j++) {
                if(v == n - 1) break;
                v = (__int128)v * v % n;
            }
            if(j >= b) return false;
        } 
        return true;
    }
}

Miller-Rabin 素性测试