对Shor算法破解RSA的探讨

作     者：凃玲英 胡一凡 张洪涛 代永涛 熊红梅 TU Lingying;HU Yifan;ZHANG Hongtao;DAI Yongtao;XIONG Hongmei

作者机构：湖北工业大学纳米电子技术与微系统实验室湖北武汉430068 湖北工业大学电气与电子工程学院湖北武汉430068 

出 版 物：《华侨大学学报（自然科学版）》 (Journal of Huaqiao University(Natural Science))

年 卷 期：2015年第36卷第6期

页      面：640-644页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：湖北省武汉市科技局"十城千辆新动力汽车计划"项目(2013011801010600) 

主　　题：Shor算法 非完全平方数 RSA算法 公钥密码体制 蒙特卡洛法 

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