一兼蕊、介紹

This paper proposes RSA parameters for which key generation, encryption, decryption, signing, and verification are feasible on today’s computers while all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor’s algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.

本文提出了RSA參數(shù)，在當(dāng)今的計(jì)算機(jī)上，密鑰生成莲组，加密，解密室埋，簽名和驗(yàn)證是可行的徙缴，而所有已知的攻擊都是不可行的，甚至假定高度可擴(kuò)展的量子計(jì)算機(jī)田绑。 作為性能分析的一部分勤哗，本文介紹了一種新的算法來生成一批素?cái)?shù)。 作為攻擊分析的一部分掩驱，本文介紹了一種新的量子分解算法芒划，它比Shor算法快得多冬竟，比預(yù)量子分解算法快得多。 提供了初始的pqRSA實(shí)施結(jié)果民逼。

The 1994 publication of Shor’s algorithm prompted widespread claims that quantum computers would kill cryptography, or at least public-key cryptography.Shor算法的1994年出版引起了普遍的說法：量子計(jì)算機(jī)會(huì)殺死密碼學(xué)泵殴，至少是公鑰密碼學(xué)。

But these claims go far beyond the actual limits of Shor’s algorithm, and subsequent research into quantum cryptanalysis has done little to close the gap. Theconventional wisdom among researchers in post-quantum cryptography is thatquantum computers will kill RSA and ECC but will not kill hash-based cryptography, code-based cryptography, lattice-based cryptography, ormultivariatequadratic-equations cryptography.但是這些說法遠(yuǎn)遠(yuǎn)超出了Shor算法的實(shí)際限制拼苍，隨后對(duì)量子密碼分析的研究幾乎沒有縮小差距笑诅。該后量子密碼學(xué)研究人員的傳統(tǒng)觀點(diǎn)是量子計(jì)算機(jī)將殺死RSA和ECC，但不會(huì)殺死基于散列的密碼學(xué)疮鲫，基于代碼的密碼學(xué)吆你，基于格子的密碼學(xué)或多元二次方程密碼學(xué)。

Contents of this paper. Is it actually true that quantum computers will killRSA?

The question here is not whether quantum computers will be built, or will be

affordable for attackers. This paper assumes that astonishingly scalable quantum computers will be built, making a qubit operation as inexpensive as a bitoperation. Under this assumption, Shor’s algorithm easily breaks RSA as usedon the Internet today. The question is whether RSA parameters can be adjusted

so that all known quantum attack algorithms are infeasible while encryption and

decryption remain feasible.本文內(nèi)容俊犯。 量子計(jì)算機(jī)是否真的會(huì)殺死RSA妇多？

這里的問題不是量子計(jì)算機(jī)將會(huì)建成還是將來對(duì)攻擊者負(fù)擔(dān)得起。本文假定將構(gòu)建令人驚訝的可擴(kuò)展的量子計(jì)算機(jī)燕侠，使量子比特操作成本低廉砌梆。在這個(gè)假設(shè)下，Shor算法很容易破壞當(dāng)今互聯(lián)網(wǎng)上使用的RSA贬循。 問題是RSA參數(shù)是否可以調(diào)整所有已知的量子攻擊算法在加密時(shí)都是不可行的解密仍然可行。

The conventional wisdom is that Shor’s algorithm factors an RSA public keyn almost as quickly as the legitimate RSA user can decrypt. Decryption usesan exponentiation modulo n; Shor’s algorithm uses a quantum exponentiationmodulo n. There are some small overheads in Shor’s algorithm—for example,the exponent is double-length—but these overheads create only a very small gapbetween the cost of decryption and the cost of factorization. (Shor speculatedin [48, Section 3] that faster quantum algorithms for modular exponentiation“could even make breaking RSA on a quantum computer asymptotically fasterthan encrypting with RSA on a classical computer”; however, no such algorithmshave been found.)傳統(tǒng)的觀點(diǎn)是桃序，Shor的算法幾乎和合法的RSA用戶解密一樣快杖虾。 解密使用指數(shù)模n; Shor算法使用量子冪模n。 Shor算法中有一些小的開銷媒熊，例如指數(shù)是雙倍長度的奇适，但是這些開銷在解密成本和分解成本之間只產(chǎn)生一個(gè)非常小的差距。 （Shor在[48]第三節(jié)中推測(cè)芦鳍，用于模冪運(yùn)算的更快的量子算法甚至可以使量子計(jì)算機(jī)上的RSA比經(jīng)典計(jì)算機(jī)上的RSA加密快得多;然而嚷往，沒有發(fā)現(xiàn)這樣的算法。

The main point of this paper is that standard techniques for speeding up RSA,when pushed to their extremes, create a much larger gap between the legitimateuser’s costs and the attacker’s costs. Specifically, for this paper’s version of RSA,the attack cost is essentially quadratic in the usage cost.本文的主要觀點(diǎn)是柠衅，加速RSA的標(biāo)準(zhǔn)技術(shù)在被推到極限時(shí)皮仁，會(huì)在合法用戶成本和攻擊者成本之間造成更大的差距。 具體而言菲宴，對(duì)于本文的RSA版本來說贷祈，攻擊代價(jià)在使用成本上基本上是二次的。

