[原创]尝试用RHO方法分解因数

drc2000

[这个贴子最后由drc2000在 2011/01/04 01:28pm 第 2 次编辑]

[watermark]例1.用RHO方法分解35  
解:取X0=1
X1=1^2+1= 2≡ 2(mod35)   gcd( 2-1,35)=gcd( 1,35)=1
X2=2^2+1= 5≡ 5(mod35)   gcd( 5-2,35)=gcd( 3,35)=1
X3=5^2+1=26≡26(mod35)   gcd(26-5,35)=gcd(21,35)=7
∵7≠1,7≠35
∴7是35的一个因数.
35=7*5

例2:用RHO方法分解143
解:取X0=1
X1=1^2+1=    2≡ 2(mod143) gcd( 2- 1,143)=gcd( 1,143)= 1
X2=2^2+1=    5≡ 5(mod143) gcd( 5- 2,143)=gcd( 3,143)= 1
X3=5^2+1=   26≡26(mod143) gcd(26- 5,143)=gcd(21,143)= 1
X4=26^2+1= 577≡95(mod143) gcd(95-26,143)=gcd(69,143)= 1
X5=95^2+1=9026≡17(mod143) gcd(95-17,143)=gcd(78,143)=13
∵13≠1,13≠143
∴13是143的一个因数.
143=13*11

以上方法远远比"试除法"麻烦.
当我试图尝试用RHO方法来分解更大的数的数时,比如99400891(=9967*9973) 时,却失败了.
因为我的计算器位数才9位.运算常出现溢出错误.手工计算又不能保证无误.
缺少工具啊.
看来:牛刀未必适合杀鸡,杀鸡刀也未必适合宰牛.选择的时候只要适合既可.[/watermark]