对 Shor 算法破解 RSA 的探讨

• 作者: 代永涛 凃玲英 张洪涛 熊红梅 胡一凡
• 来源期刊: 华侨大学学报（自然科学版）
• 关键词: Shor 算法 非完全平方数 RSA 算法 公钥密码体制 蒙特卡洛法
• 年，卷（期）: 2015,（6）
• 页码范围: 640-644
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.11830/ISSN.1000-5013.2015.06.0640

摘要

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