Pollard Rho Algorithm
Pollard Rho 用伪随机序列 x_{i+1}=f(x_i) mod n 寻找大数因子，期望复杂度 O(n^(1/4))。
用途
中等大小整数因子分解，用于攻击弱 RSA 模数。
机制
用 f(x)=x^2+c mod n 生成序列，Floyd 找环。环上 gcd(|x_i-x_j|, n) 可能给出非平凡因子。生日悖论使期望步数 O(p^(1/2))，p 为最小素因子。
用例
- 整数因子分解
- RSA 攻击
- 数论算法
Pollard Rho 用伪随机序列 x_{i+1}=f(x_i) mod n 寻找大数因子，期望复杂度 O(n^(1/4))。
中等大小整数因子分解，用于攻击弱 RSA 模数。
用 f(x)=x^2+c mod n 生成序列，Floyd 找环。环上 gcd(|x_i-x_j|, n) 可能给出非平凡因子。生日悖论使期望步数 O(p^(1/2))，p 为最小素因子。