100种算法【Python版】第14篇——Pollard‘s Rho 质因数分解算法

1 基本原理

Pollard’s Rho 算法是由约翰·波拉德（John Pollard）于1975年提出的一种用于整数因数分解的概率算法。它以高效性和实现简洁著称。

核心原理

• 伪随机序列生成：利用一个简单的迭代函数生成一个伪随机数序列。
• 周期检测：根据鸽巢原理，当序列在有限集合内循环时，序列元素会发生重复。
• 最大公约数：通过计算序列中两元素差值与待分解整数的最大公约数，可能找到非平凡因子。

基本思想
算法通过迭代函数生成两个序列，一个以正常速度推进（慢指针），另一个以两倍速度推进（快指针）。当序列进入循环后，快慢指针会相遇，此时两者的差值与待分解整数 n n