大整数分解(Pollard Rho 算法)

数字输入

示例数字:

分解结果

输入数字后点击"开始分解"

Pollard Rho 算法说明:

算法原理: 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 为测试轮数,用于素性判定

应用场景:

  • 密码学:分析 RSA 加密的安全性(破解弱密钥)
  • 数论研究:研究数字的因子结构和分布
  • 竞赛编程:快速分解大整数,解决数论问题
  • 数学教育:理解整数分解和素数的性质