Miller-Rabin 和 Pollard-Rho 小记

Miller-Rabin 可以帮助我们快速判断一个大数是不是质数，现在已经有了确定性算法。在 \(2^{64}\) 范围内，我们可以快速地进行确定性判素。

二次校验定理：若 \(p\) 为奇质数，则 \(a^x \equiv 1 \pmod p\) 的解为 \(x = ±1\)。

我们有这样的流程：

令 \(d = p - 1\)，然后不断检验 \(a^d\)，并令 \(d \leftarrow \dfrac{d}{2}\)，直到 \(d\) 为奇数（注意这时要再检验一次）。

容易想到，我们可以随机一些 \(a\) 并对其进行判断。可以证明的是，取前 12 个质数作为 \(a\) 进行校验就可以在 \(2^{64}\) 的范围内的确定一个数的素性了。

Pollard-Rho 可以帮助我们快速求出一个合数 \(n\) 的质因子。它采用随机算法，

一开始时，\(t = 0\)，然后每次让 \(t \leftarrow t^2 + c\;\text{mod}\;p\)，其中 \(c\) 为一个随机的常数。

这样得到的一群随机数会成环，样子很像 rho，所以得名 Pollard-Rho。

我们假设 \(n\) 最小的质因子为 \(m\)，若连续两次生成的 \(t\) 的差的绝对值在模 \(m\) 意义下的值相同，那么这个差和 \(n\) 的 gcd 就是一个 \(n\) 的非平凡因子，由生日悖论，需要的 \(t\) 的个数是 \(O(\sqrt{m})\) 的，也就是 \(O(n^{\frac{1}{4}})\) 的，因为 \(m \leq \sqrt{n}\)。

为了优化这个过程，我们采用倍增法，即枚举步长，在每段结尾算一遍 \(\prod |t_i - t_0|\) 与 \(n\) 的 gcd，并在每个步长的过程中每 \((2^k - 1)\) 次生成 \(t\) 后求一遍 gcd，这里一般取 \(k = 7\)。

如果 gcd > 1，那么我们就成功找到了 \(n\) 的一个非平凡因子，直接返回其值即可。