These extremes require a careful analysis of quantum algorithms for integer factorization. As part of this security analysis, this paper introduces a newquantum factorization algorithm, GEECM, that is often much faster than Shor’salgorithm and all pre-quantum factorization algorithms. See Section 2. GEECMturns out to be one of the main constraints upon parameter selection for post-quantum RSA.這些極端情況需要仔細(xì)分析整數(shù)分解的量子算法喝峦。 作為安全性分析的一部分势誊，本文介紹了一種新的量子分解算法GEECM，它比Shor算法和所有預(yù)量子分解算法快得多谣蠢。 參見第2節(jié).GEECM成為后量子RSA參數(shù)選擇的主要限制之一粟耻。

These extremes also require a careful analysis of algorithms for the basic RSAoperations. See Section 3. As part of this performance analysis, this paper introduces a new algorithm to generate a large batch of independent uniform randomprimes more efficiently than any known algorithm to generate such primes oneat a time.這些極端情況還需要仔細(xì)分析基本RSA操作的算法查近。 參見第3節(jié)。作為性能分析的一部分挤忙，本文介紹了一種新的算法霜威，比任何已知算法更有效地生成大批獨(dú)立的均勻隨機(jī)素?cái)?shù)，以一次一個(gè)地生成這樣的素?cái)?shù)饭玲。

Section 4 reports initial implementation results for RSA parameters largeenough to push all known quantum attacks above 2100 qubit operations. Theseresults include successful completion of the most expensive operation in post-quantum RSA, namely generating a 1-terabyte public key.第4節(jié)報(bào)告RSA參數(shù)的初始實(shí)現(xiàn)結(jié)果足夠大侥祭，以推動(dòng)所有已知的量子攻擊超過2100 qubit操作。 這些成果包括成功完成后量子RSA中最昂貴的操作茄厘，即生成1TB的公鑰矮冬。

Evaluation and comparison. Post-quantum RSA does not qualify as secure under old-fashioned security definitions requiring asymptotic security against polynomial-time adversaries. However, post-quantum RSA does appear to provide a reasonable level of concrete security評(píng)估和比較。后量子RSA在老式安全定義下不符合安全要求次哈，要求對(duì)多項(xiàng)式時(shí)間對(duì)手進(jìn)行漸進(jìn)安全胎署。 然而，后量子RSA似乎提供了一個(gè)合理的具體安全水平

Note that, for theoretical purposes, it is possible that (1) there are no public-key encryption systems secure against polynomial-time quantum adversaries but (2) there are public-key encryption systems secure against, e.g., essentially-linear-time quantum adversaries. Post-quantum RSA is a candidate for the second category.注意窑滞，為了理論上的目的琼牧，有可能（1）沒有公鑰加密系統(tǒng)對(duì)多項(xiàng)式時(shí)間量子對(duì)手是安全的，但是（2）有公鑰加密系統(tǒng)對(duì)于例如基本線性時(shí)間 量子對(duì)手哀卫。 后量子RSA是第二類的候選人巨坊。

One might think that the quadratic security of post-quantum RSA is no better than the well-known quadratic security of Merkle’s original public-key system. However, the well-known quadratic security is against pre-quantum attackers, not against post-quantum attackers. The analyses by Brassard and Salvail in [17], and by Brassard, H?yer, Kalach, Kaplan, Laplante, and Salvail in [16], indicate that more complicated variants of Merkle’s original public-key system can achieve exponents close to 1.5 against quantum computers, but this is far below the exponent 2 achieved by post-quantum RSA. Concretely, (2^100)^(1/1.5) is

approximately 100000 times larger than (2^100)^(1/2)有人可能會(huì)認(rèn)為后量子RSA的二次安全性不如Merkle原有的公鑰系統(tǒng)的眾所周知的二次安全性好。 然而此改，眾所周知的二次安全是針對(duì)前量子攻擊者趾撵，而不是針對(duì)后量子攻擊者。 Brassard和Salvail [17]以及Brassard共啃，Hyer占调，Kalach，Kaplan移剪，Laplante和Salvail [16]的分析表明究珊，Merkle原始公開密鑰體系的更復(fù)雜的變體可以達(dá)到接近1.5的指數(shù) 計(jì)算機(jī)，但是這遠(yuǎn)低于后量子RSA實(shí)現(xiàn)的指數(shù)2纵苛。 具體來說剿涮，（2 ^ 100）^（1 / 1.5）是

比（2 ^ 100）^（1/2）大大約10萬倍，

