Pollard rho 因子分解法

一种 素因数分解算法，也称为 Pollard 蒙特卡洛因子分解法。Pollard 因子分解法有两个方面。第一个方面是迭代公式直到它陷入循环的想法。设 , 其中 是要分解的数， 和 是其未知的素因子。迭代公式

(1)

或几乎任何多项式公式（ 是一个例外）对于任何初始值 都会产生一个最终陷入循环的数字序列。 s 变为循环的预期时间和循环的预期长度都与 成正比。

然而，由于 其中 和 互质，中国剩余定理保证了 (mod ) 的每个值唯一对应于值对 (), )。此外，序列 s 遵循完全相同的公式模 和 ，即

			(2)
			(3)

因此，序列 (mod ) 将陷入长度约为 的短得多的循环。可以直接验证两个值 和 具有相同的值 (mod )，通过计算

(4)

这等于 。

Pollard 方法的第二部分涉及检测序列已变为周期性的事实。Pollard 的建议是使用归因于 Floyd 的想法，即比较 和 对于所有 。Brent 因子分解法中使用了不同的方法。

在最坏的情况下，Pollard 算法可能非常慢。