\(\text{Miller-Rabin}\)素性测试
\(\text{Miller-Rabin}\)素性测试分为两步，分别是费马小定理逆定理和二次探查。（算法导论中文版567页，英文版968页）
首先把偶数去掉，下文中的探查对象\(p\)均为奇数。
对于任意整数\(a\)和素数\(p\)，有费马小定理：\[a^{p-1}\equiv 1\pmod p\]按照其逆否命题可知如果上式不成立则\(p\)一定不是素数，可是对于一些被称为“伪素数”的数\(n\)，\(a\)取遍\(1\cdots n-1\)上式都成立，但是它们是合数。换言之，费马小定理的逆定理不一定成立。
对于通过上述测试的数，\(\text{Miller-Rabin}\)素性测试要追加一步，称为二次探查。
考虑方程 \(x^{2k}\equiv 1\pmod p\) 的解，可以化为 \((x^k+1)(x^k-1)\equiv 0\pmod p\)，在\(p\)为素数时解只能为 \(x^k\equiv 1\) 或 \(x^k\equiv p-1\pmod p\)，在\(p\)为合数时则有其它解。
所以在 \(a^{p-1}\equiv 1\pmod p\) 成立时，Miller-Rabin会令 \(u=\frac{p-1}{2}\)，然后判断是否通过二次探查：即判断 \(a^u\bmod p\) 的值是否等于\(1\)或\(p-1\)，或是把\(u\)再提出一个\(2\)的因子变成\(\frac{u}{2}\)，然后再进行上述的探查。实际上在实现时会先把\(p-1\)的\(2\)的因子全提出来然后再通过一次次平方来进行分步探查，只要遇到一步满足条件即判断为素数。
素数一定会通过这样的判断；一个合数有\(\frac{1}{4}\)的概率通过这个判断。但是实践证明：对于\(\text{int32}\)范围中的数，使用\(2,7,61\)探测即不会出错；对于\(\text{int64}\)范围中的数，使用前十个素数探测即可。结合代码理解：
ll qpow(ll base, ll exp, ll mod); // 快速幂，计算 (base^exp)%mod
bool check(ll a, ll p) {
ll t = 0, k = p - 1;
while (!(k & 1)) {
t++;
k >>= 1;
}
ll x = qpow(a, k, p);
if (x == 1 || x == p - 1)
return true;
while (t) {
x = (x*x) % p;
if (x == p - 1)
return true;
t--;
}
return false;
}
bool millerrabin(ll x) {
return x == 2 || x == 7 || x == 61 || ((x > 2) && (x & 1) && check(2, x) && check(7, x) && check(61, x));
}
\(\text{Pollard-Rho}\)因数分解
\(\text{Pollard-Rho}\)分解算法期望复杂度为\(O(n^{\frac{1}{4}})\)，适用于int64范围内的数的分解。它使用一种神秘的随机方法来枚举因子，尝试进行分解。
设被分解数为\(p\)，首先运行\(\text{Miller-Rabin}\)，如果被分解数是素数则停止。现在我们要枚举一些\(a\)然后计算它们的\(\text{gcd}\)，判断这个数是否不是\(1\)。如果可以分解则分成两半继续递归。
考虑一种奥妙重重的枚举方法。先随机一个数，设为 \(x_0\)。递推计算 \(x_i=x_{i-1}*x_{i-1}+c\bmod p\)，每次枚举的 \(a\) 即为 \(x_i-x_{0}\)。观察发现，几次递推后会出现 \(x_i=x_j\) 的情况，此时就停止枚举，返回失败。
为了优化，我们要限制它的递推步数\(k\)，而且每\(k\)次递推后就把\(k\)乘以二，然后重新指定新的随机\(x_0\)。由于某种神秘的原因，这个过程很快。