{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T03:22:54Z","timestamp":1776482574655,"version":"3.51.2"},"reference-count":91,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Eker\u00e5-H\u00e5stad 2017, Eker\u00e5 2017, Eker\u00e5 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>10<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\u2212<\/mml:mo><mml:mn>3<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:math>, a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>3<\/mml:mn><mml:mi>n<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>0.002<\/mml:mn><mml:mi>n<\/mml:mi><mml:mi>lg<\/mml:mi><mml:mo>\u2061<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:math> logical qubits, <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>0.3<\/mml:mn><mml:msup><mml:mi>n<\/mml:mi><mml:mn>3<\/mml:mn><\/mml:msup><mml:mo>+<\/mml:mo><mml:mn>0.0005<\/mml:mn><mml:msup><mml:mi>n<\/mml:mi><mml:mn>3<\/mml:mn><\/mml:msup><mml:mi>lg<\/mml:mi><mml:mo>\u2061<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:math> Toffolis, and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>500<\/mml:mn><mml:msup><mml:mi>n<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>+<\/mml:mo><mml:msup><mml:mi>n<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mi>lg<\/mml:mi><mml:mo>\u2061<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:math> measurement depth to factor <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.<\/jats:p>","DOI":"10.22331\/q-2021-04-15-433","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T18:27:45Z","timestamp":1618511265000},"page":"433","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":555,"title":["How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits"],"prefix":"10.22331","volume":"5","author":[{"given":"Craig","family":"Gidney","sequence":"first","affiliation":[{"name":"Google Inc., Santa Barbara, California 93117, USA"}]},{"given":"Martin","family":"Eker\u00e5","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden"},{"name":"Swedish NCSA, Swedish Armed Forces, SE-107 85 Stockholm, Sweden"}]}],"member":"9598","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson, and D. Smith-Tone. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. Technical Report NIST Internal Report (NISTIR) 8240, NIST, January 2019. 10.6028\/NIST.IR.8240.","DOI":"10.6028\/NIST.IR.8240"},{"key":"1","doi-asserted-by":"publisher","unstructured":"R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity. Physical Review X, 8 (4): 041015(1\u201336), 2018. 10.1103\/PhysRevX.8.041015. arXiv:1805.03662.","DOI":"10.1103\/PhysRevX.8.041015"},{"key":"2","doi-asserted-by":"publisher","unstructured":"R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O'Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and J. M. Martinis. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature, 508: 500\u2013503, April 2014. 10.1038\/nature13171. arXiv:1402.4848.","DOI":"10.1038\/nature13171"},{"key":"3","doi-asserted-by":"publisher","unstructured":"E. Barker, L. Chen, A. Roginsky, A. Vassilev, and R. Davis. Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. Technical Report NIST Special Publication (SP) 800-56A, Rev. 3, NIST, April 2018. 10.6028\/NIST.SP.800-56Ar3.","DOI":"10.6028\/NIST.SP.800-56Ar3"},{"key":"4","doi-asserted-by":"publisher","unstructured":"E. Barker, L. Chen, A. Roginsky, A. Vassilev, R. Davis, and S. Simon. Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. Technical Report NIST Special Publication (SP) 800-56B, Rev. 2, NIST, March 2019. 10.6028\/NIST.SP.800-56Br2.","DOI":"10.6028\/NIST.SP.800-56Br2"},{"key":"5","doi-asserted-by":"publisher","unstructured":"S. Beauregard. Circuit for Shor's algorithm using $2n+3$ qubits. Quantum Information & Computation, 3 (2): 175\u2013185, 2003. 10.26421\/QIC3.2-8. arXiv:quant-ph\/0205095.","DOI":"10.26421\/QIC3.2-8"},{"key":"6","doi-asserted-by":"publisher","unstructured":"D. Beckman, A. N. Chari, S. Devabhaktuni, and J. Preskill. Efficient networks for quantum factoring. Physical Review A, 54 (2): 1034, 1996. 10.1103\/PhysRevA.54.1034. arXiv:quant-ph\/9602016.","DOI":"10.1103\/PhysRevA.54.1034"},{"key":"7","doi-asserted-by":"publisher","unstructured":"D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush. Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization. Quantum, 3: 208, 2019. 10.22331\/q-2019-12-02-208. arXiv:1902.02134.","DOI":"10.22331\/q-2019-12-02-208"},{"key":"8","unstructured":"BlueKrypt. Cryptographic Key Length Recommendation. https:\/\/www.keylength.com, 2019. URL https:\/\/www.keylength.com. Accessed: 2019-03-03."},{"key":"9","doi-asserted-by":"publisher","unstructured":"A. Bocharov, M. Roetteler, and K. M. Svore. Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits. Physical Review Letters, 114: 080502, Feb 2015. 10.1103\/PhysRevLett.114.080502. arXiv:1404.5320.","DOI":"10.1103\/PhysRevLett.114.080502"},{"key":"10","doi-asserted-by":"publisher","unstructured":"F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thom\u00e9, and P. Zimmermann. Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment. In Advances in Cryptology \u2013 CRYPTO 2020, volume 12171 of Lecture Notes in Computer Science (LNCS), pages 62\u201391. Springer, 2020. 10.1007\/978-3-030-56880-1_3.","DOI":"10.1007\/978-3-030-56880-1_3"},{"key":"11","unstructured":"M. Braithwaite. Experimenting with post-quantum cryptography. https:\/\/security.googleblog.com\/2016\/07\/experimenting-with-post-quantum.html, July 2016. URL https:\/\/security.googleblog.com\/2016\/07\/experimenting-with-post-quantum.html."},{"key":"12","doi-asserted-by":"publisher","unstructured":"S. Bravyi and A. Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103\/PhysRevA.71.022316. arXiv:quant-ph\/0403025.","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"13","doi-asserted-by":"publisher","unstructured":"J. P. Buhler, H. W. Lenstra Jr., and C. Pomerance. Factoring integers with the number field sieve. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM), pages 50\u201394. Springer, 1993. 10.1007\/BFb0091539.","DOI":"10.1007\/BFb0091539"},{"key":"14","doi-asserted-by":"publisher","unstructured":"E. Campbell, A. Khurana, and A. Montanaro. Applying quantum algorithms to constraint satisfaction problems. Quantum, 3: 167, 2019. 10.22331\/q-2019-07-18-167. arXiv:1810.05582.","DOI":"10.22331\/q-2019-07-18-167"},{"key":"15","doi-asserted-by":"publisher","unstructured":"R. Cleve and J. Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 526\u2013536. IEEE, 2000. 10.1109\/SFCS.2000.892140.","DOI":"10.1109\/SFCS.2000.892140"},{"key":"16","doi-asserted-by":"publisher","unstructured":"D. Copsey, M. Oskin, F. Impens, T. Metodiev, A. Cross, F. T. Chong, I. L. Chuang, and J. Kubiatowicz. Toward a scalable, silicon-based quantum computing architecture. IEEE Journal of Selected Topics in Quantum Electronics, 9 (6): 1552\u20131569, 2003. 10.1109\/JSTQE.2003.820922.","DOI":"10.1109\/JSTQE.2003.820922"},{"key":"17","unstructured":"S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton. A new quantum ripple-carry addition circuit. arXiv preprint quant-ph\/0410184, 2004. URL https:\/\/arxiv.org\/abs\/quant-ph\/0410184."},{"key":"18","doi-asserted-by":"publisher","unstructured":"W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22 (6): 644\u2013654, 1976. 10.1109\/TIT.1976.1055638.","DOI":"10.1109\/TIT.1976.1055638"},{"key":"19","doi-asserted-by":"publisher","unstructured":"T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Information & Computation, 6 (4\u20135): 351\u2013369, 2006. 10.26421\/QIC6.4-5-4. arXiv:quant-ph\/0406142.","DOI":"10.26421\/QIC6.4-5-4"},{"key":"20","unstructured":"M. Eker\u00e5. Modifying Shor's algorithm to compute short discrete logarithms. Cryptology ePrint Archive, Report 2016\/1128, 2016. URL https:\/\/eprint.iacr.org\/2016\/1128."},{"key":"21","unstructured":"M. Eker\u00e5. Revisiting Shor\u2019s quantum algorithm for computing general discrete logarithms. arXiv preprint arXiv:1905.09084, 2019. URL https:\/\/arxiv.org\/abs\/1905.09084."},{"key":"22","doi-asserted-by":"publisher","unstructured":"M. Eker\u00e5. On post-processing in the quantum algorithm for computing short discrete logarithms. Designs, Codes and Cryptography, 88 (11): 2313\u20132335, 2020. 10.1007\/s10623-020-00783-2. iacr:2017\/1122.","DOI":"10.1007\/s10623-020-00783-2"},{"key":"23","doi-asserted-by":"publisher","unstructured":"M. Eker\u00e5. Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. Journal of Mathematical Cryptology, 15 (1): 359\u2013407, 2021. 10.1515\/jmc-2020-0006. (To appear.) iacr:2018\/797.","DOI":"10.1515\/jmc-2020-0006"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M. Eker\u00e5 and J. H\u00e5stad. Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. In Post-Quantum Cryptography, volume 10346 of Lecture Notes in Computer Science (LNCS), pages 347\u2013363. Springer, 2017. 10.1007\/978-3-319-59879-6_20.","DOI":"10.1007\/978-3-319-59879-6_20"},{"key":"25","unstructured":"A. G. Fowler. Time-optimal quantum computation. arXiv preprint arXiv:1210.4626, 2012. URL https:\/\/arxiv.org\/abs\/1210.4626."},{"key":"26","unstructured":"A. G. Fowler and C. Gidney. Low overhead quantum computation using lattice surgery. arXiv preprint arXiv:1808.06709, 2018. URL https:\/\/arxiv.org\/abs\/1808.06709."},{"key":"27","doi-asserted-by":"publisher","unstructured":"A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3): 032324, 2012. 10.1103\/PhysRevA.86.032324. arXiv:1208.0928.","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"28","doi-asserted-by":"publisher","unstructured":"A. G. Fowler, S. J. Devitt, and C. Jones. Surface code implementation of block code state distillation. Scientific Reports, 3: 1939, 2013. 10.1038\/srep01939. arXiv:1301.7107.","DOI":"10.1038\/srep01939"},{"key":"29","unstructured":"V. Gheorghiu and M. Mosca. Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes. arXiv preprint arXiv:1902.02332, 2019. URL https:\/\/arxiv.org\/abs\/1902.02332."},{"key":"30","unstructured":"C. Gidney. Factoring with $n+2$ clean qubits and $n-1$ dirty qubits. arXiv preprint arXiv:1706.07884, 2017. URL https:\/\/arxiv.org\/abs\/1706.07884."},{"key":"31","doi-asserted-by":"publisher","unstructured":"C. Gidney. Halving the cost of quantum addition. Quantum, 2: 74, 2018. 10.22331\/q-2018-06-18-74. arXiv:1709.06648.","DOI":"10.22331\/q-2018-06-18-74"},{"key":"32","unstructured":"C. Gidney. Approximate encoded permutations and piecewise quantum adders. arXiv preprint arXiv:1905.08488, 2019a. URL https:\/\/arxiv.org\/abs\/1905.08488."},{"key":"33","unstructured":"C. Gidney. Asymptotically Efficient Quantum Karatsuba Multiplication. arXiv preprint arXiv:1904.07356, 2019b. URL https:\/\/arxiv.org\/abs\/1904.07356."},{"key":"34","unstructured":"C. Gidney. Windowed quantum arithmetic. arXiv preprint arXiv:1905.07682, 2019c. URL https:\/\/arxiv.org\/abs\/1905.07682."},{"key":"35","doi-asserted-by":"publisher","unstructured":"C. Gidney and A. G. Fowler. Efficient magic state factories with a catalyzed $|\\text{CCZ}\\rangle$ to $2|\\text{T}\\rangle$ transformation. Quantum, 3: 135, 2019a. 10.22331\/q-2019-04-30-135. arXiv:1812.01238.","DOI":"10.22331\/q-2019-04-30-135"},{"key":"36","unstructured":"C. Gidney and A. G. Fowler. Flexible layout of surface code computations using AutoCCZ states. arXiv preprint arXiv:1905.08916, 2019b. URL https:\/\/arxiv.org\/abs\/1905.08916."},{"key":"37","doi-asserted-by":"publisher","unstructured":"D. Gillmor. RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS), August 2016. 10.17487\/RFC7919.","DOI":"10.17487\/RFC7919"},{"key":"38","doi-asserted-by":"publisher","unstructured":"D. M. Gordon. Discrete logarithms in GF($p$) using the Number Field Sieve. SIAM Journal on Discrete Mathematics, 6 (1): 124\u2013138, 1993. 10.1137\/0406010.","DOI":"10.1137\/0406010"},{"key":"39","doi-asserted-by":"publisher","unstructured":"R. B. Griffiths and C.-S. Niu. Semiclassical Fourier Transform for Quantum Computation. Physical Review Letters, 76 (17): 3228\u20133231, April 1996. 10.1103\/PhysRevLett.76.3228. arXiv:quant-ph\/9511007.","DOI":"10.1103\/PhysRevLett.76.3228"},{"key":"40","doi-asserted-by":"publisher","unstructured":"J. Haah and M. B. Hastings. Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates. Quantum, 2: 71, 2018. 10.22331\/q-2018-06-07-71. arXiv:1709.02832.","DOI":"10.22331\/q-2018-06-07-71"},{"key":"41","doi-asserted-by":"publisher","unstructured":"T. H\u00e4ner, M. Roetteler, and K. M. Svore. Factoring using $2n+2$ qubits with Toffoli based modular multiplication. Quantum Information & Computation, 17 (7\u20138): 673\u2013684, 2017. 10.26421\/QIC17.7-8-7. arXiv:1611.07995.","DOI":"10.26421\/QIC17.7-8-7"},{"key":"42","doi-asserted-by":"publisher","unstructured":"M. B. Hastings and A. Geller. Reduced Space-Time and Time Costs Using Dislocation Codes and Arbitrary Ancillas. Quantum Information & Computation, 15 (11\u201312): 962\u2013986, 2015. 10.26421\/QIC15.11-12-6. arXiv:1408.3379.","DOI":"10.26421\/QIC15.11-12-6"},{"key":"43","doi-asserted-by":"publisher","unstructured":"C. Horsman, A. G. Fowler, S. Devitt, and R. Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, 2012. 10.1088\/1367-2630\/14\/12\/123011. arXiv:1111.4022.","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"44","doi-asserted-by":"publisher","unstructured":"L. Jiang, J. M. Taylor, A. S. S\u00f8rensen, and M. D. Lukin. Scalable quantum networks based on few-qubit registers. International Journal of Quantum Information, 8 (01n02): 93\u2013104, 2010. 10.1142\/S0219749910006058.","DOI":"10.1142\/S0219749910006058"},{"key":"45","doi-asserted-by":"publisher","unstructured":"N. C. Jones, R. Van Meter, A. G. Fowler, P. L. McMahon, J. Kim, T. D. Ladd, and Y. Yamamoto. Layered Architecture for Quantum Computing. Physical Review X, 2 (3): 031007, 2012. 10.1103\/PhysRevX.2.031007. arXiv:1010.5022.","DOI":"10.1103\/PhysRevX.2.031007"},{"key":"46","unstructured":"A. A. Karatsuba and Y. P. Ofman. Multiplication of many-digital numbers by automatic computers. Doklady Akademii Nauk SSSR, 145 (2): 293\u2013294, 1962. URL http:\/\/mi.mathnet.ru\/eng\/dan\/v145\/i2\/p293."},{"key":"47","doi-asserted-by":"publisher","unstructured":"Y. Kim, R. Daly, J. Kim, C. Fallin, J. H. Lee, D. Lee, C. Wilkerson, K. Lai, and O. Mutlu. Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors. In 2014 ACM\/IEEE 41st International Symposium on Computer Architecture (ISCA), pages 361\u2013372. IEEE, 2014. 10.1109\/ISCA.2014.6853210.","DOI":"10.1109\/ISCA.2014.6853210"},{"key":"48","doi-asserted-by":"publisher","unstructured":"T. Kivinen and M. Kojo. RFC 3526: More Modular Exponentiation (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE), May 2003. 10.17487\/RFC3526.","DOI":"10.17487\/RFC3526"},{"key":"49","doi-asserted-by":"publisher","unstructured":"T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thom\u00e9, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, t. R. Herman, A. Timofeev, and P. Zimmermann. Factorization of a 768-Bit RSA Modulus. In Advances in Cryptology \u2013 CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science (LNCS), pages 333\u2013350. Springer, 2010. 10.1007\/978-3-642-14623-7_18.","DOI":"10.1007\/978-3-642-14623-7_18"},{"key":"50","unstructured":"S. A. Kutin. Shor's algorithm on a nearest-neighbor machine. arXiv preprint quant-ph\/0609001, 2006. URL https:\/\/arxiv.org\/abs\/quant-ph\/0609001."},{"key":"51","unstructured":"A. K. Lenstra. Key Lengths. In The Handbook of Information Security, chapter 6. 2004. URL https:\/\/infoscience.epfl.ch\/record\/164539\/files\/NPDF-32.pdf."},{"key":"52","doi-asserted-by":"publisher","unstructured":"A. K. Lenstra and H. W. Lenstra Jr., editors. The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM). Springer, 1993. 10.1007\/BFb0091534.","DOI":"10.1007\/BFb0091534"},{"key":"53","doi-asserted-by":"publisher","unstructured":"A. K. Lenstra and E. R. Verheul. Selecting Cryptographic Key Sizes. Journal of Cryptology, 14: 225\u2013293, 2001. 10.1007\/s00145-001-0009-4.","DOI":"10.1007\/s00145-001-0009-4"},{"key":"54","doi-asserted-by":"publisher","unstructured":"A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard. The number field sieve. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pages 564\u2013572. ACM, 1990. 10.1145\/100216.100295.","DOI":"10.1145\/100216.100295"},{"key":"55","doi-asserted-by":"publisher","unstructured":"D. Litinski. Magic State Distillation: Not as Costly as You Think. Quantum, 3: 205, 2019. 10.22331\/q-2019-12-02-205. arXiv:1905.06903.","DOI":"10.22331\/q-2019-12-02-205"},{"key":"56","doi-asserted-by":"publisher","unstructured":"M. Mosca. Cybersecurity in an Era with Quantum Computers: Will We Be Ready? IEEE Security & Privacy, 16 (5): 38\u201341, 2018. 10.1109\/MSP.2018.3761723. iacr:2015\/1075.","DOI":"10.1109\/MSP.2018.3761723"},{"key":"57","doi-asserted-by":"publisher","unstructured":"M. Mosca and A. Ekert. The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In Quantum Computing and Quantum Communications, volume 1509 of Lecture Notes in Computer Science (LNCS), pages 174\u2013188. Springer, 1999. 10.1007\/3-540-49208-9_15.","DOI":"10.1007\/3-540-49208-9_15"},{"key":"58","doi-asserted-by":"publisher","unstructured":"NIST. Digital Signature Standard (DSS). Technical Report Federal Information Processing Standards Publications (FIPS PUBS) 186-4, July 2013. 10.6028\/NIST.FIPS.186-4.","DOI":"10.6028\/NIST.FIPS.186-4"},{"key":"59","unstructured":"NIST and CCCS. Implementation Guidance for FIPS 140-2 and the Cryptographic Module Validation Program. Technical report, May 2019. URL https:\/\/csrc.nist.gov\/csrc\/media\/projects\/cryptographic-module-validation-program\/documents\/fips140-2\/fips1402ig.pdf. Accessed: 2019-05-10, Document Revision: 2019-05-07."},{"key":"60","doi-asserted-by":"publisher","unstructured":"J. O'Gorman and E. T. Campbell. Quantum computation with realistic magic-state factories. Physical Review A, 95 (3): 032338, 2017. 10.1103\/PhysRevA.95.032338. arXiv:1605.07197.","DOI":"10.1103\/PhysRevA.95.032338"},{"key":"61","doi-asserted-by":"publisher","unstructured":"D. K. L. Oi, S. J. Devitt, and L. C. L. Hollenberg. Scalable error correction in distributed ion trap computers. Physical Review A, 74 (5): 052313, 2006. 10.1103\/PhysRevA.74.052313. arXiv:quant-ph\/0606226.","DOI":"10.1103\/PhysRevA.74.052313"},{"key":"62","unstructured":"OpenSSL Software Foundation. OpenSSL source code: Line 32 of apps\/dhparam.c. https:\/\/github.com\/openssl\/openssl\/blob\/07f434441e7ea385f975e8df8caa03e62222ca61\/apps\/dhparam.c#L32, 2018. URL https:\/\/github.com\/openssl\/openssl\/blob\/07f434441e7ea385f975e8df8caa03e62222ca61\/apps\/dhparam.c#L32. Accessed: 2018-12-11."},{"key":"63","doi-asserted-by":"publisher","unstructured":"M. Oskin, F. T. Chong, and I. L. Chuang. A practical architecture for reliable quantum computers. Computer, 35 (1): 79\u201387, 2002. 10.1109\/2.976922.","DOI":"10.1109\/2.976922"},{"key":"64","doi-asserted-by":"publisher","unstructured":"A. Parent, M. Roetteler, and M. Mosca. Improved reversible and quantum circuits for Karatsuba-based integer multiplication. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), volume 73 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1\u20137:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2018. 10.4230\/LIPIcs.TQC.2017.7. arXiv:1706.03419.","DOI":"10.4230\/LIPIcs.TQC.2017.7"},{"key":"65","doi-asserted-by":"publisher","unstructured":"S. Parker and M. B. Plenio. Efficient Factorization with a Single Pure Qubit and $\\log N$ Mixed Qubits. Physical Review Letters, 85 (14): 3049, October 2000. 10.1103\/PhysRevLett.85.3049. arXiv:quant-ph\/0001066.","DOI":"10.1103\/PhysRevLett.85.3049"},{"key":"66","doi-asserted-by":"publisher","unstructured":"A. Pavlidis and D. Gizopoulos. Fast quantum modular exponentiation architecture for Shor's factorization algorithm. Quantum Information & Computation, 14 (7\u20138): 649\u2013682, 2014. 10.26421\/QIC14.7-8-8. arXiv:1207.0511.","DOI":"10.26421\/QIC14.7-8-8"},{"key":"67","doi-asserted-by":"publisher","unstructured":"S. C. Pohlig and M. E. Hellman. An Improved Algorithm for Computing Logarithms over GF($p$) and Its Cryptographic Significance. IEEE Transactions on Information Theory, IT-24 (1): 106\u2013110, 1978. 10.1109\/TIT.1978.1055817.","DOI":"10.1109\/TIT.1978.1055817"},{"key":"68","doi-asserted-by":"publisher","unstructured":"J. M. Pollard. Monte Carlo Methods for Index Computation (mod $p$). Mathematics of Computation, 32 (143): 918\u2013924, 1978. 10.1090\/s0025-5718-1978-0491431-9.","DOI":"10.1090\/s0025-5718-1978-0491431-9"},{"key":"69","doi-asserted-by":"publisher","unstructured":"J. M. Pollard. Factoring with cubic integers. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM), pages 4\u201310. Springer, 1993a. 10.1007\/BFb0091536.","DOI":"10.1007\/BFb0091536"},{"key":"70","doi-asserted-by":"publisher","unstructured":"J. M. Pollard. The lattice sieve. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM), pages 43\u201349. Springer, 1993b. 10.1007\/BFb0091538.","DOI":"10.1007\/BFb0091538"},{"key":"71","unstructured":"C. Pomerance. A Tale of Two Sieves. Notices of the AMS, 43 (12): 1473\u20131485, 1996. URL https:\/\/www.ams.org\/notices\/199612\/pomerance.pdf."},{"key":"72","doi-asserted-by":"publisher","unstructured":"R. L. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21 (2): 120\u2013126, 1978. 10.1145\/359340.359342.","DOI":"10.1145\/359340.359342"},{"key":"73","doi-asserted-by":"publisher","unstructured":"M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter. Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. In Advances in Cryptology \u2013 ASIACRYPT 2017, volume 10625 of Lecture Notes in Computer Science (LNCS), pages 241\u2013270. Springer, 2017. 10.1007\/978-3-319-70697-9_9.","DOI":"10.1007\/978-3-319-70697-9_9"},{"key":"74","unstructured":"O. Schirokauer. On pro-finite groups and on discrete logarithms. PhD thesis, University of California, Berkeley, May 1992."},{"key":"75","doi-asserted-by":"publisher","unstructured":"O. Schirokauer. Discrete Logarithms and Local Units. Philosophical Transactions of the Royal Society of London A, 345 (1676): 409\u2013423, 1993. 10.1098\/rsta.1993.0139.","DOI":"10.1098\/rsta.1993.0139"},{"key":"76","doi-asserted-by":"publisher","unstructured":"A. Sch\u00f6nhage and V. Strassen. Schnelle Multiplikation gro\u00dfer Zahlen. Computing, 7 (3\u20134): 281\u2013292, 1971. 10.1007\/BF02242355.","DOI":"10.1007\/BF02242355"},{"key":"77","doi-asserted-by":"publisher","unstructured":"B. Schroeder, E. Pinheiro, and W.-D. Weber. DRAM Errors in the Wild: A Large-Scale Field Study. SIGMETRICS Performance Evaluation Review, 37 (1): 193\u2013204, 2009. 10.1145\/1555349.1555372.","DOI":"10.1145\/1555349.1555372"},{"key":"78","doi-asserted-by":"publisher","unstructured":"P. W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124\u2013134. IEEE, 1994. 10.1109\/SFCS.1994.365700.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"79","unstructured":"The GnuPG Project. GnuPG Frequently Asked Questions: Why does GnuPG default to 2048 bit RSA-2048? https:\/\/www.gnupg.org\/faq\/gnupg-faq.html#default_rsa2048, 2018. URL https:\/\/www.gnupg.org\/faq\/gnupg-faq.html#default_rsa2048. Accessed: 2018-12-11."},{"key":"80","unstructured":"The OpenSSH Project. Linux Documentation: Man Page for ssh-keygen(1). https:\/\/linux.die.net\/man\/1\/ssh-keygen, 2018. URL https:\/\/linux.die.net\/man\/1\/ssh-keygen. Accessed: 2018-12-11."},{"key":"81","doi-asserted-by":"publisher","unstructured":"R. Van Meter. A #QuantumComputerArchitecture Tweetstorm, 2019. 10.5281\/zenodo.3496597.","DOI":"10.5281\/zenodo.3496597"},{"key":"82","doi-asserted-by":"publisher","unstructured":"R. Van Meter and K. M. Itoh. Fast quantum modular exponentiation. Physical Review A, 71 (5): 052320, 2005. 10.1103\/PhysRevA.71.052320. arXiv:quant-ph\/0408006.","DOI":"10.1103\/PhysRevA.71.052320"},{"key":"83","doi-asserted-by":"publisher","unstructured":"R. Van Meter, W. J. Munro, K. Nemoto, and K. M. Itoh. Arithmetic on a distributed-memory quantum multicomputer. ACM Journal on Emerging Technologies in Computing Systems (JETC), 3 (4): 1\u201323, 2008. 10.1145\/1324177.1324179.","DOI":"10.1145\/1324177.1324179"},{"key":"84","doi-asserted-by":"publisher","unstructured":"R. Van Meter, T. D. Ladd, A. G. Fowler, and Y. Yamamoto. Distributed quantum computation architecture using semiconductor nanophotonics. International Journal of Quantum Information, 8 (01n02): 295\u2013323, 2010. 10.1142\/S0219749910006435. arXiv:0906.2686.","DOI":"10.1142\/S0219749910006435"},{"key":"85","doi-asserted-by":"publisher","unstructured":"P. C. van Oorschot and M. J. Wiener. On Diffie-Hellman Key Agreement with Short Exponents. In Advances in Cryptology \u2013 EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science (LNCS), pages 332\u2013343. Springer, 1996. 10.1007\/3-540-68339-9_29.","DOI":"10.1007\/3-540-68339-9_29"},{"key":"86","doi-asserted-by":"publisher","unstructured":"V. Vedral, A. Barenco, and A. Ekert. Quantum networks for elementary arithmetic operations. Physical Review A, 54 (1): 147\u2013153, 1996. 10.1103\/PhysRevA.54.147. arXiv:quant-ph\/9511018.","DOI":"10.1103\/PhysRevA.54.147"},{"key":"87","doi-asserted-by":"publisher","unstructured":"M. G. Whitney, N. Isailovic, Y. Patel, and J. Kubiatowicz. A fault tolerant, area efficient architecture for Shor's factoring algorithm. In Proceedings of the 36th Annual International Symposium on Computer Architecture, pages 383\u2013394. ACM, 2009. 10.1145\/1555754.1555802.","DOI":"10.1145\/1555754.1555802"},{"key":"88","unstructured":"Wikipedia. Timeline of quantum computing. https:\/\/en.wikipedia.org\/wiki\/Timeline_of_quantum_computing, 2018. URL https:\/\/en.wikipedia.org\/wiki\/Timeline_of_quantum_computing. Accessed: 2018-12-18."},{"key":"89","unstructured":"C. Zalka. Fast versions of Shor's quantum factoring algorithm. arXiv preprint quant-ph\/9806084, 1998. URL https:\/\/arxiv.org\/abs\/quant-ph\/9806084."},{"key":"90","unstructured":"C. Zalka. Shor's algorithm with fewer (pure) qubits. arXiv preprint quant-ph\/0601097, 2006. URL https:\/\/arxiv.org\/abs\/quant-ph\/0601097."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-15-433\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T18:28:51Z","timestamp":1618511331000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-15-433\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":91,"URL":"https:\/\/doi.org\/10.22331\/q-2021-04-15-433","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,15]]},"article-number":"433"}}