Miller-Rabin 算法
NEKO_Daze
·
·
算法·理论
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理论基础
费马小定理
#### 二次探测定理
若 $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