日前山东大学有破解小组找到了一种简单的快速分解素因数的方法，该方法可以用于RSA的解密。我们知道使用广泛的加密算法RSA的安全性基于对大合数的分解有足够的困难。如果寻找到大合数的素因子分解的高效算法RSA将毫无招架之力。
其实在印度理工学院的马宁德拉.阿格拉瓦发现简单的素数判定方法的时候，很多数学工作者就担心可能忽略了很多重大数学问题的简单解决方法，可能存在简单的素因子分解算法，只不过我们还没有发现罢了。这次山东大学信息科学与工程学院的季凯和他的破解团队成员刘强等人宣布找到了这样的一种快速素因子分解算法，并且公布了算法。下面是他们公布算法的简单介绍（是我经过稍微整理的，省略了一些证明，这些证明其实都是很容易证出，如果你对这算法有兴趣我建议你读慢点读仔细点我不敢说别的但是很有发现是肯定的！！）：
已知一个大合数n(n=pq p,q均为大素数),如果能找到另一个数m(m<n),并且使m于n有除了1以外的公约数，很显然这个公约数肯定是p或q。那么分解大数n的问题可以转化成求n与m的最大公约数。由于求最大公约数的效率是很高的，所以该算法的核心是寻找数m的效率。该破解小组提供了一种能通过n快速求解m的算法。下面是该算法的过程：
已知一个数n为两个素数的乘积，首先将n转换成二进制。下面我们以1101和1011为例来看一下,先来看一下二进作乘法的过程。
1011
* 1101
————
1011
0000
1011
+1011
————
10001111
这是计算乘法的基本方法10001111是n，我们可以把求1011与1101的积看成是求1011、00000、101100、1011000相加。即：
1011 （第一行）
00000 （第二行）
101100 （第三行）
+ 1011000 （第四行）
————
10001111 式1
根据这个式子我们可以证明 式1（证明略）在任何一行做加法或减法与直接在结果上做加法或减法是等价的，例如在第一行1011处减1即1011-1=1010，式1变为：
1010
00000
101100
+ 1011000
————
10001110
10001110=10001111-1。
若在第一行减掉1111即1011-1111=-100,式1变为：
-100
00000
101100
+ 1011000
————
10000000
10000000=10001111-1111。
构造m的第一步是猜解p和q的长度，由于我们不知道p和q的长度所以只有使用穷举法测试，可以证明这个情况并不复杂。现在我们直接看猜解到p为4位q也为4位的情况，知道p和q的长度可以构造这样的一个数，p位的数且每一位的值都为1（本例中为1111）和q位的数且每一位的值都为1（本例中为1111）的数的乘积，即：
1111
* 1111
————
1111
1111
1111
1111
————
11100001
用这个数1110001减去10001111，可以看作1111*1111的一行减掉1011*1101的对应的一行然后把结果相加（证明略），即1110001-10001111为：
100
1111
100
+ 100
————
1010010 式2
凡是式1中全为0的行在式2中变为全是1（证明略）。
将这个数乘以10即1010010*10=10100100,这个过程可以看作式2在每一行中的后面都添0（证明略），即：
1000
11110
1000
+ 1000
————
10100100
我们现在在第一行减去1111，在第2行减去11110，在第n行减去1111（跟n减一个0），即
-111
1111
-111
+ -111
————
-1011011 式4
这个式子的值根据上面的内容我们知道其等于10100100-1111-11110-111100-1111000=-1011011
我们可以看到式3中的第2行即1111与式2中的第2行是一样的，因为如果一个二进制的数在末尾添零就相当于该数乘以10（二进制）。在该数后面添零减掉该数结果一定等于该数（如11110-1111=1111），若减掉的不是该数则结果一定不为该数（证明略）。
现在我们将式4在进行一次和变换即在第一行减去1111，在第2行减去11110，在第n行减去1111（跟n减一个0），经过两次变换（可以证明一定要进行两次以上的变换才能保证下面的运算成立 证明略）后即为：
-10110
1111
-10110
-10110 式5
现在用式2减掉式5（由于所有数每一位都为1的行经过变换后不发生改变，实际作减后上我们得到了与式1结构相似的一个式子 证明略）即：
10010
0000
10010
+ 10010
————
11101010 式6
用式6的结果和式1的结果，以大数减掉小数所得的差如果比式1的结果小则这个差就是m,如果这个差比比式1的结果大，再用该差和式1的结果作减，直到差小于式1的结果，这个差就是m（证明略）。然后求n与m的最大公约数就可以分解n得到p或q.
式6和式1的结果作减11101010-10001111=1011011，1011011与10001111有最大公约数1101！
这个算法我已开始看起来也有些乱，但仔细一分析发现这个算法是有效的！！！！至少在我看来！！
我不知道这样贴出来这个算法是不是正确的做法，希望是我的水平太低没有看出中间还存在的什么问题，我很担心这个东西。或许像前一段时间山东大学的王小云教授找到凑MD5值一样，可能RSA也要被山东大学破解了吧，或许今年真是一个山东大学密码年吧！我也希望看到这篇帖子的人不要乱用这种算法，不管怎么样觉得那样做是极不道德的和极不负责任的，现在知道这个算法的只有很少很少的一些密码界的人士，我不想说我是谁，现在我心里也很矛盾现在是凌晨.....最终我还是决定将他公布出去，最后再透漏一下吧他们的信箱是[email protected]和[email protected]，需要完整论文的可以和他们联系吧。我想再说一遍希望不要用这个算法作除了测试以外的任何事！！否则后果自负！
本文地址：http://com.8s8s.com/it/it32975.htm