[趣味]素数小题

ysr

[这个贴子最后由ysr在 2012/04/30 10:08pm 第 1 次编辑]

已知30000内的1个最大素数，加上它的2倍减4是个素数，求这两个素数的积，问类似这样的15位或30位以上的合数，你能在几分几秒内笔算分解因数吗？也可以用电脑自带的计算器，可算30位的有效数字！

ysr

主楼写错,已改过来,请感兴趣朋友试验!

ysr

[这个贴子最后由ysr在 2012/05/04 01:35pm 第 2 次编辑]

问题答案,2素数是29989和89963,积为29989*89963=2697900407,
此类合数容易分解,可用如下简单方法:
  法1:解2次方程法,
例:M=2697900407,
  据题意的方程P*(3P-4)=2697900407,
解得P=29989,当然用求根公式会得2个根,负值舍去,实际不用求根,两边同除以3得,
P^2-4*P/3=2697900407/3,可知左边符合  非平方数公式,我们要的是方根的整数部分,非平方数的方根的整数部分与公式1次项无关,但左边中间为-号,P^2与P^2-4P/3是非同一组相邻数,方根的整数部分差1,所以,方根为P-1,所以有,
P-1=√(2697900407/3)=29988,
看,如此简单,就是笔算开方也不会超过3分钟!
   法2:特殊类型法,
例,M=2697900407,
由题知B=1,那令B=1,则有,
  D=2697900407/4=674475101.75,
N=√(D/(2B+1))=√(674475101.75/3)=14994(取整数)
2N+1=29989,
  法3:经验公式法,
例,M=14585113,
  D=M\4=14585113\4=3646278,
√M=√14585113=3819,
2N+1=D/√M=3646278/3819=954.77=955,(这个就是经验公式,原理及推导过程略),
商=14585113/955=15272.369633507853403141361256545,
X=(15272.369633507853403141361256545-955)/4=3579,
N=955/2=477,
B=X/N=7.5031446540880503144654088050314,
代入细化公式及修正值公式得出F值,从而得新的试除因子,细化公式相当于解如下方程,
  (955+2*F)(15272-4*7.5*F)=14585113,
解得F=31,(另1根0舍去),则有,955+2*F=955+62=1017,
求修正值数据,H=X-F*B-(M/(2N+1)-(2N+1))/4=3579-31*7.5-(14585113/1017-1017)/4=3579-232.5-3331=15.5,
误差虽小,也可以修正试除因子,公式,新因子=M/(商+4*H)=14585113/(14341+4*15)=1012,
与实际更近了些,还有如下公式可能效果更好,
新商=14585113-955*15272+15*955=14678,
新因子=M/新商=14585113/14678=993,
与实际997差4,实际14585113=997*14629,
新因子可以代入上面初始公式循环,即所谓的迭代,这样误差越来越小,至达要求的精确度或误差为0,对于接近实际的因子是有效且有利的,离实际太远的不行,不能无限循环,迭代是有限的,
  
以上为B值较小的类型,双因子的RSA公钥密码的公开模数属于此类,所以容易分解,多因子RSA的公开模数的B的值很大,要迭代,穷举,等才能找到接近实际的因子!
本来想那位编辑给优化程序或指点1下,谁知道那些猪头不会脑筋急转弯,非要往墙上撞呢?!
   

ysr

[这个贴子最后由ysr在 2012/05/04 01:39pm 第 1 次编辑]

误差修正值公式是很重要的,据原稿改过来了,(可见RSA密码的破解1文),希望朋友批评指导!如何编程?请高手指点!谢谢!!

ysr

有 无 有 参考 价值 ？？ 希望 朋友 指点 ！！

ysr

该法是RSA密码破解的简化版,请朋友指点!

ysr

欢迎朋友指导!