Post-quantum RSA is not what one would call lightweight cryptography: thecost of each new encryption or decryption is on the scale of $1 of computer time,many orders of magnitude more expensive than pre-quantum RSA. However, ifthis is the least expensive way to protect high-security information against beingrecorded by an adversary today and decrypted by future quantum computers,then it should be of interest to some users. One can draw an analogy here withfully homomorphic encryption: something expensive might nevertheless be usefulif it is the least expensive way to achieve the user’s desired security goal.后量子RSA并不是什么人會(huì)稱之為輕量級(jí)加密：每個(gè)新的加密或解密的成本是計(jì)算機(jī)時(shí)間的1美元的規(guī)模赶站，比前量子RSA昂貴許多數(shù)量級(jí)幔虏。 但是，如果這是保護(hù)高安全性信息不被對(duì)手記錄并由未來的量子計(jì)算機(jī)解密的最便宜的方式贝椿，那么一些用戶應(yīng)該感興趣想括。 在這里可以用完全同態(tài)加密來進(jìn)行類比：如果昂貴的方法是實(shí)現(xiàn)用戶所期望的安全目標(biāo)的最便宜的方法，則可能是有用的烙博。

Code-based cryptography and lattice-based cryptography have been studiedfor many years and appear to provide secure encryption at far less expense thanpost-quantum RSA. However, one can reasonably argue that triple encryptionwith code-based cryptography, lattice-based cryptography, and post-quantumRSA, for users who can afford it, provides a higher level of confidence than onlytwo of the mechanisms. Post-quantum RSA is also quite unusual in allowing post-quantum encryption, signatures, and more advanced cryptographic functionalitysuch as blind signatures to be provided in a familiar way by a single unifiedmechanism, a multiplicatively homomorphic trapdoor permutation.基于代碼的密碼學(xué)和基于格子的密碼學(xué)已經(jīng)研究了很多年，似乎以比后量子RSA更低的費(fèi)用提供安全加密。 然而衷旅，人們可以合理地認(rèn)為，對(duì)于負(fù)擔(dān)得起的用戶宪躯，基于代碼的密碼術(shù)，基于格的密碼術(shù)和后量子RSA的三重加密提供了比僅兩個(gè)機(jī)制更高的置信水平位迂。 后量子RSA在允許后量子加密访雪，簽名和更高級(jí)的密碼功能如盲簽名方面也是非常不尋常的，通過單一的統(tǒng)一機(jī)制掂林，即乘性同態(tài)陷門置換臣缀，以熟悉的方式提供盲簽名。

Obviously the overall use case for post-quantum RSA relies heavily on thefaint possibility of dramatic improvements in attacks against a broad range ofalternatives. But the same criticism applies even more strongly to, e.g., theproposals in [16]. More importantly, it is interesting to see that the conventional wisdom is wrong, and that RSA has enough flexibility to survive the advent of quantum computers—beaten, bruised, and limping, perhaps, but not dead.顯然泻帮，后量子RSA的總體使用情況很大程度上依賴于大范圍的替代攻擊的顯著改善的微弱可能性精置。 但是，同樣的批評(píng)更適用于例如[16]中的提案锣杂。 更重要的是脂倦，有趣的是，傳統(tǒng)智慧是錯(cuò)誤的元莫，RSA有足夠的靈活性來經(jīng)受量子計(jì)算機(jī)的出現(xiàn) - 被打擊赖阻，受傷和跛行，可能但不是死亡踱蠢。

Future work.There is a line of work suggesting big secrets as a protectionagainst limited-volume side-channel attacks and limited-volume exfiltration bymalware. As a recent example, Shamir is quoted in [7] as saying that he wants thefile containing the Coca-Cola secret “to be a terabyte, which cannot be [easily]exfiltrated”. A terabyte takes only a few hours to transmit over a gigabit-per-second link, but the basic idea of this line of work is that there are sometimeslimits on time and/or bandwidth in side channels and exfiltration channels, andthat these limits could stop the attacker from extracting the desired secrets. Itwould be interesting to analyze the extent to which the secrets in post-quantumRSA provide this type of protection. Beware, however, that a positive answercould be undermined by other parts of the system that have not put the sameattention into expanding their data.未來的工作政供。有一系列的工作表明，大規(guī)模的秘密可以防止惡意軟件限制數(shù)量的旁路攻擊和有限數(shù)量的漏洞朽基。作為最近的一個(gè)例子，沙米爾在[7]中引用他的話說离陶，他希望包含可口可樂秘密的文件“是一個(gè)TB稼虎，不能[很容易]被泄露”。 一個(gè)TB級(jí)只需要幾個(gè)小時(shí)就可以通過千兆位每秒的鏈路進(jìn)行傳輸招刨，但是這一線工作的基本思想是霎俩，有時(shí)會(huì)限制側(cè)通道和出口通道的時(shí)間和/或帶寬，而且這些限制 可以阻止攻擊者提取所需的秘密沉眶。 分析后量子RSA中的秘密提供這種保護(hù)的程度是很有意思的打却。 然而，要小心谎倔，系統(tǒng)的其他部分可能會(huì)損害正面的回答柳击，而這些部分并沒有把注意力放在擴(kuò)展數(shù)據(jù)上。

