Miller–Rabin 素性测试（Miller–Rabin primality test）是进阶的素数判定方法。它是由 Miller 和 Rabin 二人根据费马小定理的逆定理（费马测试）优化得到的。因为和许多类似算法一样，它是使用伪素数的概率性测试，我们必须使用慢得多的确定性算法来保证素性。然而，实际上没有已知的数字通过了高级概率性测试（例如 Miller–Rabin）但实际上却是复合的。因此我们可以放心使用。
在不考虑乘法的复杂度时，对数 \(n\) 进行 \(k\) 轮测试的时间复杂度是 \(O(k \log n)\)。Miller-Rabbin 素性测试常用于对高精度数进行测试，此时时间复杂度是 \(O(k \log^3n)\)，利用 FFT 等技术可以优化到 \(O(k \log^2n \log \log n \log \log \log n)\)。
二次探测定理
如果 \(p\) 是奇素数，则 \(x^2 \equiv 1 \pmod p\) 的解为 \(x \equiv 1 \pmod p\) 或者 \(x \equiv p - 1 \pmod p\)。
要证明该定理，只需将上面的方程移项，再使用平方差公式，得到 \((x+1)(x-1) \equiv 0 \bmod p\)，即可得出上面的结论。
实现
根据卡迈克尔数的性质，可知其一定不是 \(p^e\)。
不妨将费马小定理和二次探测定理结合起来使用：
将 \(a^{n-1} \equiv 1 \pmod n\) 中的指数 \(n−1\) 分解为 \(n−1=u \times 2^t\)，在每轮测试中对随机出来的 \(a\) 先求出 \(v = a^{u} \bmod n\)，之后对这个值执行最多 \(t\) 次平方操作，若发现非平凡平方根时即可判断出其不是素数，否则再使用 Fermat 素性测试判断。
还有一些实现上的小细节：
- 对于一轮测试，如果某一时刻 \(a^{u \times 2^s} \equiv n-1 \pmod n\)，则之后的平方操作全都会得到 \(1\)，则可以直接通过本轮测试。
- 如果找出了一个非平凡平方根 \(a^{u \times 2^s} \not\equiv n-1 \pmod n\)，则之后的平方操作全都会得到 \(1\)。可以选择直接返回
false，也可以放到 \(t\) 次平方操作后再返回false。
这样得到了较正确的 Miller Rabin。
代码：
bool MillerRabin(int n) {
if (n == 2) return true;
if (n <= 1 || n % 2 == 0) return false;
ll base[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
ll u = n - 1, k = 0;
while (u % 2 == 0) u /= 2, k++;
for (auto x : base) {
if (x % n == 0) continue;
ll v = powmod(x, u, n);
if (v == 1 || v == n - 1) continue;
for (int j = 1; j <= k; j++) {
ll last = v;
v = (__int128)v * v % n;
if (v == 1) {
if (last != n - 1) return false;
break;
}
}
if (v != 1) return false;
}
return true;
}
另外，假设 广义 Riemann 猜想（generalized Riemann hypothesis, GRH）成立，则对数 \(n\) 最多只需要测试 \([2, \min\{n-2, \lfloor 2\ln^2 n \rfloor\}]\) 中的全部整数即可 确定 数 \(n\) 的素性。
而在 OI 范围内，通常都是对 \([1, 2^{64})\) 范围内的数进行素性检验。对于 \([1, 2^{32})\) 范围内的数，选取 \(\{2, 7, 61\}\) 三个数作为基底进行 Miller–Rabin 素性检验就可以确定素性；对于 \([1, 2^{64})\) 范围内的数，选取 \(\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}\) 七个数作为基底进行 Miller–Rabin 素性检验就可以确定素性。
也可以选取 \(\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}\)（即前 \(12\) 个素数）检验 \([1, 2^{64})\) 范围内的素数。
注意如果要使用上面的数列中的数 \(a\) 作为基底判断 \(n\) 的素性：
- 所有的数都要取一遍，不能只选小于 \(n\) 的；
- 把 \(a\) 换成 \(a \bmod n\)；
- 如果 \(a \equiv 0 \pmod n\)，则直接通过该轮测试。
模板题：loj143
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
ll powmod(__int128 x, ll y, ll mod) {
ll res = 1;
while (y) {
if (y & 1) res = res * x % mod;
y >>= 1;
x = x * x % mod;
}
return res;
}
bool MillerRabin(ll n) {
if (n == 2) return true;
if (n <= 1 || n % 2 == 0) return false;
ll base[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
ll u = n - 1, k = 0;
while (u % 2 == 0) u /= 2, k++;
for (auto x : base) {
if (x % n == 0) continue;
ll v = powmod(x, u, n);
if (v == 1 || v == n - 1) continue;
for (int j = 1; j <= k; j++) {
ll last = v;
v = (__int128)v * v % n;
if (v == 1) {
if (last != n - 1) return false;
break;
}
}
if (v != 1) return false;
}
return true;
}
int main() {
ll n;
while (scanf("%lld", &n) != EOF) {
if (Mr(n))
printf("Y\n");
else
printf("N\n");
}
return 0;
}