Pollard's Rho 算法

Pollard's Rho 算法(波拉德 Rho 算法)是由波拉德于一九七五年提出的整数因数分解随机算法。它通过构造一个伪随机数序列并观察其在模某待分解合数意义下的循环结构,用不断计算差值与合数的最大公约数的方式,期望在较短时间内找到一个非平凡因子。因序列轨迹形似希腊字母 Rho 的环带尾巴而得名。

概述

大整数分解是密码学与数论的核心难题。Pollard's Rho 属于亚指数复杂度以下的实用启发式方法,尤其擅长找出合数中相对较小的质因子,其期望时间与最小质因子的平方根成正比。它内存占用极低、实现简洁,常与 Miller-Rabin 素性测试配合,构成分解中等规模整数的标准工具链。

核心原理

• 伪随机序列:选定一个多项式迭代函数在模合数意义下生成看似随机的数列。
• 判圈技巧:利用 Floyd 快慢指针检测序列进入循环,快指针每次走两步、慢指针走一步。
• 求公因子:不断计算两指针对应值之差与合数的最大公约数,一旦得到大于一且小于合数的结果即找到非平凡因子。
• 失败重启:若最大公约数直接等于合数,则更换迭代函数的常数或初值重新尝试。
• 加速优化:可把多次差值连乘后再统一求一次公约数,以减少昂贵的求公约数调用。

应用场景

Pollard's Rho 常用于竞赛与工程中分解中等大小的整数、计算欧拉函数或约数结构、破解基于小因子的弱密钥等。它是通用因数分解流程中的关键一环,通常先做素性测试排除质数,再用它逐层剥离合数的质因子。

常见问题

问:Pollard's Rho 能分解任意大整数吗?答:不能高效分解所有大整数。它对含较小质因子的合数很快,但面对两个都很大的质数之积仍然乏力,后者正是 RSA 安全性的基础。

问:为什么要配合 Miller-Rabin 使用?答:算法只对合数有效,需先用 Miller-Rabin 判定当前数是否为质数,避免对质数徒劳分解,并在递归分解时正确终止。