米勒拉宾算法

原理

目标：检测某个较大的正整数 (n) 是否为质数。

证明：

若 (n leq 2) 则直接给出结果。否则，若 (n) 为偶数，也直接给出结果。

否则，假设 (n) 为奇质数，显然 (n-1) 为偶数，可以写成 (2^sd) 的形式，其中 (s) 是正整数，而 (d) 是奇数。则对于任意 (a) 和 (0leq rleq s-1) ，必定满足以下两种形式的一种：

(a^dequiv 1 pmod{n}) 或 (a^{2^rd}equiv -1 pmod{n}) 。

因为，由于费马小定理，对一个质数 (n) ，有 (a^{n-1}equiv 1 pmod{n})

代码

namespace MillerRabin {

    const int ptop = 13;
    const ll p[ptop] = {
        1, 2, 3, 5, 7, 11, 13, 17,
        19, 61, 2333, 4567, 24251
    };

    ll qmul(ll a, ll b, ll p) {
        ll res = 0LL;
        while(b) {
            if(b & 1LL) {
                res += a;
                if(res >= p)
                    res -= p;
            }
            a += a;
            if(a >= p)
                a -= p;
            b >>= 1;
        }
        return res;
    }

    ll qpow(ll x, ll n, ll p) {
        ll res = 1LL;
        while(n) {
            if(n & 1LL)
                res = qmul(res, x, p);
            x = qmul(x, x, p);
            n >>= 1;
        }
        return res;
    }

    bool check(ll x, ll p) {
        if(x % p == 0LL)
            return true;
        if(p >= x)
            p %= x;
        if(qpow(p, x - 1LL, x) != 1LL)
            return true;
        ll t, k = x - 1LL;
        while(k % 2LL == 0LL) {
            t = qpow(p, k >>= 1, x);
            if(t != 1LL && t != x - 1LL)
                return true;
            if(t == x - 1LL)
                return false;
        }
        return false;
    }

    bool MillerRabin(ll x) {
        if(x <= 1)
            return false;
        for(int i = 1; i <= ptop; ++i) {
            if(x == p[i])
                return true;
            if(check(x, p[i]))
                return false;
        }
        return true;
    }

}

using namespace MillerRabin;

check函数的意图是用质数p作为基检查x是否为质数。

首先排除掉相等的情况，然后排除掉x已经有p作为质数的情况。然后后续p只会出现在快速幂中，所以先进行一次取模。先用费马小定理确定x不是质数。

选取特定的整数可以在一定范围内确定（而非单纯基于概率猜测）某个整数是素数还是合数。对于小于 (2^{32}) 的情形，选取 (2,7,61) 共三个凭据可以做到这一点；对于小于 (2^{64}) 的情形，选取 (2,325,9375,28178,450775,9780504,1795265022) 共七个凭据可以做到这一点。

【数学】米勒拉宾算法

原文：https://www.cnblogs.com/purinliang/p/13676459.html