Our batch prime-generation algorithm suggests that, to help reduce energyconsumption and protect the environment, all users of RSA—including users oftraditional pre-quantum RSA—should delegate their key-generationcomputations to NIST or another trusted third party. This speed improvement would alsoallow users to generate new RSA keys and erase old RSA keys more frequently,limiting the damage of key theft.4 However, all trusted-third-party protocolsraise security questions (see, e.g., [19] and [24]), and there are significant coststo all known techniques to securely distribute or delegate RSA computations.The challenge here is to show that secure multi-user RSA key generation can becarried out more efficiently than one-user-at-a-time RSA key generation.我們的批量生成算法表明片习，為了幫助降低能耗和保護(hù)環(huán)境捌肴，RSA的所有用戶（包括傳統(tǒng)的預(yù)量子RSA的用戶）都應(yīng)該將他們的密鑰生成計(jì)算委托給NIST或另一個(gè)可信的第三方蹬叭。 這種速度的提高還可以使用戶生成新的RSA密鑰，并更頻繁地刪除舊的RSA密鑰状知，從而限制了密鑰被盜用的危害秽五。然而，所有可信的第三方協(xié)議都引發(fā)了安全問題（參見[19]和[ 24]）饥悴，并且所有已知技術(shù)安全地分配或委托RSA計(jì)算的成本都很高坦喘。 這里面臨的挑戰(zhàn)是證明，與一次一個(gè)用戶的RSA密鑰生成相比西设，可以更有效地執(zhí)行安全的多用戶RSA密鑰生成瓣铣。

Another natural direction of followup work is integration of post-quantumRSA into standard Internet protocols such as TLS. This integration is conceptually straightforward but requires tackling many systems-level challenges, suchas various limitations on the RSA key sizes allowed in cryptographic libraries.后續(xù)工作的另一個(gè)自然方向是將后量子RSA集成到標(biāo)準(zhǔn)互聯(lián)網(wǎng)協(xié)議（如TLS）中。 這種集成在概念上很簡單济榨，但需要解決許多系統(tǒng)級(jí)的挑戰(zhàn)坯沪，例如對(duì)加密庫允許的RSA密鑰大小的各種限制。

If the goal is merely to protect past traffic against complete key theft (“forward secrecy”) then a user can obtain a speedup by generating many RSA keys in advance,and erasing each key soon after it is first used. But erasing each key soon after it hasbeen generated is sometimes advertised as helping protect future traffic against limited types of compromise. Furthermore, batching across many users provides largerspeedups.如果目的僅僅是為了防止過去的流量完全失竊（“前向保密”）擒滑，則用戶可以通過預(yù)先生成許多RSA密鑰來獲得加速腐晾，并且在第一次使用之后不久就擦除每個(gè)密鑰。 但是丐一，在生成每個(gè)密鑰之后不久就會(huì)刪除每個(gè)密鑰藻糖，有時(shí)會(huì)被稱為幫助保護(hù)未來的流量免受有限類型的泄露。 而且库车，跨越多個(gè)用戶的批量提供更大的加速巨柒。

二、后量子分解

For every modern variant of RSA, including the variants considered in this paper,the best attacks known are factorization algorithms. This section analyzes thepost-quantum complexity of integer factorization.對(duì)于RSA的每個(gè)現(xiàn)代變體柠衍，包括本文中考慮的變體洋满，已知的最好的攻擊都是分解算法。 本節(jié)分析整數(shù)分解的后期量子復(fù)雜度珍坊。

There have been some papers analyzing and improving the complexity ofShor’s algorithm; see, e.g., [56]. However, the literature does not seem to containany broader study of quantum factorization algorithms. There seems to be animplicit assumption that—once large enough quantum computers are available—Shor’s algorithm supersedes the entire previous literature on integer factorization, rendering all previous factorization algorithms obsolete, so studying thecomplexity of factorization in a post-quantum world is tantamount to studyingthe complexity of Shor’s algorithm.已經(jīng)有一些論文分析和改進(jìn)了Shor算法的復(fù)雜性; 例如參見[56]牺勾。 然而，文獻(xiàn)似乎沒有包含任何更廣泛的量子分解算法的研究阵漏。 似乎有一個(gè)隱含的假設(shè)驻民，一旦足夠大的量子計(jì)算機(jī)可用，Shor算法取代了以前關(guān)于整數(shù)分解的所有文獻(xiàn)履怯，使以前的所有分解算法都被淘汰回还，因此研究后量子世界中分解的復(fù)雜性等同于 研究Shor算法的復(fù)雜性。

The main point of this section is that post-quantum factorization is actually amuch richer subject. It should be obvious that previous algorithms are not alwayssuperseded by Shor’s algorithm: as a trivial example, an integer divisible by 2 or3 or 5 is much more efficiently detected by trial division than by Shor’s algorithm.Perhaps less obvious is that there are quantum factorization algorithms that are,for many integers, much faster than Shor’s algorithm and much faster than allknown pre-quantum algorithms. These algorithms turn out to be important forpost-quantum RSA, as discussed in Section 3.這部分的主要觀點(diǎn)是后量子分解實(shí)際上是一個(gè)更加豐富的課題叹洲。 很明顯柠硕，以前的算法并不總是被Shor算法所取代：作為一個(gè)簡單的例子，一個(gè)可以被2或者3或者5整除的整數(shù)比使用Shor算法更有效地被檢測(cè)分割运提。 也許不那么明顯的是仅叫，對(duì)于許多整數(shù)帜篇，量子分解算法比Shor算法快得多，比所有已知的預(yù)量子算法快得多诫咱。 這些算法對(duì)于后量子RSA是非常重要的笙隙，正如第3節(jié)所討論的那樣。

