【数学】米勒拉宾算法

原理

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

证明：

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

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

\(a^d\equiv 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