ipad 9.3.5降级方法 rho 9.3.5Pollardrho方法_rho

分享人:等候下个花季来源:互联网28
9.3.5 Pollard rho方法
1975年，John M. Pollard提出了第二种因数分解的方法。Pollard rho因数分解方法基于下列几点：
(1) 假定有两个整数[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/174700711.jpg" width=18 border=0> 和[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0> 使得p可以整除[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/174700711.jpg" width=18 border=0>-[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0>，但是n不能整除[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=20 alt="" src="http://pic.aIhUaU.com/201602/15/174856699.jpg" width=64 border=0> 。
(2) 可以证明[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=24 alt="" src="http://pic.aIhUaU.com/201602/15/174936734.jpg" width=174 border=0> 。因为p可以整除[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/174700711.jpg" width=18 border=0>- [I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0>，可以写成[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=23 alt="" src="http://pic.aIhUaU.com/201602/15/175038225.jpg" width=135 border=0> 。但是，因为n不能整除[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/174700711.jpg" width=18 border=0>-[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0>，很明显q不能整除n。这就表明[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=23 alt="" src="http://pic.aIhUaU.com/201602/15/175137971.jpg" width=141 border=0> 既可以是1也可以是n的一个因数。
下列算法重复选择[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/174700711.jpg" width=18 border=0>和[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0>，直到求出一个合适的对。
(1) 选择[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/174700711.jpg" width=18 border=0>，一个小的随机整数称为种子。
(2) 运用函数算出[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0>，使得n不能整除[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=20 alt="" src="http://pic.aIhUaU.com/201602/15/175306689.jpg" width=104 border=0> 。这里所用的一个函数也许就是[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0> = [I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=25 alt="" src="http://pic.aIhUaU.com/201602/15/175356708.jpg" width=135 border=0> (a通常选作1)。
(3) 计算[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=22 alt="" src="http://pic.aIhUaU.com/201602/15/175430723.jpg" width=135 border=0> 。如果它不是1，结果是n的一个因数；如果它是1，返回到步骤1并用[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=15 alt="" src="http://pic.aIhUaU.com/201602/15/174746351.jpg" width=18 border=0>重复这个过程。现在我们计算[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=18 alt="" src="http://pic.aIhUaU.com/201602/15/175513175.jpg" width=21 border=0> 。注意，在下一轮中，我们以[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=18 alt="" src="http://pic.aIhUaU.com/201602/15/175513175.jpg" width=21 border=0>开始，如此这般。如果我们运用Pollard rho算法列出x的值，就会发现最终要重复的这个值，创建一个和希腊字母rho ([I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=19 alt="" src="http://pic.aIhUaU.com/201602/15/175603728.jpg" width=12 border=0> )一样的形状，如图9-3所示。
[TR]
[TD][I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=311 alt="" src="http://pic.aIhUaU.com/201602/15/174555510.jpg" width=311 border=0>[/TD][/TR]
[TR]
[TD]图9-3 Pollard rho连续数[/TD][/TR]
为了减少反复的次数，算法做了一些改进。该算法用数对([I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/175713557.jpg" width=20 border=0> , [I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=17 alt="" src="http://pic.aIhUaU.com/201602/15/175713557.jpg" width=20 border=0>)开始，并且用[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=24 alt="" src="http://pic.aIhUaU.com/201602/15/175805135.jpg" width=98 border=0> ，迭代计算[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=24 alt="" src="http://pic.aIhUaU.com/201602/15/175852716.jpg" width=313 border=0> 。在每一次迭代中，我们都应用上述函数式运算(从第二步)第一次计算数对中的第一个元素，第二次计算数对中的第二个元素(参看算法9.6)。
算法 9.6 Pollard rho方法的伪代码
[TR]
[TD][I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=331 alt="" src="http://pic.aIhUaU.com/201602/15/175948477.jpg" width=670 border=0>[/TD][/TR]
[TR][/TR]
复杂度 这种方法需要算术运算[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=25 alt="" src="http://pic.aIhUaU.com/201602/15/180232659.jpg" width=25 border=0> 。不过，因为我们希望p小于或等于[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=24 alt="" src="http://pic.aIhUaU.com/201602/15/180313803.jpg" width=22 border=0> ，我们希望做[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=23 alt="" src="http://pic.aIhUaU.com/201602/15/180358279.jpg" width=34 border=0> 算术运算。这就是说比特操作复杂度是[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=27 alt="" src="http://pic.aIhUaU.com/201602/15/180430214.jpg" width=75 border=0> ，它是指数增长的。
例9.32
假定有一台每秒可以执行[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=20 alt="" src="http://pic.aIhUaU.com/201602/15/180511783.jpg" width=27 border=0> 比特(几乎10亿)运算的计算机。要分解一个大小如下的整数，近似的计算次数是多少？
(1) 60个十进制数位？
(2) 100个十进制数位？
解答
(1) 一个60个十进制数位的数几乎有200比特，那么复杂度就是[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=29 alt="" src="http://pic.aIhUaU.com/201602/15/180649523.jpg" width=57 border=0> 或[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=23 alt="" src="http://pic.aIhUaU.com/201602/15/180713773.jpg" width=29 border=0> 。如果每秒运算[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=22 alt="" src="http://pic.aIhUaU.com/201602/15/180738936.jpg" width=26 border=0> 次，算法可以在[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=22 alt="" src="http://pic.aIhUaU.com/201602/15/180803590.jpg" width=27 border=0> 秒或者说差不多12天中完成，
(2) 一个100个十进制数位的数几乎有300比特，复杂度是[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=23 alt="" src="http://pic.aIhUaU.com/201602/15/180827465.jpg" width=29 border=0> 。如果每秒运算[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=22 alt="" src="http://pic.aIhUaU.com/201602/15/180738936.jpg" width=26 border=0>次，该算法可以在[I]498)this.width=498;' onmousewheel = 'javascript:return big(this)' height=21 alt="" src="http://pic.aIhUaU.com/201602/15/180853399.jpg" width=29 border=0> 秒或许多年中完成。
例9.33
我们已经写出一个计算434617的因数的程序，结果是709 (434617 = 709′ 613)。表9-2所示的就是这种运算中数对(x和 y)和p的值。
表9-2 例9.33中x、y和p的值
[TR]
[TD]
[I]x[/I]
[/TD]
[TD]
[I]y[/I]
[/TD]
[TD]
[I]p[/I]
[/TD][/TR]
[TR]
[TD]
2
[/TD]
[TD]
2
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
5
[/TD]
[TD]
26
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
26
[/TD]
[TD]
23713
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
677
[/TD]
[TD]
142292
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
23713
[/TD]
[TD]
157099
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
346589
[/TD]
[TD]
52128
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
142292
[/TD]
[TD]
41831
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
380320
[/TD]
[TD]
68775
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
157099
[/TD]
[TD]
427553
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
369457
[/TD]
[TD]
2634
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
52128
[/TD]
[TD]
63593
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
102901
[/TD]
[TD]
161353
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
41831
[/TD]
[TD]
64890
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
64520
[/TD]
[TD]
21979
[/TD]
[TD]
1
[/TD][/TR]
[TR]
[TD]
68775
[/TD]
[TD]
16309
[/TD]
[TD]
709
[/TD][/TR]

ipad 9.3.5降级方法 rho 9.3.5Pollardrho方法_rho
  
ipad 9.3.5降级方法 

爱华网本文地址 » http://www.aihuau.com/a/381751/862674632319.html

更多阅读

iPhone系统怎么降级 苹果手机系统怎么降级

iPhone系统怎么降级——简介 很多朋友都会发现，iphone系统升级后，系统变慢，界面不适应，感觉还不如原来的好用！但又不知道怎么做，笔者现在就相关经验同大家分享！iPhone系统怎么降级——工具/原料iphone手机一台安装了itools的电脑一台！iP

win10ie浏览器怎么降级 IE浏览器如何降级

IE浏览器如何降级――简介IE浏览器不像是软件一样，可以自由的随便的卸载。通常一些新手，可能升级了IE后，出于网页兼容，使用习惯，个人爱好等方面的原因，不想使用新版本的IE，那么就像将其卸载了。（我比较喜欢新的版本，这次就演示如何从ie10回到

iphone6plus降级9.3.5 iphone6iPhone6 Plus怎么降级

iphone6iPhone6 Plus怎么降级――简介iphone6iPhone6 Plus怎么降级？当新的软件版本出现的时候，手贱党尝鲜党总是迫不及待地想升级自己的系统，有时候新系统又不靠谱到抓狂，这时候你不禁会问世上是否有后悔药可以喝一喝。真有，下面小编给大

诺基亚n1 a5cnb19降级 A5降级新希望 肌肉男已经更新支持

iPhone4等其他A4芯片只要你保持SHSH是可以从降级成功，但是iPad2等A5芯片则目前还没有特殊的办法可以从降级，而就在昨天，iPhone越狱团队肌肉男宣布已经发现一个苹果iPad2 降级技术，这个让很多想要从iPad2 降级的椒友多了一些期盼。肌肉

声明:《ipad 9.3.5降级方法 rho 9.3.5Pollardrho方法_rho》为网友等候下个花季分享！如侵犯到您的合法权益请联系我们删除