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

重生888

下面引用由天山草在 2011/11/12 09:27pm 发表的内容：
怒直言，我看没戏。程序是能编成的，只是在运行速度上太慢，没有实用价值。
用十几位、几十位的数字来检验，没有什么意思。300 位以上，还差不多。

老师好！您的话我是相信的！不过我是这样孬想：第一步将要分解的数做一下简单处理：
(30n+17)*(30m+31)=695800000167999998647
900nm+930n+510m+527=695800000167999998647
30(30nm+31n+17m)+17=30(23193333338933333280)+17
30nm+31n+17m=23193333338933333280
第二步对以上等式的n或m=0 1 2 3........求n或m 的整解！这样的程序慢吗？如果不是太慢，得整解确定是合数，没有整解就是素数！恳求老师回复，谢谢！
[br][br]-=-=-=-=- 以下内容由 重生888 在 时添加 -=-=-=-=-
没有整解就停，再掉头！.......

天山草

[这个贴子最后由天山草在 2011/11/13 10:12am 第 3 次编辑]

对(30n+17)*(30m+31)=695800000167999998647
或 900nm+930n+510m+527=695800000167999998647
求整数解，运行速度会慢得不可思议。
现代软件分解下面这个数（把上面的数四次排队）695800000167999998647695800000167999998647695800000167999998647695800000167999998647，仅用时 0.2 秒，结果是 {{7, 2}, {11, 1}, {13, 1}, {29, 1}, {101, 1}, {109, 1}, {127,1}, {281, 1}, {2689, 1}, {9901, 1}, {226549, 1}, {459691,1}, {909091, 1}, {121499449, 1}, {4458192223320340849, 1}, {6383486240073394483, 1}
原数进行八次排队（168位），分解用时为43秒，结果是：
695800000167999998647695800000167999998647695800000167999998647695800000167999998647695800000167999998647695800000167999998647695800000167999998647695800000167999998647 = 7×7×11×13×29×73×101×109×127×137×281×2689×7841×9901×226549×459691×909091×99990001×121499449×11189053009×603812429055411913×4458192223320340849×6383486240073394483×127522001020150503761×148029423400750506553
由此可见，“土办法”差距太大，思路不对。[br][br]-=-=-=-=- 以下内容由 天山草 在 时添加 -=-=-=-=-
如果分解一万位的大数，“洋办法”也无能为力了，可见破解 RSA 密码之难。再说，他的密码可能是一天一换，让你没有时间进行分解——虽然国家情报局的电脑比民间电脑厉害得多，那也是不行的。等到你行的时候，他会把数字弄到 100 万位。

重生888

下面引用由天山草在 2011/11/13 09:40am 发表的内容：
对(30n+17)*(30m+31)=695800000167999998647
或 900nm+930n+510m+527=695800000167999998647
求整数解，运行速度会慢得不可思议。
现代软件分解下面这个数（把上面的数四次排队）695800000167999998647695800000 ...

知道了，谢谢老师！

ysr

感谢各位老师关注!方法对了,经过努力就可能成功!

ysr

感谢老申鼓励!
对于太大的可把细化公式就是最后结果返回初始位置,迭代,就可快速得到误差范围内的实际素因数

任在深

要求的是速度！
必须把 2ˆn提高到幂指数 nˆi.
    那就需要解决 P=NP的问题！
    即找出一个适用的数学结构式。

ysr

感谢申先生鼓励!你的公式若成立且能编称的话,就是真正的多项式时间,如果得到承认那就了不起!
上述方法只有在特殊值时是多项式分解,此法较多项式法多了在精确度范围搜索实际因数的时间，事实上如果精确度达到要求，仅试除末尾8位数,余数为0时，就是实际的素因子，精确度不够只能扩大范围或不扩大而漏掉了实际因子，可见，只要精确度达到了，接近多项式时间，而精确度可以通过迭代和穷举法等提高。

ysr

(对试除末尾数段的技术处理）
1，对倒数第2次商值的余数的处理（以8位1段分段为例）：我们把第1次除完除数数段所得商值叫1次商值，仅高位数段相同的试除因子改变，而高位段余数不加处理就用于试除不同数段是错误的，可能使任何因子的余数不为0，就找不到实际因子了，当从小因子开始往大处实验时，每增加1个因子比前1个多2，余数等于少减掉商值的2倍，所以余数比实际大，要减掉商的2，4，6，8，……倍，才能做为实际余数；若从大到小实验，则加上商的2，4，6，8，……倍。
2，末尾数段商的处理：由于试除因子增加2，则商减小2B，而相同位数的因数的积B=4，2B=8，8乘以末尾8位数，则得9位数，B增大或因子再增大商变化更大，所以倒数第2次商值是不对的，至少末尾2位数不对，不加处理商不正确，除完末尾数段所得实际商必须是1个数段，超过1个数段的，把高位数段与前面的商相加，这样才正确，如末尾商为
   16 5000 0000超过1段，把16与前面商相加，还可以这样，在找到实际因子时，用它去除公开模数n，得到正确的商。
这样做比起设想的，仅试除末尾数段消耗时间，但比依次重新试除全部数段节约时间。

ysr

(对试除末尾数段的技术处理举例调整如下）
举例：14585113/975=14959余88，14585113/993=14687余992，14585113/997=14629余0，14585113/1097=13295余498，以2位为1段分段试除演示如下：
被除数3段除以除数2段，145851/975=149余576，145851/993=146余873，145851/997=146余289，145851/1097=132余1047，
997-975=22，997-993=4，1097-997=100，
576-22*149=-2702，-270200+13=-270187，-270187/997=-271余0，商为14900-271=14629，
873-4*146=289，28900+13=28913，28913/997=29余0，商为14600+29=14629，
1047+100*132=14247，1424700+13=1424713，1424713/997=1429余0，商为13200+1429=14629，
可见，由于倒数第2商随因子不同有差别，从小到大算，余数和商会为负值，从大到小算，商会超过1段，为了消除此弊端，上述技术处理可调整为：
  算到倒数第3商值及余数，进行处理！
可见，细节处理不当会使计算机运算错误无法调试，细节处理参见《大整数的整除及求余》，称序员可据自己对大整数的运算经验另外处理，只要正确且更快！
感谢关注,欢迎探讨!

ysr

收到火花的退稿信:
ysr2857  先生/女士：您好！
       首先，感谢您对本栏目的关注！
       经过审阅，我们认为您的来稿不符合本栏目的定位和要求，因此予以退稿。
               
                                                                     此致
敬礼！
                                                                                 《科学智慧火花》编辑组
                                                                                             2011年11月28日