Miller Rabin

Miller Rabin 定理是一种素性测试方法，其中利用到了素数的一些性质，还有费马小定理，以及二次探测定理。

素数的一些性质

我们首先看一下素数的 4 条有趣的性质：

不存在最大的素数
假设最大的素数为 $p_k$ ，小于它的所有素数为 $p_1, p_2, \dots, p_{k-1}$ ，那么我们可以构造出数 $p_1p_2\cdots p_k+1$ ，它不能被 $p_1, \cdots, p_k$ 中的任何一个数整除，故它是素数，又它显然大于 $p_k$ ，于是可以得出不存在最大的素数。
相邻素数之间的间隔任意大

考虑数 $a$ 满足 $0\le a\le n$ ，那么 $n!+a$ 一定能被 $a$ 整除，因此长度为 $n$ 的数列 $n!,n!+2, \cdots, n!+n$ （注意没有 $n!+1$ ）都是合数，由于 $n$ 可以任意大，所以相邻素数之间的间隔可以任意大。
所有大于 2 的素数都可以被唯一的表示为两个平方数之差

所有大于 2 的素数都是奇数，假设它是 $2n+1$ ，那么它可以被表示为 $(n+1)^2-n^2$ 。

下面证明这种表示法是唯一的。假设素数 $p$ 可以被表示为 $a^2-b^2$ ，即 $p=(a+b)(a-b)$ ，因为 $p$ 是素数，所以只能有 $a-b=1,a+b=p$ ，得证。
当 $n$ 为大于 2 的整数时， $2^n+1$ 和 $2^n-1$ 两个数中，如果其中一个数是素数，那么另一个数一定是合数

显然 $2^n\nmid 3(n>2)$ ，如果 $2^n\equiv 1\pmod{3}$ ，那么 $(2^n-1)\mid 3$ 为合数；如果 $2^n\equiv 2\pmod{3}$ ，那么 $(2^n+1)\mid 3$ 为合数。

Fermat 素性测试

回顾一下费马小定理：

若 $p$ 为素数，且 $a\bot p$ ，那么有 $a^{p-1}\equiv 1\pmod{p}$ 。

根据费马小定理，我们很容易想到能不能利用它的逆定理来判定素数呢？很遗憾，费马小定理的逆定理是伪的。

人们用伪素数来称呼满足费马小定理的合数，如果是令 $a=2$ 的情况下的伪素数，就叫它以 2 为底的伪素数，其他取值情况下的名字以此类推。

为了提高这个素数测试的正确率，一个很自然的想法就是多次选取 $a$ 来判断，一旦不满足费马小定理就判定它为合数，显然正确率随 $a$ 的选取次数的增加而增加。我们随机选取若干个小于 $n$ 的数来作为 $a$ 的取值进行测试，这个判定素数的方法就是所谓的 Fermat 素性测试。

然而不幸的是，存在 Carmichael 数，它们满足当 $a$ 取遍所有小于 $n$ 的数时都满足费马小定理，自身却是合数。

二次探测定理

要继续加强素数的判定方法，就轮到二次探测定理出场了。

当需要判定的数 $n>2$ 时，显然 $n-1$ 是偶数，如果小于 $n$ 的数 $a$ 满足 $a^{n-1}\equiv 1\pmod{n}$ ，那么 $a^{n-1}-1=(a^{\frac{n-1}{2}}+1)(a^{\frac{n-1}{2}}-1)\mid n$ ，若 $n$ 为素数，则 $a^{\frac{n-1}{2}}\equiv n-1\pmod{n}$ 或 $a^{\frac{n-1}{2}}\equiv n+1\pmod{n}$ ，我们可以利用这一性质来继续加强素数的判定。

二次探测定理就是指，如果 $p$ 是奇素数，那么对于正整数 $x$ ，若 $x^2\equiv1\pmod{p}$ ，则 $x\equiv1\pmod{p}$ 或 $x\equiv p-1\pmod{p}$ 。

Miller Rabin 素性测试

Miller Rabin 素性测试综合以上方法，不断提取 $n-1$ 的因子 2 ，将 $n-1$ 表示为 $d\times2^r$ 的形式（其中 $d$ 为奇数），首先得到 $a^d$ ，然后不断将其平方直到变为 $a^{n-1}$ ，每次平方后首先测试是否满足 $(a^{d\times 2^s})^2\equiv 1\pmod{n}$ ，看是否满足二次探测定理的条件，如果满足就立即判断是否满足它的结论，一旦不满足就判断 $n$ 为合数。

Miller Rabin 素性测试也是不确定算法，我们可以把以 $a$ 为底的满足 Miller Rabin 素性测试的合数称为以 $a$ 为底的强伪素数。第一个以 2 为底的强伪素数是 2047 ，而第一个以 2 和 3 为底的强伪素数则大到了 1 373 653 。

对于大数的 Miller Rabin 测试，底数一般是随机选取，但是当待测数不太大时，底数的选取就有一些技巧了。如，当 $n<4,759,123,141$ 时，选取 $2,7,61$ 进行测试即可。随机选取 $k$ 个底数进行测试的失误率大概是 $4^{-k}$ 。

另外还有第一个多项式的、确定的、无需其它条件的素性判断算法 AKS 算法，之后有空可以了解一下。

Miller Rabin 的一点小优化：当某一次平方后得到 $a^{d\times 2^s}\equiv n-1\pmod{n}$ ，那么之后所有的平方操作都会得到 1 ，可以直接通过此次测试。

bool MillerRabin(int n, int t = 8) {
    if (n < 3 || n % 2 == 0) return false;  // n = 2 时虽然是素数，但是不满足 MillerRabin 素性测试的条件
    int d = n - 1, r = 0;
    while (d % 2 == 0) d >>= 1, r++;
    while (t--) {  // t 为测试次数，最好大于 8
        int a = rand() % (n - 2) + 2, s;  //为了不让 a = 1 ，所以最后是 +2
        int u = qpow(a, d, n);
        if (u == 1) continue;  //此时后面平方总会得到 1 ，必然满足测试，直接跳过
        for (s = 0; s < r; ++s) {
            if (u == n - 1) break;  //小优化
            u = (long long)u * u % n;
        }
        if (s == r) return false;  //如果存在一次平方后不满足条件，s 会增加到 r ，说明此次测试失败
    }
    return true;
}