首页 > 代码库 > Pollard-Rho学习笔记

Pollard-Rho学习笔记

pollard-rho是对大数分解质因数的算法

先要米勒罗宾判下素数

主要思想是选取随机数,随机数生成是只与前一个随机数有关的。

这样因为生日悖论,选取重复导致出现循环的期望是根号n的

选取随机数 ri

计算ai = ri mod n

这时我们假定有 n1 | n ,bi = ai mod n1

当我们选取随机数时,如果发现序列b已经进入了循环而序列a还没进入循环,就说明已经有ai ≡ aj mod n1,而ai != aj 

那么我们就已经找到了n1 = gcd ( n , aj - ai )

当然实际上我们无法求出b序列,但我们可以通过a序列判断b是否进入循环

即若有gcd( aj - ai , n) !=1 or n 时,必然b已经进入循环,因为设n1=gcd( aj - ai , n ),aj - ai = k * n1,即bj - bi ≡ 0 mod n1

然后递归分解n1和n/n1

 

Pollard-Rho学习笔记