Overview of pre-quantum integer factorization.There are two importantclasses of factorization algorithms. The first class consists of algorithms thatare particularly fast at finding small primes: e.g., trial division, the rho method[40], the p?1 method [39], the p+ 1 method [55], and the elliptic-curve method(ECM) [35].前量子整數(shù)分解概述坎缭。有兩類重要的因子分解算法竟痰。第一類包括在尋找小素?cái)?shù)方面特別快的算法：例如，除法掏呼，rho方法[40]坏快，p-1方法[39]，p + 1方法[55]和橢圓曲線方法 （ECM）[35]憎夷。

Each of these algorithms can be rephrased, without serious loss of efficiency,as a ring algorithm that composes the ring operations 0, 1, +, ?, · to producea large integer divisible by many small primes. By carrying out the same sequence of operations modulo a target integer n and computing the greatestcommon divisor of the result with n, one sees whether n is divisible by any of thesame primes. For example, trial division up through y has essentially the sameperformance as computing gcd{n, 2 · 3 · 5 · · · · y}; as another example, m stepsof the rho method compute gcd{n,(ρ2 ? ρ1)(ρ4 ? ρ2)(ρ6 ? ρ3)· · ·(ρ2m ? ρm)}with ρ1 = 1 and(ρ(i+1))=(pi)^2+ 10.這些算法中的每一個(gè)都可以被重寫莽鸿，而不會(huì)造成嚴(yán)重的效率損失，因?yàn)樗且粋€(gè)環(huán)算法拾给，它構(gòu)成了一個(gè)可以被許多小素?cái)?shù)整除的大整數(shù)的環(huán)操作0,1祥得，+， - 蒋得。 通過執(zhí)行以目標(biāo)整數(shù)n為模的相同操作序列并用n計(jì)算結(jié)果的最大公約數(shù)级及，可以看出n是否可以被任何相同的素?cái)?shù)整除。 例如额衙，通過y的審判分區(qū)與計(jì)算gcd {n饮焦，2·3·5···y}的性能基本相同; 作為另一個(gè)例子，ρ1= 1和（ρ（i + 1））的rho方法的m個(gè)步驟計(jì)算gcd {n窍侧，（ρ2-ρ1）（ρ4-ρ2）（ρ6-ρ3）...（ρ2m-ρm） ））=（pi）^ 2 + 10县踢。

The importance of ring operations is that carrying them out modulo n has theeffect of carrying them out modulo every prime p dividing n; i.e., Z/n → Z/pis a ring morphism. To measure the speed and effectiveness of a ring algorithmone sees how many operations are carried out by the algorithm and how manyprimes p of various sizes divide the output. The size of n is almost irrelevant,except that each ring operation modulo n costs (lg n)^(1+o(1))bit operations.環(huán)運(yùn)算的重要性在于將它們模n進(jìn)行模n的運(yùn)算， 即Z / n→Z / p是環(huán)形態(tài)伟件。 為了測(cè)量環(huán)算法的速度和有效性殿雪，我們可以看到算法執(zhí)行了多少操作，以及不同大小的素?cái)?shù)p是如何劃分輸出的锋爪。 n的大小幾乎是不相關(guān)的，除了每個(gè)環(huán)運(yùn)算模n花費(fèi)（lg n）^（1 + o（1））位操作爸业。

The second class consists of congruence-combining algorithms: e.g., thecontinued-fraction method [33], the quadratic sieve [41], and the number-fieldsieve (NFS) [34]. These algorithms multiply various congruences modulo n to obtain a congruence of the form a^2 ≡ b^2(mod n), and then hope that gcd{n, a ? b}is a nontrivial factor of n. These algorithms are not usefully viewed as ring algorithms (the congruences modulo n are produced in a way that depends on n)and are not particularly fast at finding small primes.第二類包括同余組合算法其骄，例如連續(xù)分?jǐn)?shù)法[33]，二次篩[41]和數(shù)字場(chǎng)篩（NFS）[34]扯旷。 這些算法乘以各種同余模n拯爽，得到形式a ^ 2≡b ^ 2（mod n）的同余，然后希望gcd {n钧忽，a - b}是n的一個(gè)非平凡因子毯炮。 這些算法并沒有被視為環(huán)算法（同余模n是以一種依賴于n的方式產(chǎn)生的）逼肯，而且在尋找小素?cái)?shù)方面并不是特別快。

