Pollard Rho因子分解算法

有一类问题，要求我们将一个正整数x，分解为两个非平凡因子（平凡因子为1与x）的乘积x=ab。

显然我们需要先检测x是否为素数（如果是素数将无解），可以使用Miller-Rabin算法来进行测试。

Pollard Rho是一个非常玄学的方式，用于在O(n^1/4)的期望时间复杂度内计算合数n的某个非平凡因子。事实上算法导论给出的是O(√p)，p是n的某个最小因子，满足p与n/p互质。但是这些都是期望，未必符合实际。但事实上Pollard Rho算法在实际环境中运行的相当不错。

Pollard Rho利用伪随机数生成公式来提供待测因子，其公式为x_i=x_i-1^2+c(mod n)，其中c是开始时确认的随机常数。我们只要给出x₁，利用这个公式可以生成一系列数值。由于每个数完全依赖于前一个数，因此数值的分布中必定含环，我们设t为环的路口，u为环的周长，那么有x_t+i=x_t+u+i。而整个数值分布就像一个ρ符号，因此该算法的后缀用Rho来表示。我们将该公式得出的序列视作随机序列。

生日悖论中指出一个√d个学生的班级中，期望至少有一对人在同一天生日，其中d是一年中的日期，即365。同样一个√d个人的班级中，至少有一对人在同一天生日的概率大于50%。我们将n视作一年中的天数，而1~n-1中的每个值都对应一年中的日期，将x1,x2,...视作学生，那么序列中期望有两个有两个人相同，只需要序列的长度达到√n即可。因此我们可以认为ρ符号的尾部与环的周长的期望均为√n。

假设n=ab，其中a与b均不是n的平凡因子，我们假设a<=b，可知a<=√n。我们记yi=xi(mod a)。可知：

$$ y_i=x_i\left(mod\ a\right)=\left(x_{i-1}^2+c\right)\left(mod\ n\right)\left(mod\ a\right)=\left(x_{i-1}^2+c\right)\left(mod\ a\right) $$ $$ =\left(\left(x_{i-1}\left(mod\ a\right)\right)^2+c\right)\left(mod\ a\right)\Rightarrow\left(y_{i-1}^2+c\right)\left(mod\ a\right)=y_i\left(mod\ a\right) $$

我们依据a为模数建立了新的一个ρ型轨迹，且a的ρ型轨迹的环必然仅出现n的ρ型轨迹的环上的数值（模a的结果）。由同样的分析可得a的ρ型轨迹的环的尾部和环的长度的期望均为n^(1/4)。对于a的ρ型轨迹的环上的任意一点k，假设其对应的是两个不同的值xi与xj，即xi<>xj(mod n)但xi=xj(mod a)。此时可以知(xi-xj)=rp(mod n)，而gcd(xi-xj, n)的结果必然是n的一个非平凡因子（且能被a整除）。我们可以利用一个特定的变量p先后在迭代到x1,x2,x4,x8,...时记录这些值，之后每次都校验gcd(xi-p, n)是否既非1又非n，如果满足则找到n的非平凡因子，否则继续迭代。之前说过a的ρ型轨迹的环的尾部和环的长度的期望均为n^(1/4)，因此当我们p记录xh时，其中xh落在a的ρ型轨迹的环上且h大于等于环的周长时，此时我们会沿着a的ρ型轨迹的环进行周而复始的循环迭代，最终在修改p之前xi回到了xh的位置，此时借助gcd(xi-p, n)我们就找到了一个n的非平凡因子。h的期望应该为O(n^(1/4))，因此时间复杂度的期望应该为O(n^(1/4))。

下面给出代码：