Miller–Rabin 素性测试

Miller–Rabin 素性测试（Miller–Rabin primality test）是进阶的素数判定方法。它是由 Miller 和 Rabin 二人根据费马小定理的逆定理（费马测试）优化得到的。因为和许多类似算法一样，它是使用伪素数的概率性测试，我们必须使用慢得多的确定性算法来保证素性。然而，实际上没有已知的数字通过了高级概率性测试（例如 Miller–Rabin）但实际上却是复合的。因此我们可以放心使用。

在不考虑乘法的复杂度时，对数 进行 轮测试的时间复杂度是 。Miller-Rabbin 素性测试常用于对高精度数进行测试，此时时间复杂度是 ，利用 FFT 等技术可以优化到 。

二次探测定理

如果 是奇素数，则 的解为 或者 。

要证明该定理，只需将上面的方程移项，再使用平方差公式，得到 ，即可得出上面的结论。

实现

根据卡迈克尔数的性质，可知其一定不是 。

不妨将费马小定理和二次探测定理结合起来使用：

将 中的指数 分解为 ，在每轮测试中对随机出来的 先求出 ，之后对这个值执行最多 次平方操作，若发现非平凡平方根时即可判断出其不是素数，否则再使用 Fermat 素性测试判断。

还有一些实现上的小细节：

• 对于一轮测试，如果某一时刻 ，则之后的平方操作全都会得到 ，则可以直接通过本轮测试。
• 如果找出了一个非平凡平方根 ，则之后的平方操作全都会得到 。可以选择直接返回 false，也可以放到 次平方操作后再返回 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）成立，则对数 最多只需要测试 中的全部整数即可 确定 数 的素性。

而在 OI 范围内，通常都是对 范围内的数进行素性检验。对于 范围内的数，选取 三个数作为基底进行 Miller–Rabin 素性检验就可以确定素性；对于 范围内的数，选取 七个数作为基底进行 Miller–Rabin 素性检验就可以确定素性。

也可以选取 （即前 个素数）检验 范围内的素数。

注意如果要使用上面的数列中的数 作为基底判断 的素性：

• 所有的数都要取一遍，不能只选小于 的；
• 把 换成 ；
• 如果 ，则直接通过该轮测试。

模板题：loj143