For large n the best congruence-combining algorithm appears to be NFS,which (conjecturally) uses 2^((lg n)^(1/3+o(1)))bit operations. For comparison, ECMuses 2^((lg y)^(1/2+o(1)))ring operations if ECM parameters are chosen to (conjecturally) find every prime p ≤ y. Evidently ECM uses fewer bit operations thanNFS to find sufficiently small primes p; the cutoff is 2^((lg n)^(2/3+o(1)))對(duì)于大n桃煎，最好的同余組合算法似乎是NFS篮幢，它（推測(cè)性地）使用2 ^（（lg n）^（1/3 + o（1）））位操作。 為了比較为迈，如果選擇ECM參數(shù)（猜測(cè)）找到每個(gè)素?cái)?shù)p≤y三椿，則ECM使用2 ^（（lg y）^（1/2 + o（1）））環(huán)操作。 顯然ECM使用比NFS更少的位操作來找到足夠小的素?cái)?shù)p; 截距為2 ^（（lg n）^（2/3 + o（1）））

Shor’s algorithm.Shor begins with a circuit to compute the function x →(x, 3^x mod n), where x is an integer having about 2lgn bits. Exponentiationuses about 2lgn multiplications modulo n, and the best multiplication methodsknown use (lgn)^(1+o(1))bit operations, so exponentiation uses (lgn)^(2+o(1))bitoperations.Shor的算法葫辐。 Shor從一個(gè)電路開始計(jì)算函數(shù)x→（x搜锰，3 ^ x mod n），其中x是一個(gè)大約2lgn位的整數(shù)耿战。 指數(shù)運(yùn)算使用大約2lgn乘法模n蛋叼，并且已知的最佳乘法方法使用（lgn）^（1 + o（1））位運(yùn)算，所以指數(shù)運(yùn)算使用（lgn）^（2 + o（1））位運(yùn)算剂陡。

A standard conversion produces a quantum circuit that uses (lg n)^(2+o(1))qubitoperations to evaluate the same function on a quantum superposition of inputs.With a small extra overhead (applying a quantum Fourier transform to theoutput, sampling, et al.) Shor finds the period of this function, i.e., the order of3 modulo n. This order is a divisor, typically a large divisor, of ?(n) = #(Z/n)?,and factoring n with this information is a standard exercise. In the rare case that3 has small order modulo n, one can replace 3 with a randomnumber—preferablya small random number to save time in exponentiation.

標(biāo)準(zhǔn)轉(zhuǎn)換產(chǎn)生量子電路狈涮，其使用（lg n）^（2 + o（1））量子位運(yùn)算來評(píng)估輸入的量子疊加上的相同函數(shù)。 由于額外的額外開銷（對(duì)輸出進(jìn)行量子傅立葉變換鹏倘，采樣等）薯嗤，Shor找到了這個(gè)函數(shù)的周期，即3階模n纤泵。 這個(gè)順序是φ（n）=＃（Z / n）*的除數(shù)骆姐，通常是一個(gè)大的除數(shù)，并且用這個(gè)信息進(jìn)行因式分解是一個(gè)標(biāo)準(zhǔn)的練習(xí)捏题。 在少數(shù)情況下玻褪，3有小模n，可以用一個(gè)隨機(jī)數(shù)（最好是一個(gè)小隨機(jī)數(shù)）替換3公荧，以節(jié)省取冪的時(shí)間带射。

There is a tremendous gap between the (lg n)^(2+o(1))qubit operations usedby Shor and the 2^((lg n)^(1/3+o(1)))bit operations used by NFS. Of course, for themoment qubit operations seem impossibly expensive compared to bitoperations,but post-quantum cryptography looks ahead to a future where qubit operationsare affordable at a large scale. In this future it seems that congruence-combiningalgorithms will be of little, if any, interest.Shor使用的（lg n）^（2 + o（1））量子比特操作與2 ^（（lg n）^（1/3 + o（1）））比特操作之間存在巨大的差距NFS。 當(dāng)然循狰，與量子比特操作相比窟社，量子比特操作似乎不可能成本高昂，但量子后密碼技術(shù)展望了量子比特大規(guī)男髟浚可支付的未來灿里。 在這個(gè)未來看來，同余組合算法將沒有什么興趣程腹，如果有的話匣吊。

On the other hand, Shor’s algorithm is not competitive with ring algorithmsat finding small primes. Even if a qubit operation is as inexpensive as a bitoperation, Shor’s (lg n)^(2+o(1))qubit operations are as expensive as (lg n)^(1+o(1))ring operations. ECM’s 2^((lg y)^(1/2+o(1)))ring operations are better than this forsufficiently small primes. The cutoff is 2^((lg lg n)^(2+o(1)))另一方面，Shor算法在尋找小素?cái)?shù)時(shí)與環(huán)算法沒有競(jìng)爭(zhēng)力。 即使量子比特操作與比特操作一樣便宜色鸳，Shor's（lg n）^（2 + o（1））量子比特操作與（lg n）（1 + o（1））環(huán)操作一樣昂貴社痛。 對(duì)于足夠小的素?cái)?shù)，ECM的2 ^（（lg y）^（1/2 + o（1）））環(huán)操作比這更好命雀。 截止值為2 ^（（lg lg n）^（2 + o（1）））

