整数分解费马方法以及Pollardrho pollard rho

整数分解费马方法以及Pollardrho pollard rho
大整数分解现在任然是个世界级的难题,但却依旧是个非常重要的研究方向,大整数在公共密钥的研究上有着重要的作用。 而对于大整数的分解有很多种算法,性能上各有优异,比如大整数分解的Fermat方法,Pollardrho方法,试除法,以及椭圆曲线法,连分数法,二次筛选法,数域分析法等等。这里,我主要讲解其中两种算法的原理和操作。 首先,对于任意的一个偶数,我们都可以提取出一个2的质因子,如果结果仍为偶数,则可继续该操作,直至将其化为一个奇数和2的多少次幂的乘积,那么我们可以假定这个奇数可以被表示成2*N+1,如果这个数是合数,那么一定可以写成N=c*d的形式,不难发现,式中的c和d都是奇数,不妨设c>d,我们可以令a=(c+d)/2,b=(c-d)/2,那么的可以得到N=a*a-b*b,而这正是Fermat整数分解的基础;由不等式的关系,我们又可以得到a>=sqrt(c*d)=sqrt(N),那么,我们就可以枚举大于N的完全平方数a*a,计算a*a-N的值,判断计算的结果是否为一个完全平方数,如果是,那么a,b都是N的因子,我们就可以将算法递归的进行下去,知道求出N的所有质因子。 容易看出,Fermat分解大数的效率其实并不高,但是比起试除法要好了很多;而且每次的计算都是计算出N的一个因子,更加降低了其效率。这就让我们想着去尝试新的算法,那就是Pollardrho算法。 Pollardrho算法的原理就是通过某种方法得到两个整数a和b,而待分解的大整数为n,计算p=gcd(a-b,n),直到p不为1,或者a,b出现循环为止。然后再判断p是否为n,如果p=n成立,那么返回n是一个质数,否则返回p是n的一个因子,那么我们又可以递归的计算Pollard(p)和Pollard(n/p),这样,我们就可以求出n的所有质因子。 具体操作中,我们通常使用函数x2=x1*x1+c来计算逐步迭代计算a和b的值,实践中,通常取c为1,即b=a*a+1,在下一次计算中,将b的值赋给a,再次使用上式来计算新的b的值,当a,b出现循环时,即可退出进行判断。 在实际计算中,a和b的值最终肯定一出现一个循环,而将这些值用光滑的曲线连接起来的话,可以近似的看成是一个ρ型的。 对于Pollardrho,它可以在O(sqrt(p))的时间复杂度内找到n的一个小因子p,可见效率还是可以的,但是对于一个因子很少、因子值很大的大整数n来说,Pollardrho算法的效率仍然不是很好,那么,我们还得寻找更加的方法了。

  

爱华网本文地址 » http://www.413yy.cn/a/25101012/145042.html

更多阅读

佳能IP1200打印机加墨方法以及清零步骤 联想打印机清零步骤

买了一台佳能的喷墨打印机,是IP1200。买之前也没有仔细研究打印机,只觉得佳能毕竟是大牌货色,质量应该没什么问题,而且当时1200也是比较新的型号。买了以后就上网查找与之相兼容的便宜的国产墨盒,毕竟1200用的这个原装彩色墨盒(CL-41)要160

出体方法以及出体后的注意事项 竹养殖方法和注意事项

看了些有关的书和资料自己又去试了一下下偶总结出了能出体的方法: 1.要相信自己能成功(自我暗示很重要) 2.想要成功率高的话最好在''睡''前把自己搞累(好让自己身体放松快)3.找个地方睡觉,最好在能让自己放松的地方(怎么睡随便你,

费马小定理与循环小数 费马小定理 逆元

(选自《数论妙趣——数学女王的盛情款待》第十章 循环到无穷)我们知道,如果某个整数的倒数,可以表达为有限小数,其必要条件是该整数只含有2,5的方幂,或者兼而有之。否则,将出现循环小数。研究循环小数,就要掌握循环节的规律。对此,费马小

声明:《整数分解费马方法以及Pollardrho pollard rho》为网友恋上棉花糖分享!如侵犯到您的合法权益请联系我们删除