Pollard-rho & Miller Rabin

Pollard-rho

• 找到 \(n\) 的一个非平凡因子。

暴力

发现 \(n\) 的因子数 \(\omega(n)\) 实际很少，我们考虑随机一个数，判断是否和 \(n\) 有公因子，显然很劣。

生日悖论：随机 \(k\) 个值域大小为 \(n\) 的数，当 \(k\ge \sqrt n\) 时，\(k\) 个数两两不同的几率几乎为 \(0\)。

以下忽略这种概率极小的情况。

我们考虑找到 \(n\) 的最小质因子 \(p\)，显然 \(p\le \sqrt n\)，随机 \(n^{\frac14}\) 个数，组成的集合为 \(S\)，则存在两个数 \(x,y\in S\) 使得 \(x\equiv y\pmod p\)，因为值域在 \([0,p)\) 并随机了 \(n^{\frac 1 4}\ge \sqrt p\) 个数。

于是时间复杂度为 \(\mathcal O(\sqrt n)\)，和质因数分解相比没有明显变化。

比较随机集合中每一对 \(x,y\) 太费时了，能否少比较几对数呢？PR 算法中引出了一个产生序列的函数：

令 \(f(x)=x^2+c\)，其中 \(c\) 是随机数，则构造随机序列 \(a_1=1\)，\(a_i=f(a_{i-1})\)。

对于这个序列，函数 \(f\) 产生了一个很关键的性质：

令 \(val(i,j)=|x_i-x_j|\)，则\(val(i+1,j+1)=|f^2(x_i)-f^2(x_j)|=|(x_i-x_j)(x_i+x_j)|\bmod n\)，也就是 \(val(i,j)\mid val(i+1,j+1)\)。

这说明了所有 \(val(i,j)\) 都可以归纳到 \(val(i+(|S|-j),|S|)\)，于是我们只要计算 \(\gcd(val(i,|S|),n)>1\)。

但是有一个很尴尬的事情，因为 \(val(i+1,j+1)=|(x_i-x_j)(x_i+x_j)|\bmod n\)，当 \(x_i+x_j\equiv 0\pmod n\) 时，后面的计算都无效了，而且 \(f\) 函数并不是真随机，很容易产生环，我们考虑更准确的算法。

Floyd 判环算法

我们维护两个指针 \(s=x_i,t=x_{2i}\)，在迭代过程中如果 \(s=t\)，说明此时环长为 \(i\)，可以推出，否则 \(val(i,2i)\) 计算了下标距离为 \(i\) 的所有 \(val\)，时间复杂度为 \(\mathcal O(n^{\frac 14}\log n)\)。

倍增优化

这个 \(\log\) 看起来很难受，考虑均摊掉。

如果 \(\gcd(a,n)>1\)，则 \(\gcd(ac,n) >1\)，同时 \(\gcd(ac\bmod n, n)>1\)。

于是我们可以每隔 \(128\) 种距离算一次 \(\gcd\)，只要计算 \(\gcd(\prod val(s,t),n)>1\) 即可，时间复杂度 \(\mathcal O\left(\dfrac{128n^{\frac14}}{\log n}\right)=\mathcal O(n^{\frac14})\)。

然后如果找不到质因子就要随机多次，这个随机次数位置，但应该是常数级（待定）。为了排除 \(n\) 为质数 Pollard-rho 怎么也跑不出来的情况，我们需要一个快速判断是质数的算法。

Miller Rabin

• 判断 \(n\) 是否是一个质数。

费马素性检验

费马小定理：\(p\in \mathbb P, a\nmid p,a^{p-1}\equiv1\pmod p\)。

于是我们只要随机 \([1,p)\) 内的数，判断是否满足费马小定理即可。

可惜的是，对于费马伪素数，素性检验的正确性无法保证。

Miller Rabin 素性检验

二次探测定理：对于奇素数 \(p\)，\(x\equiv 1\pmod p\) 的解只有 \(1\) 和 \(p-1\)。

令 \(p-1=t2^k\)，其中 \(t\) 为奇数。随机一个数 \(a\)，求出 \([a^t,a^{2t},a^{4t},\cdots,a^{p-1}]\) 中每个数 \(\bmod\ p\) 的值 \([b_0,b_1,b_2,\cdots,b_k]\)。根据费马小定理 \(b_k=1\)，且当 \(b_i=1\) 时，\(b_{i-1}^2\equiv b_i\pmod p\)，所以只要判断数组是否是 \([?,?,\cdots,?,-1,1,1,\cdots,1]\) 的形态即可，时间复杂度 \(\mathcal O(\log^3n)\)，\(a\) 不必随机，在值域为 long long 范围内只要取前 12 个质数即可。