第40卷 计算机学报 Vol.402017论文在线出版号No.58 CHINESEJOURNALOFCOMPUTERS OnlinePublishingNo.58———————————————2017-04-28. 本课题得到国家自然科学基金资助重点项目(61332019);国家重点基础研究发展规划项目(973计划)(2014CB340601);国家自然科学基金资助项目(61303212,61202386);国家自然科学基金资助重大项目(91018008)资助.王亚辉，女，1988年生，博士研究生，主要研究领域为量子计算，密码学，E-mail:wangyh_ecc@whu.edu.cn联系电话：15997497518. 张焕国，男，1945年生，博士，教授，博士生导师，计算机学会(CCF)会员(e200005823s)，主要研究领域为信息安全，密码学，可信计算，E-mail:liss@whu.edu.cn. 吴万青，男，1981年生，讲师，主要研究领域为信息安全，量子密码，E-mail:wuwanqing8888@126.com.韩海清，男，1979年生，博士后，主要研究方向为密码学，量子计算。基于方程求解与相位估计攻击RSA的量子算法王亚辉1，2张焕国1，2吴万青3韩海清1，21.武汉大学计算机学院,武汉4300722.空天信息安全与可信计算教育部重点实验室,武汉4300723.河北大学计算机科学与技术学院，保定071002摘要量子计算的发展对现有的公钥密码体制提出了严峻的挑战，利用Shor算法就可攻击公钥密码RSA，ELGamal等。因此，研究量子计算环境下的密码破译就有重大意义。经典的因子分解算法是通过求解同余方程 ( ) n   mod2 2b º a 实现的。据我们所知，目前还没有求解此方程的量子算法，故我们试图从量子的角度提出解决此同余方程的量子算法1。该算法是对经典求解同余方程 ( ) n   mod2 2b º a 的量子化实现。相比于Shor算法，算法1所需量子位少，具有亚指数时间复杂度，且成功概率接近于1。为了降低时间复杂度，我们从非因子分解角度出发，基于量子Fourier逆变换和相位估计，给出了算法2。同Shor算法相比，算法2不需要分解n而从RSA密文C直接恢复出明文M，具有多项式时间复杂度，且成功概率高于Shor算法攻击RSA的成功概率，同时不必要满足密文的阶为偶数。关键词 信息安全；密码学；RSA密码体制；量子计算中图法分类号P301论文引用格式：王亚辉,张焕国,吴万青,韩海清,基于方程求解与相位估计攻击RSA的量子算法,2017,Vol.40,在线出版号No.58WangYa-Hui,ZhangHuan-Guo,WUWan-Qing,HanHai-Qing,QuantumAlgorithmsforBreakingRSAbasedonPhaseEstimationandEquationSolving,2017,Vol.40,OnlinePublishingNo.58QuantumAlgorithmsforBreakingRSAbasedonPhaseEstimationandEquationSolvingWANGYa-Hui1，2ZHANGHuan-Guo1，2WUWan-Qing3HANHai-Qing1，21.ComputerSchool,WuhanUniversity,Wuhan,4300722.KeyLaboratoryofAerospaceInformationSecurityandTrustedComputingMinistryofEducation,Wuhan,4300723.SchoolofComputerScienceandTechnology,HebeiUniversity,Baoding,071002Abstract Thedevelopment of quantumcomputationpresents aserious challengetotheexistingpublic-keycryptosystems, andthepublic-keycryptosystems, RSA, ELGamal, etc. arebrokenbyusingShor’salgorithm.网络出版时间：2017-05-10 12:10:54网络出版地址：http://kns.cnki.net/kcms/detail/11.1826.TP.20170510.1210.002.html2 计算机学报 2017年Therefore, it is of great significancetostudythecryptanalysis inthequantumcomputingenvironment. It iswell-knownthat theRSApublic-keycryptographydependsessentiallyonlyonthecomputational intractabilityoftheIntegerFactorizationProblem(IFP), soobviously,themostdirectmethodtoattackRSAistosolvetheIFP.IfIFPcanbesolvedinpolynomial-time, thenRSAandmanyothercryptographicsystemscanbebroken.However,thecurrentlyexistingfastest integerfactorizationalgorithmuptodateistheNumberFieldSieve, whichrunsinsubexponential-time. Surprisingly, theworldwas astonishedwhenShor announcedin1994that he foundaquantumintegerfactorizationalgorithmwhichcansolveIFPandbreakRSAbothinpolynomial-time.Sincethen,variousimprovedandcompiledversionsof Shor’salgorithmusingdifferent technicshavebeenproposedandstudied, inshort, thereistwoimportantresearchdirectionsinquantumintegerfactorization:1.Builda(practical)quantumcomputerorevenothertypesofphysicalcomputerstoimplementthefullversionorcompiledversionofShor’salgorithm.2. Improve,modifyandsimplyShor’soriginalalgorithmoreveninventnewquantumfactoringalgorithmstoberunonquantumcomputerswithfewerquantumbits.Therefore, therearetwoaspectsthatneedtobeimproved. Oneisthathowtopresent aquantumalgorithmforbreakingRSAwithfewerqubits. Theclassicalfactorizationalgorithmis realizedbysolvingthe congruent equation ( ) n   mod2 2b º a . However, tothe bestknowledgeoftheauthors, thereisnoquantumalgorithmforsolvingthisequationtill now. SowearetryingtogivequantumAlgorithm1tosolvethisequationfromthequantum’spointofview,whichistheimplementationof quantizationof the classical quantumalgorithmfor solvingthe congruent equation. ComparedtoShor’salgorithm,Algorithm1requiresfewerquantumbits,withsubexponential-timecomplexity.Moreover, thesuccessprobabilityiscloseto1. Another isthat howtodesignthecompiledversionof Shor’salgorithm. Inorder toinducethetimecomplexity, fromthepoint ofviewofnon-factorization, basedonthequantuminverseFouriertransformand phase estimation, a polynomial-time quantumAlgorithm2 for directly recovering the RSAplaintextMfromtheciphertextCwithout explicitlyfactoringthemodulusnispresented, andhence, breaksthefamousRSApublic-keycryptosystem. ComparedtoShor’salgorithm, Algorithm2directlyrecoverstheRSAplaintext M fromtheciphertext , Cwithout factoringthemodulusn; theorderoftheciphertext Csatisfying( ) n Cr  mod 1 º doesnotneedtobeeven;andthesuccessprobabilityofAlgorithm2ishigherthanShor’s.Keywords:informationsecurity;cryptology;RSAcryptography;quantumcomputing1引言量子计算的发展对现有的公钥密码体制提出了严峻的挑战,利用Shor算法就可攻击公钥密码RSA，ELGamal等。因此，研究量子计算环境下的密码破译就有重大意义[1]。RSA[2]是目前信息安全领域应用广泛的公钥密码体制，其研制者Rivest，Shamir和Adleman获得了2002年图灵奖。RSA的加密和解密过程如下：( )( )îí캺n C Mn M Cde  mod  mod  满足( ) ( ) n ed f º   mod 1 (1)其中M是明文，C是密文，e是加密指数，d是解密指数， pq n= 是模数，且 q , p 是素数，f是欧拉函数。众所周知，RSA密码体制的安全性是基于整数分解问题的困难性[3]。之所以RSA密码体制难以破译，就是因为它所依赖的数论问题不能快速解决。目前最快的经典整数分解算法是数域筛法[4,5]，其复杂性是 ( ) ( )( ) ( ), n n c O/ / 3 2 3 1  log   log   log exp 其中 。 92 1. c»因此这仍是一个亚指数复杂性算法，仅适合于分解200个十进制位左右的整数。迄今为止，利用数域筛法分解的最大的数是RSA-768（768个二进制位，232个十进制位）。显然，破译RSA最直接的方法就是解决整数分解问题。因此，全世界的密码分析者的目光都集中论文在线出版号No.58 王亚辉等：基于方程求解与相位估计攻击RSA的量子算法 3在如何快速解决整数分解问题。1994年，美国出现了轰动世界的重大科学发现，美国电话电报公司的研究员Peter Shor提出了一个快速的量子算法[6,7]，它可以在多项式时间内解决整数分解问题，可攻破RSA。Shor算法的主要思想是把整数分解问题转化为求元素*Z Îna 模n的阶问题，通过计算( ) n , a/ r1 gcd2± 就能以 ( ) r / r24 p f 的概率得到n的因子。Shor算法的提出给量子计算的研究注入了新的活力，引发了近二十多年来人们对量子计算和量子计算机研究的热潮[8-15]。经典的因子分解算法大都是通过求解同余方程 ( ) n   mod2 2b º a 实现的，也即找到正整数对( ) b a, 使得 ( ) n   mod2 2b º a 且 ( ) n   mod b ¹ a 成立。一旦找到正整数对( ) b a, ，就可以通过计算 ( ) ( ) q , p n , = b ± a gcd 得到模数n的因子 。 q , p 进一步可以得到公钥密码体制RSA 的密钥 ( )( ) ( ) 1 1   mod 1 - - º q p e / d ,从而攻破RSA公钥密码。据我们所知，目前还没有对此方程求解的量子算法，故我们试图从量子的角度做一个尝试。基于Grover搜索[16,17]，本文给出了同余方程 ( ) n   mod2 2b º a 的量子求解算法。这是本文的一个创新点。虽然该算法的计算复杂性是亚指数的，但这是第一个求解同余方程 ( ) n   mod2 2b º a 的量子算法。算法所需要的量子位数比Shor算法所需要的量子位数少，且算法的成功概率接近1。众所周知，如果整数分解问题得以解决，那么我们就可攻破RSA；然而，攻破RSA却不一定要通过解决整数分解问题。因此我们可以考虑从非因子分解角度出发，通过计算密文C的阶，达到恢复明文M的目的。即不用通过分解模数n也能攻破RSA。基于量子Fourier逆变换和相位估计，提出另一个攻击RSA的量子算法。该算法避开了Shor算法的元素的阶必须为偶数和因子是n的非平凡因子这两个要求，不需要分解n而从RSA密文C直接恢复出明文 。 M 算法的成功概率大于Shor算法攻击RSA的成功概率。文章主要讲述的内容为：第2节介绍Shor算法攻击RSA的国内外研究现状；第3节介绍了与RSA密码分析有关的基础知识以及Shor算法对RSA的攻击；第4节分析经典的分解算法，并提出了基于方程求解攻击RSA的量子算法；第5节基于相位估计提出了一个攻击RSA的量子算法，并进行算法分析，该算法不通过分解模数n；第6节，总结与下一步工作。2相关工作Shor算法对RSA的攻击体现在Shor算法对RSA的安全基础的大数n的分解，关于Shor算法对n的分解的研究一直是国内外专家学者的研究热点。研究者们利用各种不同的技巧，提出了Shor算法的不同编译版本（compliedversion）。比如，2001年，文献[18]利用核磁共振技术演示了Shor算法对15的分解实验，但该实验不能很好的显示其量子属性，也无法扩展到更多的量子比特，从而分解更大的数，限制了进一步的研究。2007年，文献[19]在研究Shor算法的量子比特间残余耦合所产生的影响时，通过编写Quantware库并调用该库，用30个量子比特实现了 943 = n 的分解。该方法虽然理解容易，但是Quantware库的限制性却很多。同年，文献[20]在国际上首次利用光量子计算机实现了Shor量子分解算法，并在该量子计算机上成功操控了4个光子量子比特构造一个简单的线性光网络实现 15 = n 的分解。2008年，文献[21]首次提出了基于绝热量子计算的因子分解算法。相比于Shor算法，该算法利用的量子位少，并成功地在NMR量子处理器上实现了21的分解。2012年，文献[22]在[21]的基础上提出了一个改进的绝热量子算法，并利用核磁共振量子处理器实现了对143的分解。并且这是目前为止分解的最大的数。同年，文献[23]利用约瑟夫森电荷量子比特实现了Shor算法。并且最后利用3量子比特成功完成了对 15 = n 分解的物理实现。但它对物理属性要求很高，也就是说它需要在特定的物理条件下才能实现。2013年，文献[24]基于费马数的特性，利用8量子比特分解51和85，并给出了量子电路图。同年，文献[25]提出了一个量子分解新观点，通过寻找阶为2的元素， a实现对n的分解。因为元素的阶为2，则第二个寄存器只需要2个量子位，从而大大的减少量子位。总之，目前通过量子计算实现整数分解有两个主要的研究方向：4 计算机学报 2017年（1）建立实用的量子计算机或者其他类型的物理计算机，包括最快的D-Wave 2 量子计算机[18,19,20,22]。（2）研发Shor算法的改进版本。一方面是提出研发一些易于实现的所谓的“编译”版本。另一方面从减少量子位角度出发提出的改进算法[21,23,24,25]。3量子算法知识背景介绍3.1基础知识这节介绍与RSA密码分析有关的基础知识。定义1.（RSA 问题）[3]给定( )( ) ( )， 1 1   mod 1 - - º q p d / e ， pq n= ( )。 n M Ce  mod º求出M或者。 d定理1.设C是RSA的密文，记r为*Z ÎnC 模n的阶，则( )( )。 n C Mr e /  mod  mod 1º证明.因为r是*Z ÎnC 模n的阶，所以 ) n ( | r f又由 ( ) ( ) 1 gcd = fn , e 所以e与r互素，那么存在e模r 的乘法逆 ' d 。即 ( )。 r ' ed   mod 1 º 那么( ) ( ) n M' de  mod 是密文C对应的明文，即( ) n C M' d  mod º 因此有( )( ) n C Mr e /  mod  mod 1º 成立。证毕.引理1.[17]设mmp p na a= L11是一个正奇合数的素因子分解。如果*nZ中的一个元素x模n的阶r是偶数且 ( ) n x/ r  mod 12- ¹ ，那么 ( ) n , x/ r1 gcd2+ 或者( ) n , x/ r1 gcd2- 是n的一个非平凡因子。引理2.[17]设mmp p na a= L11是一个正奇合数的素因子分解。令x是在 1 1 - £ £ n x 内均匀随机选出的整数，且x与n互质，令r是x模n的阶，则( ) ( )m/ rn x r21- 1   mod   1 P2³ - ¹ 是偶数，且推论1.设 ， pq n= x是从[ ] 1 0 - n , 中随机选取的与n互质的整数，x模n的阶为， r那么利用x对n进行整数分解的概率为 。 4 3/ p³证明.由引理2知，此时 2 = m ，则( ) ( ) 3/421- 1   mod   1 P22= ³ - ¹ n x r/ r是偶数，且再由引理1可知：通过计算 ( ) n , x/ r1 gcd2± 可得到的n的非平凡因子，即为 。 q , p因此利用x对n进行整数分解的概率为。 4 3/ p³证毕.定义2. 量子Fourier变换（记为QFT）定义为，在一组标准正交基 1 1 0 - q , , , L 上的一个线性算子，在基态上的作用为å-=p®1021: QFTqkq / ijkk eqj那么对任意量子态的变换可写作k e x j xq / ijkqkqjjqjjp-=-=-=åå å ®2101010同样的，我们定义量子傅里叶逆变换（记为1QFT-）为，在一组标准正交基 1 1 0 - q , , , L 上的一个线性算子，在基态上的作用为å-=p - -®102 11: QFTqjq / ikjj eqk文献[17]给出了量子Fourier变换是可逆变换的证明，并且给出了其量子实现电路。3.2Shor算法对RSA的攻击1994年，Shor提出了量子整数分解算法[5,6]，其核心在于把因子分解问题转化成寻找函数的周期问题，从而利用量子Fourier变换求解周期问题。Shor算法攻击RSA的基本步骤大致如下：1.给定整数n，选择a和q，其中n是两个素数的乘积，*Z Îna 且 。2 22 2 n q nk< = £论文在线出版号No.58 王亚辉等：基于方程求解与相位估计攻击RSA的量子算法 52.给定两个量子寄存器，且初始化为零态0 00= Ψ3.对第一个量子寄存器执行Hadamard变换，得到叠加态01101 0 å-== ®qxxqΨ Ψ : H4.对第二个量子寄存器做模幂运算fU，得到( ) n a xqΨ Ψ : Uxqxf  mod1102 1 å-== ®其中 ( )， ： x f y x y x UfÅ ® ( ) 。 n a x fx  mod =5.对第二个量子寄存器进行观测。假设观测到 ( )， n a ml  mod º 此时第一个寄存器中的态也相应的坍缩到所有满足 ( ) n m ax  mod º 的x。此时第一个寄存器中的态为( ), r n l r l lnΨll+ + + + ++= L113其中ln是满足 1 2- £ +tnr l 成立的最大正整数。6.对第一个量子寄存器执行量子Fourier变换4 3QFT Ψ Ψ ® ：( )÷øöçèæ+ + + + ++= r n l r l lnllL11QFT÷øöçèæ++= å=lnjljr ln 0 11QFT÷øöçèæ++= å=lnjljr ln 0QFT11c eq nqcnjqc ) jr l ( illåå-= =+ p÷øöçèæ+=10 021117.利用连分数算法计算出r，然后判断r是否为元素a的阶。如果是，则算法结束，否则返回第1步，直到找到正确的阶r。8.如果r是奇数，重新选择a。如果r是偶数，则计算 ( ) ( ) q , p n , a/ r= ±1 gcd2。如果 1 ¹ q , p ，则q , p 就是的因子，否则重新选择a进行计算。9.计算( )( ) ( )( ) n C Mq p e /  mod1 1   mod 1 - -º ，即为RSA的明文，从而攻破RSA。Shor 量子分解算法总共所需量子位为é ùn   log 3 。Shor通过证明得出运行一次算法的成功概率为 ( ) r / r24 p f ,其中f是欧拉函数，r是a模n的阶，*Z Îna 。从而可以看出Shor算法的成功概率是依赖于元素a模n的阶r。定理2. Shor算法攻击RSA的成功概率为( ) ( ) r / r p r / rS2hor24 3 p f < £ p f 。证明.由上述知识可知：Shor算法运行一次得到元素x模n的阶的成功概率为 ( ) r / r24 p f 。又由推论1知：利用元素x模n的阶进行整数分解的概率为 。 4 3/ p³ 因此Shor算法攻击RSA的成功概率为( ) ( ) r / r p r / rS2hor24 3 p f < £ p f 。证毕.4基于方程求解攻击RSA的量子算法众所周知，目前还没有经典的多项式因子分解算法，而经典领域进行整数分解的基本思想是求出同余方程 ( ) n   mod2 2b º a 的解( ) b a, ，然后通过计算( ) ( ) q , p n , = b ± a gcd 得到n的因子。本节通过分析经典的分解算法，给出了对应的求解同余方程( ) n   mod2 2b º a 的量子求解算法。4.1经典算法步骤目前整数分解算法的基本思想：找到正整数( ) b a,使得 ( ) n   mod b ± ¹ a 且 ( ) n   mod2 2b º a 成立。一旦找6 计算机学报 2017年到整数( )， b a, 那么通过计算 ( ) ( ) q , p n , = b ± a gcd 得到n的因子 q , p 。经典的找到( ) b a, 最终求得n的因子的算法步骤如下：1.构建同余关系：构建如下的因子基FB{ }tp , , p , p L2 1FB= ，它由所有不超过y的所有素数构成。选择一个任意整数序列{ }rii 1 =a ，使得所有的ia满足( ) Õ== b º atjvj i ijp n12  mod ，其中jv是jp的指数。在这步的最后，{ }rii 1 =a 的子序列{ } r k ,ki'i< a=1和{ }rii 1 =b 的子序列{ } r k ,ki'i< b=1。这样就得到同余关系k , , , i , ptjij'i', jL 2 112i= = b = a Õ=v（2）对应的指数向量如下：( )( )( )ïîïíì===k v , , k v , k v kv , , v , vv , , , v , v, t , , , j, t , , j, t , , jLMLL2 12 12 12 2 2 21 1 1 1vvv（3）2.找乘方：由第1步的子序列{ }ki'i 1 =b ，找到一个新的子序列{ } k s ,si"i< b=1。如果 ( ) å£ ££ £ºs it j, ji12   mod 0 v 成立，那么就可以构成一个乘方22 1b = b b b"s" "L 。也就是说，由第1步的（2）和（3），得到s , , , i , ptjij'i', jL 2 112i= = b = a Õ=v（4）且对应的向量为( )( )( )ïîïíì===s v , , s v , s v sv , , v , vv , , , v , v, t , , , j, t , , j, t , , jLMLL2 12 12 12 2 2 21 1 1 1vvv（5）使得212÷øöçèæa = a Õ£ £ s i' 'i Õ£ £b =s i' 'i1Õ£ £å=£ £t jijs i, jp11vÕ£ £÷øöçèæå=£ £t jijs i, jp12121v当 ( ) å£ ££ £ºs it j, ji12   mod 0 v 成立时21212 1÷÷øöççèæå= a Õ£ £÷øöçèæ£ £t jijs i, jpv2b =因此， ， Õ£ £a = as i' 'i1。 Õ£ £b = bs i' 'i13.计算 ( ) ( ) q , p n , = b ± a gcd 。如上所述，经典的因子分解算法大都是通过求解同余方程 ( ) n   mod2 2b º a 实现的。还没有对此方程求解的量子算法，故我们试图从这个角度做一个尝试，提出解决此同余方程的量子算法，这是本文的一个创新点。具体算法见第4.2节。4.2量子算法设计4.2.1算法设计这节从量子计算的角度考虑如何实现同余方程 ( ) n   mod2 2b º a 的量子求解方法。算法1.基于方程求解攻击RSA的量子算法。输入：RSA模数n输出：一组满足同余方程 ( ) n   mod2 2b º a 的正整数b a,过程1.找到一组正整数( ) b a, 使其满足同余方程 ( ) n   mod2 2b º a 。1.找到tq 2 = ，其中 ë ûn t   log = 。2.对两个寄存器进行初始化： 0 00= Ψ 。3.对第一个寄存器执行H门变换，得到论文在线出版号No.58 王亚辉等：基于方程求解与相位估计攻击RSA的量子算法 701101 0 å-= aa = ®qqΨ Ψ : H4.对第二个寄存器进行模幂运算fU，得到( ) a a = ® å-= afqΨ Ψ Uqf102 11：( ) nqqmod1210a a = å-= a其中 ( )， ： x f y x y x UfÅ ® ( ) ( ) n x x f   mod2= 。5.重复步骤5.1--5.5 ) q ( O 次。5.1在第二个寄存器上执行条件相移变换OU，使得相同的态获得-1的相位移动，即3 2Ψ Ψ : UO®( ) ( ) nqqδn , nmod 11210  mod2  mod2a a - = å-= ab a其中假设同余方程 ( ) n   mod2 2b º a 的解对有m对，也即( )( ) ( ) { }m m, , , , , b a b a b a L2 2 1 1。为了方便书写，我们记为{ }。'm' ', , ,2 2 1a a a L OU表示算子 å=a a - =mi'i'i OI U212 。在此定义δ函数如下：ïîïíìb ¹ ab = a=b a. n n ,, n n ,δn , n  mod   mod 0  mod   mod 12 22 2  mod   mod2 2当当5.2在第二个寄存器上执行U变换，得到4 3Ψ Ψ U ® ： ( ) 0 1110  mod2  mod2å-= aa - =b aqδn , nq其中 ( ) n b b : U   mod2a Å a ® a 。5.3对第一个寄存器执行H门变换。5.4在第一个寄存器上执行条件相移，使t Ä0 之外的每个计算基态获得-1的相位移动。5.5对第一个寄存器执行H门变换。6.测量第一个寄存器。假设我们观测到态a，事实上由量子力学可知，满足 ( ) n   mod2 2b º a 的态 b a, 能够以相同的，较高的概率被观测到。但是当a被测量到时，b相应的坍缩，在这种情况下，我们需要进行过程2。过程2.找到同余方程 ( ) n a   mod2º b 的一个解b，其中2a = a 是由过程1得到的。1.找到'tq 2 = ，其中úùêé=2lognt'。2.对两个寄存器进行初始化： 0 00= Ψ 。3.对第一个寄存器执行H门变换，得到01101 0 å-= bb = ®qqΨ Ψ : H4.对第二个寄存器进行模幂运算fU，得到( ) b b = ® å-= bfqΨ Ψ Uqf102 11：( ) nqqmod1210b b = å-= b其中 ( )， ： x f y x y x UfÅ ® ( ) ( ) n x x f   mod2= 。5.重复步骤5.1--5.5 ) q ( O 次。5.1第二个寄存器上执行条件相移变换 'OU ，使得态a 获得-1的相位移动，即3 2Ψ Ψ U'O® ：( ) ( ) nqqδn , amod 11210  mod2b b - = å-= bb其中假设同余方程 ( ) n a   mod2º b 的解有'm个，不妨设为8 计算机学报 2017年{ } 'm, , , b b b L2 1。 'OU 表示算子 å=b b - =''mii iOI U12 。在此定义δ函数如下：ïîïíì¹ bº b=b. a n ,, a n ,δn , a  mod 0  mod 122  mod2当当5.2在第二个寄存器上执行U变换，得到4 3Ψ Ψ U ® ： ( ) 0 1110  mod2å-= bb - =bqδn , aq其中 ( ) n b b : U   mod2b Å b ® b 。5.3对第一个寄存器执行H门变换。5.4在第一个寄存器上执行条件相移使't Ä0 之外的每个计算基态获得-1的相位移动。5.5对第一个寄存器执行H门变换。6.测量第一个寄存器。假设我们观测到态b，如果b满足同余方程 ( ) n a   mod2º b ，则b是同余方程( ) n a   mod2º b 的一个解。事实上，我们以很高的概率观测到满足 ( ) n a   mod2º b 的b。因此，由过程1得到的a和过程2得到的b，我们就构成 ( ) n   mod2 2b º a 的解( ) b a, 。4.2.2算法分析定理3.设 pq n= ， q , p 是两个素数。如果整数对 b a, 满足同余方程( ) n   mod2 2b º a 且 ( )。 n   mod b ± ¹ a则n可以通过计算 ( ) ( ) q , p n , = b ± a gcd 得到因子q , p 。证明.因为 ( )， n   mod2 2b º a( )( ) ( )， n   mod 0 - º b a b + a Þ( )( )， b - a b + a Þ| n( )， 又因为 n   mod b ± ¹ a( ) ( )， 因此计算 q , p n , = b ± a gcd。 ， 也即 n q , p pq n < < = 1证毕.因此通过算法1，我们可以得到RSA模数n的素因子 q , p 。进一步，可以计算RSA密码体制的密钥 ( )( ) ( ) 1 1   mod 1 - - º q p e / d ，从而攻破RSA公钥密码。定理4.算法1通过求解 ( ) n   mod2 2b º a 的解( ) b a, 得到n的因子，算法的时间复杂度为( ) n O 。证明.算法的主要计算在于模指数的运算，其计算复杂性为 ( ) ( ) n n n c O   logloglog   loglog   log2，迭代次数为( ) q O 。因此，相对于经典算法，新算法是二次加速算法。证毕.定理5.算法1的成功概率接近于1。证明.算法1的成功概率依赖于迭代次数。文献[17]已经证明所需要的迭代次数的上界为，úùêép£MNR4其中N是搜索空间的总数，M是搜索问题的解的个数。因此算法迭代( ) q O 次，就能以 % 100 的成功概率得到同余方程 ( ) n   mod2 2b º a 的解( ) b a, 。证毕.定理6. 算法1 所需量子位为：ë ûúùêé+2log   lognn ，少于Shor算法攻击RSA所需的量子位数。证明.由3.2知，Shor量子分解算法总共需量子位为é ùn   log 3 。显然有ë û é ùnnn   log 32log   log <úùêé+也即算法1所需量子位少于Shor算法攻击RSA所需要的量子位数。论文在线出版号No.58 王亚辉等：基于方程求解与相位估计攻击RSA的量子算法 9证毕.综上所述，量子算法1是对经典同余方程( ) n   mod2 2b º a 的量子化实现。一旦求出解( ) b a, ,可以通过计算 ( ) ( ) q , p n , = b ± a gcd ，得到模数n的因子 q , p 。进一步，可以计算公钥密码RSA的密钥( )( ) ( ) 1 1   mod / 1 - - º q p e d ，从而攻破RSA公钥密码。相比于Shor算法，算法1所需量子位少，具有亚指数时间复杂度，且成功概率接近于1。5基于相位估计攻击RSA的量子算法如果整数分解问题得以解决，那么我们就可攻破RSA；攻破RSA却不一定要通过解决整数分解问题。我们通过对比发现：算法1仍然具有亚指数时间复杂度，为了降低时间复杂度，我们从非因子分解角度出发，提出另外一个新的量子算法。具体内容如下：5.1算法设计在第3.2节介绍的Shor算法里，攻击RSA主要是通过求元素的阶，而元素的阶主要是在第二个寄存器中进行模幂运算，再对其进行观测，利用量子傅里叶变换，观测第一个寄存器态的周期性来完成的。本节利用量子态的叠加原理，不用观测第二个量子寄存器，提出了一个基于相位估计求密文阶的量子算法。具体算法步骤如下：算法2. 基于相位估计攻击RSA的量子算法输入： n , e , C输出：M过程1.基于相位估计找到密文C模n的阶，计算( )( ) n C Mr e /  mod  mod 1º ，恢复RSA明文M。1.计算tq 2 = ，其中 é ùn t   log = 。2.给定2个t维量子寄存器，其初态为。t t01 0 = Ψ3.对第一个量子寄存器进行Hadamard门变换，产生叠加态11101 0 å-== ®qxxqΨ Ψ : H4.对第二个量子寄存器进行酉变换xCU，得到2 1: U Ψ ΨxC®1 U110xCqxxqå-== （6）( ) n C xqxqx  mod110å-==krikx qxrkΦ e xqrp -=-=åå =2 10101（7）其中r 为*Z ÎnC 模n 的阶，同时也是函数( ) ( ) n C x fx  mod = 的周期。5.对第一个量子寄存器进行量子Fourier逆变换，得到3 21: QFT Ψ Ψ ®-krikxqicxqc , xrkΦ c e er qpp --= =-=åå =2210 0101 1krkqc , xxqcrkiΦ c er qåå-=-= =÷øöçèæ- p=1010 021设krkj = ,化简得：krkqc , xxqciΦ c er qΨkåå-=-= =÷øöçèæ- j p=1010 0231（8）6．对第一个寄存器进行观测。假设观测到态1c ，利用连分数算法可得到满足q qcrk21111£ - 的1r。如果没有找到满足此式的1r，则输出“失败”。7．重复步骤1-5，对第一个寄存器进行观测。假设观测到态2c ，利用连分数算法可得到满足q qcrk21222£ -的2r。如果没有找到满足此式的2r，则输出“失败”。10 计算机学报 2017年8．计算 ( )2 1  LCM r , r r= ，其中 ( )2 1  LCM r , r 表示1r和2r的最小公倍数，也即得到密文的阶r。9．计算( )( ) n C Mr e /  mod  mod 1º ，即攻破RSA。算法2攻击RSA，没有通过分解n，也没有利用陷门 ( ) { } n , q , p , d f 的任何信息。仅仅是通过密文C就把明文M恢复出来，而获得密文在现实攻击中也是最容易满足的条件。因此该攻击属于唯密文攻击。它改变了以往密码分析者试图恢复私钥的做法，直接从恢复消息入手，给出一个对抗RSA密码体制的唯密文攻击。从密码学来看，只要是能从密文系统地恢复出明文，就是密码破译。算法2针对RSA的任意密文都可以恢复出明文，因此是对RSA的密码破译。不过算法2考虑点在于：从非因子分解角度出发破译公钥密码RSA。即从RSA本身破译的传统数学方法出发，是可以不通过因子分解。而传统的方法，都是从因子分解入手的。比如：经典的Shor算法就是求解因子分解问题的。5.2正确性分析算法2的第3步利用Hadamard门变换，由文献[17]可知，Hadamard门变换是一个酉变换。第4步所使用的xCU构造如下：对于给定的与n互素的正整数C，C为RSA的密文，存在酉变换( ) n Cy yC  mod U =且酉变换CU能够被有效执行[17]，则xCU表示酉变换CU的x次方，也即( ) n y C yx xC  mod U =考虑如下态：( ) n C erΦsrsriksk  mod1102å-=p -= （9）其中，k表示满足条件 1 0 - £ £ r k 的整数。将酉变换CU作用于量子态kΦ ，得到( ), n C erΦsrsCriksk C  mod U1U102å-=p -=( ) n C ersrsriks  mod11102+-=p -å =( )( ) n C eresrssrikrik  mod111012 2+-=+p - på =krikΦ ep=2因此，量子态kΦ 是酉变换CU的本征向量，且rikep 2是对应的本征值。将酉变换xCU作用于量子态kΦ ,得到krikxkxCΦ e Φp=2U （10）注意到：r 为*Z ÎnC 模n的阶，如果( ) r k   mod 0 º ，则 ( ) 1   mod = n Cr。对（9）求和，也即( ) n C er rΦrsrsriksrkrkk  mod1 1 11021010å å å-=p --=-== （11）由（11）式可知，态1的振幅为å å-=-=p -= =1010021 11 1 1rkrkrikrer r因为态1的振幅是1，那么其他所有态的振幅都为0。因此得到1110= å-=rkkΦr（12）将（10）和（12）代入（6）可得：krikx qxrkΦ e xqrΨp -=-=åå =2 101021该式子与等式（7）一致。而文献[17]指出了量子Fourier逆变换是一个酉变换，算法2中所使用的变换满足量子计算算法所要求的可逆条件。因此就算法所使用的变换而言，该算法是正确的。且图1给出实现算法2的量子电路图。论文在线出版号No.58 王亚辉等：基于方程求解与相位估计攻击RSA的量子算法 11图1.算法2的量子电路图5.3成功概率分析由算法2的第5步（8）式，如果 是 的整数倍，得到. q / c, q / c qekkqxxqcik¹ j= jîíì= å=÷øöçèæ- j p: 0::1 -02由此可知第一个寄存器中不满足 q / ck= j 的量子态c 的概率幅为0,在算法2第5步中第一个寄存器保留下的量子态c 均满足 q / ck= j 。由算法2的第5步的（8）式知：观测到c 的概率为( )210221å-=÷øöçèæ- j p=qxxqcikerqc P （13）其中，rkk= j 。因此所得量子叠加态的每个态c 被观测到的概率为( ). q / c, q / c r /erqc Pkkqxxqcik¹ j= jîíì= = å=÷øöçèæ- j p: 0: 1:121 -022而在第6步观测到的态c 有r种可能的取值，但是满足 ( ) 1 gcd = r , c 的c只有( ) r f 种可能取值，因此第6步能正确输出态c 的概率为( ) ( )( )。rrr c P Pf= f ´ =当q是r的整数倍时，算法2的成功概率为( )rr f，其中f为欧拉函数。如果q不是r的整数倍，则由图2看到，满足q qcrk21£ - （14）的c一定存在于{ } 1 2 1 0 - q , , , , L 中。图2.在q不是r的整数倍的情况下对r的搜索当满足（14）式时，容易得知相位集中在复平面的上平面或者下平面，此时对 的求和可导致相位的叠加，但如果不满足（14）式，此时对 的求和就导致相位的互相抵消，其大小几乎可以忽略不计。因此，观测到 的概率为( )., q / q / c r / k r /erqc Pqxxqcik其他2 1: 0: 1 121 -022£ -îíì» = å=÷øöçèæ- j p从而在q不是r的整数倍的情况下，可以以近似于r1的概率观测到态c ，同样地，这样的态共有 ( ) r f种可能取值。因此此种情况下第6步能正确输出态c 的概率为( ) ( )( )rrr c P Pf= f ´ »即在q不是r的整数倍的情况下，算法2的成功概率( )rr f» 。由上面的分析可知，密文C的阶决定算法2的成功概率，特别地，当r为素数时，算法2的成功概率( ) r / r 1 - » ，也即随着r的增大，算法的成功概率接近于1。定理7.算法2的成功概率大于Shor算法攻击RSA的成功概率。证明.由定理2知，Shor算法攻击RSA的成功12 计算机学报 2017年概率为 ( ) ( ) r / r p r / r2 24 3 p f < £ p f 。由上面的分析知道，对于算法2，如果q是r的整数倍时，算法2的成功概率为( )rr f。如果q是r的整数倍时，算法2的成功概率( )rr f» 。而( ) ( )rrrr f<pf24，也即算法2的成功概率大于Shor算法攻击RSA的成功概率。证毕.5.4复杂性分析算法2的第2步初始化零态是( ) n O   log 量子比特的。第3步执行Hadamard变换需要( ) n O   log 规模的基本量子门[17]。第4步所使用的酉变换xCU需要 ( ) ( )3  logn O 规模的量子门。第5步中的量子Fourier变换需要 ( ) ( )2  logn O 规模的量子门。第6步和第7步所使用的连分数需要的量子门规模为( ) ( )3  logn O 。因此算法2所需要的基本量子门规模为 ( ) ( )3  logn O 。5.5实例从已有的参考文献来看，人们利用量子计算机只能分解一些诸如15，21，143这些数。因此在此我们也采用同等规模的例子来说明算法2的正确性。具体见例1。例1 在RSA密码体制中，设RSA模数 35 = n ，加密指数 , e 11 = 密文 , C 13 = 找到明文M。1. 计算 é ù6 35   log = = t ，则 64 26= = q 。2. 给定2个6维量子寄存器，其初态为。 1 00= Ψ3. 对第一个量子寄存器进行Hadamard门变换，产生叠加态11101 0 å-== ®qxxqΨ Ψ : H 181630å==xx4.将酉变换xCU应用到第二个量子寄存器得2 1: U Ψ ΨxC®( ) n C xqxqx  mod110å-==( ) 35   mod 1381630xxx å==( + + + + = 27 3 26 2 13 1 1 081+ + + + 27 7 26 6 13 5 1 4+ L) 27 63 26 62 13 61 1 60 + + +可见在第二个寄存器中， 27 26 13 1 , , , 等4个态杂乱排列。选择这些态中的一个进行量子Fourier逆变换，则将在第一个量子寄存器中以( )210221 1å-=÷øöçèæ- j p=qxxqcikeq cc P的几率观测到c 。在这里，第二个量子寄存器的k取 1 2 1 0 - r , , , , L 。应用量子Fourier逆变换之后，对64 = q 绘出的概率分布如图3所示。图3.1QFT-后观察到第一寄存器中态c 的概率， 64 = q可以看到，对每个k的值，使几率接近于 r / 1 的s值为 48 32 16 , , s= 等。5.测量第一个量子寄存器。假设观测到 16 = s ，利用连分数算法得到 41= r 。论文在线出版号No.58 王亚辉等：基于方程求解与相位估计攻击RSA的量子算法 136.重复步骤1-4。测量第一个量子寄存器。假设观测到 32 = s ，利用连分数算法得到 22= r 。7.计算 ( ) 4   LCM2 1= = r , r r ，计算( )( ) n C Mr e /  mod  mod 1º( )( ) 35   mod 134   mod 1/11º27 º则输出 4 = r ，且得到明文 27 = M 。进一步，可验证( ) ( ) 35   mod 27   mod11= n Me13 ºC =即攻破了RSA。为了更直观清晰的看出算法1和算法2的特点以及跟前人在攻击RSA方面的不同，在表1中，我们针对各算法在成功概率，时间复杂性，所需要的量子位以及理论基础等方面进行了比较。表1 各算法消耗资源对比攻击RSA算法成功概率时间复杂度 量子位 理论基础文献[6,7]hor Sp( ) ( )e + 2  logn O é ùn   log 3因子分解文献[26]hor Sp( ) ( )e + 2  logn O é ùn   log 3因子分解算法11 »( ) n O ë ûúùêé+2log   lognn因子分解算法2( )rr f( ) ( )e + 2  logn O é ùn   log 3非因子分解其中 ( ) ( ) r / r p r / rS2hor24 3 p f < £ p f 。通过表1，我们可以看出：算法1具有如下特点：1.基于因子分解实现攻击RSA的，即算法1是对经典同余方程 ( ) n   mod2 2b º a 的量子化实现。2.相比于Shor算法，算法1所需量子位少。3.具有亚指数时间复杂度。4.成功概率接近于1。算法2具有如下特点：1.基于非因子分解实现攻击RSA的，从目前查到的文献来看，还没有从非因子分解角度考虑攻击RSA的量子算法。2.同Shor算法所需量子位相同。3.具有多项式时间复杂度。4.成功概率高于Shor算法攻击RSA的成功概率。6总结与下一步工作整数分解问题是一个古老的难解性问题，然而到目前为止，还没有一个有效的整数分解算法。整数分解在现代密码中有着重要的应用。比如说RSA公钥密码体制的安全性正是基于整数分解的难解性，为此其提出者Rivest，Shamir和Adleman获得了2002年图灵奖。经典的因子分解算法大都是通过求解同余方程 ( ) n   mod2 2b º a 实现的。目前还没有对此方程求解的量子算法，故我们试图从这个角度做一个尝试，基于Grover搜索，提出求解( ) n   mod2 2b º a 的量子算法，这是本文的一个创新点。虽然该算法的计算复杂性是亚指数的，但这是第一个求解同余方程 ( ) n   mod2 2b º a 的量子算法。算法1所需要的量子位数比Shor算法所需要的量子位数少，且算法1的成功概率接近1。众所周知，如果整数分解问题得以解决，那么我们就可攻破RSA；然而，攻破RSA却不一定要通过解决整数分解问题。因此我们可以考虑从非因子分解角度出发，发现通过计算密文C的阶，可以恢复出明文。 M也就是说不用通过分解模数n也能攻破RSA。因此基于量子Fourier逆变换和相位估计，我们给出了一个不通过因子分解攻击RSA的量子算法，即算法2。算法2具有多项式计算复杂性。与Shor算法相比，算法2不需要分解n而从RSA密文C直接恢复出明文M,且成功概率高于Shor算法攻击RSA的成功概率。同时不必要满足密文的阶为偶数。到目前为止，Shor算法仅适合快速求解某些周期性的问题（整数分解问题，离散对数问题，椭圆曲线离散对数问题，Pell方程求解等，都可归约到函数周期的计算问题上来），而对于那些非周期性问题，Shor算法是否也能求解，这是个有意义的研究方向，仍是一个需要深入研究的问题。致谢审稿专家对本文提出了宝贵的修改意见，在14 计算机学报 2017年此对审稿专家表示由衷的感谢！参考文献[1] ZhangHG, HanWB, Lai XJ, LinDD, MaJF, Li JH. Surveyoncyberspace security. Science China Information Sciences, 2016,46(2):125-164(张焕国, 韩文报, 来学嘉, 林东岱, 马建峰, 李建华. 网络空间安全综述. 中国科学:信息科学,2016,46(2):125-164)[2] Rivest RL, Shamir A, AdlemanL. Amethod for obtaining digitalsignaturesandpublic-keycryptosystems.CommunicationsoftheACM,1978,21(2):120-126[3] YanSY. Quantumcomputational number theory. Berlin ,Germany:Springer,2015[4]LenstraAK, LenstraHW, Jr. (editors). Thedevelopment ofthenumberfield sieve. Lecture Notes in Mathematics 1554. Berlin,Germany:Springer,1993[5] Cécile P. The multiple number field sieve with conjugation andgeneralized Joux-Lercier methods//Proceedings of the 34th AnnualInternational Conference on the Theory and Applications ofCryptographicTechniques.Solfla,Bulgaria,2015:156-170[6]ShorPW.Algorithmsforquantumcomputation: discretelogarithmsandfactoring//Proceedingsofthe35thAnnualSymposiumonFoundationsofComputerScience.Washington,USA,1994:124-134[7] Shor PW. Polynomial-time algorithms for prime factorization anddiscrete logarithms on a quantum computer. SIAMJournal onComputing,1997,26(5):1484-1509[8] Broadbent A, Fitzsimons J andKashefi E. Universal blindquantumcomputation//Proceedings of the 51st Annual IEEESymposiumonFoundationsofComputerScience.LasVegas,USA,2010:517-526[9] Li Q, ChanWH, WuCHandWenZH. Triple-server blindquantumcomputationusingentanglement swapping. Physical ReviewA, 2014,89(4):040302[10] WangHF. Quantumalgorithmfor obtaining the eigenstates of aphysicalsystem.PhysicalReviewA,2016,93(5):052334[11]WuWQ, ZhangHG,WangHZ,MaoSW.Polynomial-timequantumalgorithms for finding the linear structures of boolean function.QuantumInformationProcess.2015,14(4):1215-1226[12] Zhang HG, Mao SW, Wu WQ, et al. Overviewof quantumcomputationcomplexitytheory. ChineseJournal ofComputers, 2016,39(12):2403-2428(inChinese)(张焕国，毛少武，吴万青等.量子计算复杂性理论综述.计算机学报,2016,39(12):2403-2428)[13] WuN, Song FM, Li XD. Universal quantumcomputer: theory,organization and implementation. Chinese Journal of Computers,2016,39(12):2429-2445(inChinese)(吴楠，宋方敏，LiX.通用量子计算机：理论、组成与实现.计算机学报,2016,39(12):2429-2445)[14] ZhuBL, ZhuWY, LiuZJ, et al. Anovel quantum-behavedbatalgorithm with mean best position directed for numericaloptimization. Computational Intelligence and Neuroscience, 2016,2016(2):1-17[15]FuXQ, BaoWS, WangS. QuantumalgorithmfordiscretelogarithmoverNZ . ChineseJournal of Computers, 2014, 37(5): 1058-1062(inChinese)(付向群, 鲍皖苏, 王帅.NZ 上离散对数量子计算算法. 计算机学报,2014,37(5):1058-1062)[16]Grover LK. Quantummechanicshelpsinsearchingfor aneedleinahaystack.PhysicalReviewLetters,1977,79(23):325-328[17] Nielson MA, Chuang I L. Quantumcomputation and quantuminformation. 10th Anniversary Edition. Cambridge,UK: CambridgeUniversityPress,2010[18] Vandersypen LMK, Steffen M, Breyta G, et al. ExperimentalRealizationof Shor’sQuantumFactoringAlgorithmUsingNuclearMagneticResonance.Nature,2001,414(6866):883-887[19]IgnacioGM,KlausmF,ShepelyanskyDL.Effectsofimperfectionsfor Shor’s factorizationalgorithm. Physical ReviewA, 2007, 75(5):052311[20]YangC, Daniel L, BrowneE, YangT, PanJW. Demonstrationof acompiled version of Shor’s quantumfactoring algorithmusingphotonicqubits.PhysicalReviewLetters,2007,99(99):250504[21] Peng XH, Liao ZY, XuNY, QinG, et al. Quantumadiabaticalgorithmfor factorization and its experimental implementation.PhysicalReviewLetters,2008,101(22):220405[22] XuNY, ZhuJ, LuDW, et al. Quantumfactorizationof 143onadipolar-coupling nuclear magnetic resonance system. PhysicalReviewLetters,2012,108(13):130501[23] LuceroE, BarendsR, ChenY, et al. ComputingprimefactorswithaJosephsonphasequbitquantumprocessor.NaturePhysics,2012, 8(10):719-723[24] GellerMR, ZhouZY. Factoring51and85with8qubits. ScientificReports,2013,3(3023):1-5[25] SmolinJA, SmithG, VargoA. Oversimplifyingquantumfactoring.Nature,2013,499(7457):163-165[26] Liu LH, Cao ZJ. On computing( ) 2 ordnand its application.InformationandComputation,2006,204(7):1173-1178论文在线出版号No.58 王亚辉等：基于方程求解与相位估计攻击RSA的量子算法 15WANGYa-Hui, born in 1988. Ph.D.candidate. Her current research interestsinclude quantum computing andcryptography. Email address:wangyh_ecc@whu.edu.cnZHANGHuan-Guo, born in 1945. Professor. Seniormember of ChinaComputer Federation. His current researchinterestsincludeinformationsecurity, cryptographyandtrustedcomputing.Emailaddress:liss@whu.edu.cnWUWan-Qing, born in 1981. assistant. His currentresearchinterests include informationsecurity andquantumcomputing.HANGHai-Qing, born in 1979. Ph.D. His currentresearch interests include quantum computing andcryptography.BackgroundThis work is supported by the State Key ProgramofNational Natural Science of China (Grant No. 61332019),Major StateBasicResearchDevelopment Programof China(973 Program) (No.2014CB340601), the National ScienceFoundationof China(Grant Nos. 61303212, 61202386), theMajor Research Plan of the National Natural ScienceFoundationofChina(GrantNo.91018008).The development of quantumcomputation presents aseriouschallengetotheexistingpublic-keycryptosystems, andthepublic-keycryptosystems, RSA, ELGamal, etc. arebrokenbyusingShor’salgorithm. Therefore, itisofgreat significanceto study the cryptanalysis in the quantum computingenvironment. The essential trick to breaking the RSApublic-key cryptosystem is a method for factoringmodulusnefficiently. SinceShorproposedaquantumintegerfactorizationalgorithmwhichcansolveIFPandbreakRSAboth in polymomial-time, various improved and compiledversionsofShor’salgorithmusingdifferenttechnicshavebeenproposedandstudied. Inshort, thereistwoimportant researchdirections in quantuminteger factorization: 1. with fewerquantumbits.2.compiledversionofShor’salgorithm.Therefore, therearetwoaspectsthatneedtobeimproved.Oneisthat howtopresent aquantumalgorithmfor breakingRSAwithfewer qubits. BasedonGrover search, aquantumalgorithmfor findingthepairofsolutions( ) b a, tothesquarecongruence ( ) n   mod2 2b º a ispresented. Thealgorithmrunsinsubexponential-time, but thisisthefirst quantumalgorithmfor solving the square congruence ( ) n   mod2 2b º a . AndcomparedtoShor’s algorithm, the algorithmrequires fewerquantumbits. Another is that howtodesign the compiledversionofShor’salgorithm. SobasedonthequantuminverseFourier transformand phase estimation, a polynomial-timequantumalgorithmfor directlyrecoveringtheRSAplaintextMfromthe ciphertext Cwithout explicitlyfactoringthemodulus n ispresented, andhence, breaksthefamousRSApublic-key cryptosystem. The algorithm runs inpolynomial-time ( ) ( )3  logn O . Thealgorithmavoids that theorderoftheelementmustbeeven.