[原创]RSA公钥密码的破解

ysr

当然这个法只能用来判断是否是素数，不能用来分解因数，要分解n，还要用到其他方法。

ysr

RSA密码的原理和方法的逆命题，可以用来判断一大数是否是素数，如：6958000001674999998647是两个11位的素数的积，经判断为合数。而2^89-1=618970019642690137449562111，经判断是素数有27位。

ysr

这个判断比常规法快的多。

ysr

45367929763334872117245196642377832066594422737383这是素数有50位，
8548077248145782626619300287299705673980083387922967这是素数有52位，
3535000647287053716310161223639238642910682574781777736223167这是合数有61位

ysr

经过实验，大于5位的整数的判断是正确的，小于5可能前面的原理就失效了，因为我们用的明文已经是3位的，（小于3位的是否能用是否还准确，不知道有待研究），用小于3位的如7，11，13，97等做公开模数，来判断的话，还原不出3位的明文，因为明文是余数，小于3位的模数（或者说是除数），余数不能是3位的，所以原理失效，（还原不出来明文就被判定为合数，而实际这几个例子（7，11，13，97）都是素数，所以此时输出结果错误）而大于5位的都成立！5位以下的用常规法已经可以快速分解和判断了，所以这个法对于大整数的判断还是有效的，有价值的。（经过验证大于11位的有效，判断是准确的，小于11位的就是10位以内的用常规法）

ysr

999999999977779这是素数有15位，这个判断素数速度比较快，挺好玩的程序。
23这是一个质数
233这是一个质数
2333这是一个质数
23333这是素数有5位
233333=353*661
2333333=19*227*541
23333333=17*1372549
233333333=29*47*193*887
2333333333=10163*229591
23333333333这是素数有11位
233333333333是合数
2333333333333是合数
23333333333333是合数
233333333333333是合数
2333333333333333是合数
23333333333333333这是素数有17位
233333333333333333是合数。(18位)
23333333333333333333333这是素数有23位。
23333333333333333333333333333333333333333333333333333是合数有53位。
233333333333333333333333333333333333333333333333333333这是素数有54位。

ysr

下图中是我的程序对22位的整数的分解，用常规法很费力的，此法道是快速方便，若是用到快速乘法除法程序则更快，能分解的整数就更大。
对22位的整数用费马分解法等方法也可以分解但步骤和计算量太大，必须用大整数的快速乘法除法才能出结果，这个方法则计算量稍小一些。
只是咱不会快速乘法除法，效率低，再大一些的就慢了，超过1个小时甚至是无法分解。而且只能分解成两个因子，是不完全分解法。

ysr

对这个22位的整数的分解程序运行了几秒钟时间，图片中显示了中间数据，当程序运行调试好以后就不必显示中间数据了。

ysr

19748381714759701=99368963*198737927，这是两个关联素数的积，很容易分解的。

ysr

56楼及58楼的例子中的p小于实际，B=B*η，其中η<1，F越小η越接近1，而当p大于实际呢？B=B*η，此时η>1，F越小越接近1，方程变为：（p-F）（2B+1）F=qF+r，整理得：
-（2B+1）F^2+（（2B+1）p-q）F-r=0.
η对每个F的值是不一样的，实际可以估计个值，理论上η要精确到点后的位数等于p的位数，实际我们采用点后3或5位即可。如η=0.618或η=1.618，这时F的值就会很大的，实际验证F的值不用很大，因为当B的整数部分等于实际的时候，p的值的最高位有至少2位是等于实际，的，所以，η的值要实际验证后确定，要让大多数的整数能够分解了，F值越接近实际试除的越少越能快速分解，所以η要选择适当的值。