摘要
分解大整数的困难程度是RSA公钥密码的安全基础,量子退火破译RSA密码与Shor算法有着本质性的不同,将整数分解问题转化为组合优化问题,利用D-Wave量子退火特有的量子隧穿效应跳出局部亚优解.本文提出一种新的分布式量子退火整数分解算法,将任意整数转变为D-Wave量子计算机可执行的稳定性Ising模型的框架.Ising模型局部场系数h、耦合项系数J的稳定性和取值范围是影响到整数分解成功率的重要因素,与普渡大学Jiang等人的算法相比,本文算法在降低使用的逻辑比特数的同时,参数h,J降低程度达到60%和40%以上,且Ising模型系数取值范围稳定;与洛克希德·马丁公司Warren的算法相比,在保证可以达到Ising模型稳定的情况下,本文算法参数h,J从10^6降低到10^2数量级.此外,Warren为了证明其提出的算法的正确性,遍历分解1000以内的整数,本文的算法遍历10000以内的整数,均成功分解.本文算法实验结果超过了目前Shor算法、普渡大学Jiang等人和洛克希德·马丁公司Warren公开文献最大分解规模.
The difficulty in factoring large integers is a security basis of Rivest-Shamir-Adleman public key cryptography.Quantum annealing,a completely different method as compared with that of Shor’s algorithm,can transform an integer factorization problem into a combinatorial optimization problem using the quantum tunneling effects of D-wave quantum annealing to leap from local minima.In this paper,a new distributed integer factorization algorithm based on quantum annealing,which transforms an arbitrary integer into a stable Ising model executable using a D-wave quantum computer,is proposed.The stability and range of the local field coefficient h and the coupling term coefficient J of the Ising model are important factors that affect the success rate of integer factorization.Compared with the algorithm of Purdue University’s Jiang et al.,the proposed method reduces the number of logical bits and the parameters of h and J by more than 60% and 40%,respectively,and the ranges of the coefficients of the Ising model are stable.Compared with the algorithm of Lockheed Martin Warren,the parameters of the proposed method are reduced in the orders from 10^6 to 10^2 of magnitude when the Ising model is guaranteed to be stable.In addition,to prove the correctness of the algorithm,Warren traversed factorization within 1000 integers.The proposed method traverses all integers within 10000 and all of them are successfully factored.The experimental results of this paper exceed the results of Shor’s algorithm,Jiang’s algorithm and the maximum published factorization scale of Lockheed Martin Warren’s algorithm.
作者
王宝楠
姚皓南
胡风
王潮
WANG BaoNan;YAO HaoNan;HU Feng;WANG Chao(Key Laboratory of Specialty Fiber Optics and Optical Access Networks,Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication,Shanghai Institute for Advanced Communication and Data Science,Shanghai University,Shanghai 200444,China;State Key Laboratory of Cryptology,Beijing 100878,China;Center for Quantum Computing,Peng Cheng Laboratory,Shenzhen 518000,China)
出处
《中国科学：物理学、力学、天文学》
CSCD
北大核心
2020年第3期127-137,共11页
Scientia Sinica Physica,Mechanica & Astronomica
基金
国防创新特区项目
国家自然科学基金(编号:61572304,61272096,61332019)
密码科学技术国家重点实验室开放课题基金资助
关键词
RSA
量子退火
分布式
RSA
quantum annealing
distributed
