数学-数论-Pollard_rho算法

Posted by

定义

Pollard_rho算法是一种快速分解大整数的随机化算法。

求解算法

思路与简单证明

对于一个整数\(x\),先判断该数是否是质数(通常配合Miller_Rabin算法),若不是则尝试找出该数的一个因子\(t\),递归执行\(t\)和\(\lfloor \frac nt\rfloor\)。
寻找因子\(p\)的方法:
定义函数\(f(x)\)为\([0,p)\)到\([0,p)\)的一个随机映射,通常为\((x^2+rnd)\ mod\ n\),\(rnd\)为一个随机数;
初始时\(x\)为一个随机数,\(y=f(x)\),循环执行以下操作:

  1. 令\(p=gcd(|x−y|,n)\)若\(p\not=1\),那么\(p\)就是\(n\)的一个因子,退出循环;

  2. \(x=f(x),y=f(f(y))\);

  3. 若\(x=y\),说明陷入了循环,重新随机\(rnd\)和\(x\)。

为什么\(x=y\)就说明陷入了循环呢?
如果将\(f(x),f(f(x)),f(f(f(x))),\ldots\)的轨迹画出来,应该呈下图这样的\(\rho\)型:

每次更新\(x\)和\(y\)时,\(y\)总比\(x\)领先一步,如果\(x=y\),说明\(x\)和\(y\)相差的步数恰好是环的大小(类似于跑的快的人把跑得慢的人套圈了),就需要重新寻找因子。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注