Pollard-rho算法简要分析

标签（空格分隔）： 数论

概述

Pollard-rho算法是质因数分解的一种有效的蒙特卡洛算法，可以在期望$O(n^{1/4})$的复杂度内找到合数的一个因数。其核心思想就是随机的选取$x\lt n$，试图找到一个$x|n$。但直接利用反复随机的方法是行不通的，为了提高效率，Pollard-rho算法依靠“生日悖论”来找到一个因数。

“生日悖论”

生日悖论是指$k$个人两两生日不同的概率，随着$k$的增长下降的非常快。如果在$n$个数中随机选取$k$个，其两两之差全不为一个常数$c$的概率为$O(\frac{1}{n^{k^2}})$，因而如果通过两两之差去“碰”一个数，只需要期望$k = O(\sqrt n)$次。考虑如果一个数$n$的最小质因子是$O(\sqrt n)$，其小于$n$的倍数有$\Omega (\sqrt n)$个，如果我们随机选取$k$个数，两两作差寻找，碰到的概率为$\Omega(\frac{1}{(\sqrt n)^{k^2}})$，这样只需要期望$k = O(n^{1/4})$次就可以找到一个因数。

弗洛伊德判环

考虑如何在$O(1)$的附加空间内沿着环走一周，考虑用两个指针，一个每次移动一步，一个每次移动两步，其位置差每次增加$1$，直到位置差为环长即两个指针相遇，则他们刚好绕环一周，且他们取遍了每一种可能的位置差。

Pollard-rho算法

Pollard-rho算法的核心是构造一个“随机的”函数：

$$f(n) = f(n-1)^2+1$$

我们要用这个函数生成随机数去“碰”一个质因数的倍数，设这个集合为$S$。

注意到$f(x)$在模$n$意义下必然会形成一个环。考虑$f(x)-f(y)=f^2(x-1)-f^2(y-1) = (f(x-1)+f(y-1))(f(x-1)-f(y-1))$，有一个$f(x-1)-f(y-1)$因子。因而如果$f(x-1)-f(y-1)\in S$，就有$f(x)-f(y)\in S$。而根据欧几里得算法$\gcd(x, n)=\gcd(n,x\bmod n)$说明了如果一个数与$n$有公因子，那么模$n$后也有。因为形成环，立刻可以得到对于任意的$x_1, y_1, x_2, y_2$，如果满足$|x_1-y_1| = |x_2-y_2|$，即他们在环上的位置差相等，那么$|f(x_1)-f(y_1)|\bmod n\in S \iff |f(x_2)-f(y_2)|\bmod n\in S$。

换言之，环上的二元组被其之间的距离划分为了若干个$O(k)$个等价类，$k$为环长。那么这显然可以用弗洛伊德判环快速的完成，事实上，弗洛伊德判环每一次移动，都相当于进行了$O(k)$次两两比较。因而最终复杂度就是$O(n^{1/4})$。

算法流程就是，每次随机一个初始解$f(0)$，通过$x=f(x), y = f(f(y))$进行弗洛伊德判环，直到$\gcd(|x-y|, n)\ne 1$找到一个约数，或者$x=y$算法失败。如果找到一个约数，递归的分解两边。为了防止大素数导致时间退化，需要先用$Miller-rabin$素数测试判断是否是素数。

update: 5.21

复杂度分析被hack掉了...详情见评论orz

经过一些实验，看起来使用偶数次多项式同余做$f(x)$要比使用奇数次多项式优秀得多，前者约为$n^{1/4}$，后者约为$n^{1/2}$