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;
}
参考：
数论部分第一节：素数与素性测试 | Matrix67: The Aha Moments