首页 > 代码库 > 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学习笔记
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。