对 Shor 算法破解 RSA 的探讨

摘要：

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

关键词：Shor 算法、非完全平方数、RSA 算法、公钥密码体制、蒙特卡洛法

分类号：TP301.6(计算技术、计算机技术)

资助基金：湖北省武汉市科技局“十城千辆新动力汽车计划”项目2013011801010600

在线出版日期：2015-11-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：640-644