Some wishful thinking.One might think that Shor’s algorithm can be tweakedto take advantage of a small prime divisor p of n: the function x→ 3^x mod phas small period, and this period should be visible for x having only about 2lg pbits, rather than the 2lg n bits used by Shor. This would save a factor of 2 evenin the most extreme case p ≈√n.一些一廂情愿的想法蒜哀。有人可能會(huì)認(rèn)為，可以調(diào)整Shor的算法來利用n的一個(gè)小的素?cái)?shù)除數(shù)p：函數(shù)x→3 ^ x mod p的周期很小咏雌，這個(gè)周期對(duì)于只有大約2lg p位的x是可見的凡怎，而 比Shor使用的2lg n位。 即使在最極端的情況下赊抖，這也可以節(jié)省2倍统倒。

The difficulty is that one is not given the function x→ 3^x mod p. The functionx→ 3^x mod n has a small pseudo-period, in the sense that shifting the inputproduces a related output, but one is also not given this relation.難點(diǎn)是沒有給出函數(shù)x→3 ^ x mod p。 函數(shù)x→3 ^ x mod n有一個(gè)小的偽周期氛雪，就是說移位輸入產(chǎn)生一個(gè)相關(guān)的輸出房匆，但是也沒有給出這個(gè)關(guān)系。

If there were a fast way to detect pseudo-periods with respect to unknownrelations then one could drastically speed up Shor’s algorithm by finding thepseudo-period p of the simpler function x → x mod n. If x is limited to 2lgp

A quantum ring algorithm: GEECM.A more productive approach is totake the best pre-quantum algorithms for finding small primes, and to acceleratethose algorithms using quantum techniques.量子環(huán)算法：GEECM报亩。更高效的方法是采用最好的預(yù)量子算法來尋找小素?cái)?shù)浴鸿，并使用量子技術(shù)來加速這些算法。

Under standard conjectures, ECM finds primes p ≤ y using 2^((lg y)^(1/2+o(1)))ring operations, as mentioned above; the rho method finds primes p ≤ y using y^(1/2+o(1))ring operations; and trial division (in its classic form) finds primesp ≤ y using y^(1+o(1))ring operations. Evidently ECM supersedes the rho methodand trial division as y grows. The cutoff is generally stated (on the basis of moredetailed analyses of the o(1)) to be below 2^30, and the primes of interest in thispaper are much larger, so this paper focuses on ECM.在標(biāo)準(zhǔn)猜想下弦追，ECM使用2 ^（（lg y）^（1/2 + o（1）））環(huán)操作來找到素?cái)?shù)p≤y岳链。 rho方法使用y ^（1/2 + o（1））環(huán)操作找到素?cái)?shù)p≤y; 和審判分裂（以其經(jīng)典形式）使用y ^（1 + o（1））環(huán)操作找到素?cái)?shù)p≤y。 顯然ECM取代rho法和隨著y的增長而進(jìn)行的審判分工劲件。 總的來說掸哑，（在對(duì)o（1））進(jìn)行更詳細(xì)的分析的基礎(chǔ)上，截?cái)嘀翟? ^ 30以下零远，而本文所關(guān)注的主要因素要大得多苗分，所以本文主要關(guān)注ECM。

(There are occasional primes for which the p?1 and p+1 methods are fasterthan ECM, but the primes of interest in this paper are randomly generated. Mostof the comments in this section generalize to hyperelliptic curves, but genus-≥2-hyperelliptic-curve methods have always been slightly slower than ECM.)（偶爾有質(zhì)數(shù)p-1和p + 1的方法比ECM快牵辣，但是本文中關(guān)注的主要內(nèi)容是隨機(jī)產(chǎn)生的摔癣，本節(jié)中的大部分評(píng)論推廣到超橢圓曲線，但屬≥2 超橢圓曲線方法一直比ECM稍慢纬向。）

The state-of-the-art variant of ECM is EECM (ECM using Edwards curves),introduced by Bernstein, Birkner, Lange, and Peters in [12]. EECM choosesan Edwards curve x^2 + y^2 = 1 + dx^2y^2over Q, or more generally a twistedEdwards curve, with a known non-torsion point P; EECM also chooses a largeinteger s and uses the Edwards addition law to compute the sth multiple of Pon the curve, and in particular the x-coordinate x(sP), represented as a fractionof integers. The output of the ring algorithm is the numerator of this fraction.Overall the computation takes (7+o(1)) lg s multiplications (more than half ofwhich are squarings) and a comparable number of additions and subtractions.For optimized curve choices and further details see [12], [11], [14], [5], and [22].ECM的最新變體是EECM（使用Edwards曲線的ECM）择浊，由Bernstein，Birkner逾条，Lange和Peters [12]介紹琢岩。 EECM選擇愛德華茲曲線（Edwards curve）x ^ 2 + y ^ 2 = 1 + dx ^ 2y ^ 2超過Q，或者更一般地選擇具有已知非扭轉(zhuǎn)點(diǎn)P的扭曲Edwards曲線; EECM也選擇一個(gè)較大的整數(shù)s膳帕，并使用Edwards加法定律來計(jì)算曲線上P的倍數(shù)，特別是用整數(shù)的一小部分表示的x坐標(biāo)x（sP）。 環(huán)算法的輸出是這個(gè)分?jǐn)?shù)的分子危彩。 總的來說攒磨，計(jì)算需要（7 + o（1））lg s乘法（其中一半以上是平方）和相當(dāng)數(shù)量的加法和減法。 有關(guān)優(yōu)化的曲線選擇和更多詳細(xì)信息汤徽，請(qǐng)參閱[12]娩缰，[11]，[14]谒府，[5]和[22]拼坎。

