Miller-Rabin 算法

0.序文

在打比赛的时候碰到一道题，后面要求判断一个

5\times10^{11}

的数是否为质数，故寻找着一种能快速判断质数的方法，搜索中找到了 Miller-Rabin 算法，学习一番后成功 AC。

故有此文，作为学习笔记记录。欢迎指正。

1.何为 Miller-Rabin 算法

Miller-Rabin 算法，译称米勒-拉宾素性检验，一种利用随机化算法来较快判断一个数是否为质数的质数判定方法。

该算法由 Gary Lee Miller 首先提出，后由 Michael O. Rabin 修改，将其中应用到的还未被证明的广义黎曼猜想改用为随机化算法。

Miller-Rabin 算法的用途其一为判断工业质数（通常

\ge2^{1024}

的质数），因为它所使用的随机性算法，存在一定错误率，但在判断一般题目里

\le2^{63}-1

的素数时错误率极低，可以放心使用。

2.实现过程

2.1理论基础

费马小定理

\forall p

为质数，

gcd(a,p)=1

，则

a^{p-1}\equiv1\pmod p

。

二次探测定理

若

p

为质数，则

x^2\equiv1\pmod p

的解为

x_1=1,x2=p-1

。

这两种定理在证明质数时都有一定误判概率，而 Miller-Rabin 算法同时使用这两种方法判断质数，大大降低了误判率。

2.2算法过程

Miller-Rabin 算法的流程大体如下：

特判

读取需要判断的数 $n$ ，若 $n=2$ 就可以直接返回 true。

若 $n<2$ 或 $n$ 为偶数，直接返回 false。

计算

将 $n-1$ 分为 $2^k\times t$ ，且 $d$ 为奇数， $s\ge1$ ；

选取底数 $a\in(1,n)$ 。

由 $x\equiv a^d\pmod n$ 计算 $x$ 。

检验

若 $x\equiv1\pmod n$ ，更换底数进行多次测试（Miller-Rabin 算法一次的准确率大概在 $75\%$ 左右，因此要进行 $4$ 至 $8$ 次才能保障正确率）。

反之，对于 $r=1$ 至 $s-1$ ，计算 $x\equiv x^2\pmod n$ ，若某个 $r$ 时有 $x=n-1$ ，则 $n$ 仍需进行多次测试。

如果不存在这种 $r$ ，那么 $n$ 为合数。

3.编写代码

CPP

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool check(ll n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    vector<ll> example = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ll p : example)
        if (n % p == 0) return n == p;
    ll d = n - 1;int s = 0;
    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }
    vector<ll> NEKO = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ll a : NEKO) {
        if (a >= n) continue;
        __int128 x = 1,a_mod = a,mod = n;ll temp = d;
        x = 1; a_mod = a % mod;
        while (temp > 0)
        {
            if (temp % 2 == 1)
                x = (x * a_mod) % mod;
            a_mod = (a_mod * a_mod) % mod;
            temp /= 2;
        }
        if (x == 1 || x == mod - 1) continue;
        bool flag = true;
        for (int i = 0; i < s - 1; ++i)
        {
            x = (x * x) % mod;
            if (x == mod - 1)
            {
                flag = false;
                break;
            }
        }
        if (flag)
            return false;
    }
    return true;
}
int main()
{
    ll n;
    cin >> n;
    if (check(n)) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

参考文献：

https://blog.csdn.net/cookies_s_/article/details/144299600

https://www.cnblogs.com/S-A-I/p/17368139.html

https://baike.baidu.com/item/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E7%B4%A0%E6%80%A7%E6%A3%80%E9%AA%8C/22719763#3

https://blog.csdn.net/qq_43227036/article/details/100336234

文章操作