本文目录
1 基本原理
Pollard’s Rho 算法是由约翰·波拉德（John Pollard）于1975年提出的一种用于整数因数分解的概率算法。它以高效性和实现简洁著称。
核心原理
- 伪随机序列生成：利用一个简单的迭代函数生成一个伪随机数序列。
- 周期检测：根据鸽巢原理，当序列在有限集合内循环时，序列元素会发生重复。
- 最大公约数：通过计算序列中两元素差值与待分解整数的最大公约数，可能找到非平凡因子。
基本思想
算法通过迭代函数生成两个序列，一个以正常速度推进（慢指针），另一个以两倍速度推进（快指针）。当序列进入循环后，快慢指针会相遇，此时两者的差值与待分解整数 n n