If s is chosen as lcm{1, 2, . . . , z} then lg s ≈ 1.4z so this curve computation uses about 10z multiplications. If z ∈ L^(c+o(1))as y → ∞, where L =exp√(logyloglogy)and c is a positive real constant, then standard conjecturesimply that each prime p ≤ y is found by this curve with probability 1/L^(1/2c+o(1)).Standard conjectures also imply that curves are almost independent, so by trying L^(1/2c+o(1))curves one finds each prime p with high probability. The total costof trying all these curves is L^(c+1/2c+o(1))ring operations. The expression c+ 1/2ctakes its minimum value 1 for c = 1/√2; the total cost is then L^(√2+o(1))ringoperations.如果s被選為lcm {1,2，...完疫。泰鸡。。 壳鹤，z}盛龄，那么lgs≈1.4z，所以這個(gè)曲線計(jì)算使用大約10z的乘法芳誓。 如果z∈L^（c + o（1））為y→∞余舶，其中L = exp（logyloglogy）且c是一個(gè)正實(shí)常數(shù)，那么標(biāo)準(zhǔn)猜想意味著每條素?cái)?shù)p≤y是由 概率1 / L ^（1 / 2c + o（1））锹淌。 標(biāo)準(zhǔn)猜想也意味著曲線幾乎是獨(dú)立的匿值，所以通過嘗試L ^（1 / 2c + o（1））曲線，我們發(fā)現(xiàn)每個(gè)素?cái)?shù)p具有高概率赂摆。 嘗試所有這些曲線的總成本是L ^（c + 1 / 2c + o（1））環(huán)操作挟憔。 對(duì)于c = 1 /√2，表達(dá)式c + 1 / 2c取最小值1; 那么總成本就是L ^（√2+ o（1））環(huán)操作库正。

This paper introduces GEECM (Grover plus EECM), which uses quantumcomputers as follows to accelerate the same EECM computation. Recall thatGrover’s method accelerates searching for roots of functions: if the inputs to afunction f are roots of f with probability 1/R, then classical searching performs(on average) R evaluations of f, while Grover’s method performs about √Rquantum evaluations of f. Consider, in particular, the function f whose input isan EECM curve choice, and whose output is 0 exactly when the EECM resultfor that curve choice has a nontrivial factor in common with n. EECM finds aroot of f by classical searching; GEECM finds a root of f by Grover’s method. Ifs and z are chosen as above then the inputs to f are roots of f with probability1/L^(1/2c+o(1)), so GEECM uses just L^(1/4c+o(1)) quantum evaluations of f, for a total of L^(c+1/4c+o(1)) quantum ring operations. The expression c + 1/4c takes its minimum value 1 for c = 1/2; the total cost is then just L^(1+o(1)) ring operations.本文介紹了使用量子計(jì)算機(jī)的GEECM（Grover plus EECM）曲楚，以加速相同的EECM計(jì)算∪旆回想一下龙誊，Grover的方法加速搜索函數(shù)的根：如果函數(shù)f的輸入是概率為1 / R的f的根，則經(jīng)典搜索執(zhí)行（平均）R的R評(píng)估喷楣，而Grover的方法執(zhí)行關(guān)于√R量子評(píng)估f趟大。尤其考慮函數(shù)f，其輸入是EECM曲線選擇铣焊，并且當(dāng)該曲線選擇的EECM結(jié)果具有與n相同的非平凡因子時(shí)逊朽，其輸出恰好為0。 EECM通過經(jīng)典搜索找到f的根; GEECM通過Grover的方法找到了f的根源曲伊。如果選擇s和z叽讳，那么f的輸入就是f的概率為1 / L ^（1 / 2c + o（1））的根追他，所以GEECM只使用L ^（1 / 4c + o（1））量子估計(jì)的f，總的L ^（c + 1 / 4c + o（1））量子環(huán)運(yùn)算岛蚤。對(duì)于c = 1/2邑狸，表達(dá)式c + 1 / 4c取其最小值1;那么總的成本就是L ^（1 + o（1））環(huán)操作。

To summarize, GEECM reduces the number of ring operations from L^(√2+o(1)) to L^(1+o(1)), where L = exp√(logyloglogy). For the same number of operations, GEECM increases log y by a factor 2 + o(1), almost doubling the number of bits of primes that can be found.總而言之涤妒，GEECM將環(huán)操作從L ^（√2+ o（1））減少到L ^（1 + o（1））单雾，其中L = exp（logyloglogy）。 對(duì)于相同數(shù)量的操作她紫，GEECM將log y增加了2 + o（1）硅堆，幾乎是可以找到的素?cái)?shù)的兩倍。