算法原理:
Pollard Rho 是一种用于整数分解的概率性算法,特别适合找到合数的中等大小因子。算法名称来源于其运行轨迹形似希腊字母 ρ (rho)。
优化策略:
- 试除法优化:先用小素数(2, 3, 5, 7, 11...)进行试除,快速找到小因子
- Pollard Rho:对于较大的合数,使用伪随机序列 x = (x² + c) mod n 找到因子
- Floyd 判圈算法:使用快慢指针检测序列中的环,优化空间复杂度
- Miller-Rabin 素性测试:在找到因子后,判断是否为素数,避免继续分解
- 递归分解:对找到的因子递归进行分解,直到所有因子都是素数
时间复杂度:
- 试除法:O(√n),适用于小数字或快速找到小因子
- Pollard Rho:期望时间 O(n^(1/4)),对于有中等因子的数字非常高效
- Miller-Rabin:O(k log³n),k 为测试轮数,用于素性判定