对Shor算法破解RSA的探讨

针对Shor算法具有随机性,会导致破解RSA公钥密码体制成功率不高的问题,对Shor算法原理、RSA公钥密码体制特点和大量计算结果进行分析,提出量子函数式f(x)=a^xmod n对a值的随机选取是有规律的.结合数论知识和蒙特卡洛法证明,结果表明:随机数a取完全平方数,所求周期r很可能不满足Shor算法要求;a取非完全平方数可以提高Shor算法破解RSA的成功率.

Discussion on Cracking RSA With Shor Algorithm

Since the randomness of Shor algorithm could lead to low success rate in cracking RSA. By analyzing the principle of Shor algorithm, characteristics of RSA public key password system and lots of data, the view that the way for quantum functional in randomly selecting value is regular was putting forward.Verified by number theory and Monte Carlo method, the results showed that if takes a perfect square, the cycle probably can’t meet the requirements of Shor algorithm. It comes to a conclusion that take a non-perfect square can improve the success rate of Shor algorithm in cracking RSA.