{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T07:18:01Z","timestamp":1770275881307,"version":"3.49.0"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T00:00:00Z","timestamp":1770163200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T00:00:00Z","timestamp":1770163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00145-026-09572-x","type":"journal-article","created":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T17:20:31Z","timestamp":1770225631000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient and Noise-Robust Quantum Factoring"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9628-2258","authenticated-orcid":false,"given":"Seyoon","family":"Ragavan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2666-0045","authenticated-orcid":false,"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,4]]},"reference":[{"key":"9572_CR1","unstructured":"V. Acciaro, The probability of generating some common families of finite groups. Utilitas Math. (1996), pp.\u00a0243\u2013254. URL: https:\/\/www.scopus.com\/pages\/publications\/0030464567?inward=."},{"key":"9572_CR2","doi-asserted-by":"publisher","unstructured":"F. Arute et al, Quantum supremacy using a programmable superconducting processor. Nature, 574(7779), 505\u2013510 (2019). https:\/\/doi.org\/10.1038\/s41586-019-1666-5. ISSN: 1476-4687.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"9572_CR3","doi-asserted-by":"publisher","unstructured":"S. Beauregard, Circuit for Shor\u2019s algorithm using 2n+3 qubits. Quantum Inf. Comput. 3(2), 175\u2013185 (2003) https:\/\/doi.org\/10.26421\/QIC3.2-8","DOI":"10.26421\/QIC3.2-8"},{"issue":"2","key":"9572_CR4","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1103\/PhysRevA.54.1034","volume":"54","author":"D Beckman","year":"1996","unstructured":"D. Beckman et al, Efficient networks for quantum factoring. Phys. Rev. A. 54(2), 1034 (1996) https:\/\/doi.org\/10.1103\/PhysRevA.54.1034.","journal-title":"Phys. Rev. A."},{"key":"9572_CR5","doi-asserted-by":"publisher","unstructured":"C.H. Bennett, Logical Reversibility of Computation. IBM J. Res. Development 17(6), 525\u2013532, (1973). Conference Name: IBM Journal of Research and Development, ISSN: 0018-8646. https:\/\/doi.org\/10.1147\/rd.176.0525.","DOI":"10.1147\/rd.176.0525"},{"key":"9572_CR6","doi-asserted-by":"publisher","unstructured":"C.H. Bennett, Time\/Space Trade-Offs for Reversible Computation. SIAM J. Comput. 18(4), 766\u2013776 (1989). Publisher: Society for Industrial and Applied Mathematics, ISSN: 0097-5397. https:\/\/doi.org\/10.1137\/0218053.","DOI":"10.1137\/0218053"},{"issue":"10","key":"9572_CR7","doi-asserted-by":"publisher","first-page":"52","DOI":"10.4304\/jcp.2.10.52-62","volume":"2","author":"A Byrne","year":"2007","unstructured":"A. Byrne et al, Comparison of Simple Power Analysis Attack Resistant Algorithms for an Elliptic Curve Cryptosystem. J. Comput. 2(10), 52-62, (2007). https:\/\/doi.org\/10.4304\/jcp.2.10.52-62.","journal-title":"J. Comput."},{"key":"9572_CR8","doi-asserted-by":"publisher","unstructured":"J.-Y. Cai, Shor\u2019s algorithm does not factor large integers in the presence of noise. Sci. China Inform. Sci. 67(7), 173501 (2024). https:\/\/doi.org\/10.1007\/s11432-023-3961-3. ISSN: 1869-1919.","DOI":"10.1007\/s11432-023-3961-3"},{"key":"9572_CR9","doi-asserted-by":"publisher","unstructured":"E. Campbell, A. Khurana, A. Montanaro, Applying quantum algorithms to constraint satisfaction problems. Quantum 3, 167 (2019), https:\/\/doi.org\/10.22331\/q-2019-07-18-167. ISSN: 2521-327X.","DOI":"10.22331\/q-2019-07-18-167"},{"key":"9572_CR10","doi-asserted-by":"publisher","unstructured":"S. Chen et al, The complexity of NISQ. Nature Commun 14(1), (2023). ISSN: 2041-1723. https:\/\/doi.org\/10.1038\/s41467-023-41217-6.","DOI":"10.1038\/s41467-023-41217-6"},{"key":"9572_CR11","doi-asserted-by":"publisher","unstructured":"C. Chevignard, P.-A. Fouque, A. Schrottenloher, Reducing the Number of Qubits in Quantum Factoring. in Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II. Ed. by Yael Tauman Kalai and Seny F. Kamara. Vol.\u00a016001. Lecture Notes in Computer Science. Springer, 2025, pp.\u00a0384\u2013415. https:\/\/doi.org\/10.1007\/978-3-032-01878-6_13.","DOI":"10.1007\/978-3-032-01878-6_13"},{"key":"9572_CR12","doi-asserted-by":"publisher","unstructured":"R. Cleve, J. Watrous, Fast parallel circuits for the quantum Fourier transform\u201d. in 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA. (IEEE Computer Society, 2000), pp.\u00a0526\u2013536.https:\/\/doi.org\/10.1109\/SFCS.2000.892140.","DOI":"10.1109\/SFCS.2000.892140"},{"key":"9572_CR13","doi-asserted-by":"publisher","unstructured":"S.A. Cook, S.O. Aanderaa, On the Minimum Computation Time of Functions. Trans. Am. Math. Soc. 142, pp.\u00a0291\u2013314 (1969). ISSN: 00029947. https:\/\/doi.org\/10.2307\/1995359.","DOI":"10.2307\/1995359"},{"key":"9572_CR14","doi-asserted-by":"publisher","unstructured":"D. Coppersmith, An approximate Fourier transform useful in quantum factoring. (2002). https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0201067.","DOI":"10.48550\/ARXIV.QUANT-PH\/0201067"},{"issue":"6","key":"9572_CR15","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"1976","unstructured":"W. Diffie, M. E. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644\u2013654 (1976), https:\/\/doi.org\/10.1109\/TIT.1976.1055638.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9572_CR16","doi-asserted-by":"publisher","unstructured":"T.G. Draper. Addition on a Quantum Computer. (2000). https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0008033.","DOI":"10.48550\/ARXIV.QUANT-PH\/0008033"},{"key":"9572_CR17","unstructured":"M. Eker\u00e5, J. G\u00e4rtner, Personal communication. (2024)"},{"key":"9572_CR18","doi-asserted-by":"publisher","unstructured":"M. Eker\u00e5, J. G\u00e4rtner, A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography. IACR Commun. Cryptology 2(1) (2025). ISSN: 3006-5496. https:\/\/doi.org\/10.62056\/ayzojb0kr.","DOI":"10.62056\/ayzojb0kr"},{"key":"9572_CR19","doi-asserted-by":"publisher","unstructured":"M. Eker\u00e5, J. G\u00e4rtner, Extending Regev\u2019s Factoring Algorithm to\u00a0Compute Discrete Logarithms. Post-Quantum Cryptography. Ed. by M.-J. Saarinen, D. Smith-Tone. (Springer Nature Switzerland, Cham, 2024), pp.\u00a0211\u2013242. https:\/\/doi.org\/10.1007\/978-3-031-62746-0_10. ISBN: 978-3-031-62746-0.","DOI":"10.1007\/978-3-031-62746-0_10"},{"key":"9572_CR20","doi-asserted-by":"publisher","unstructured":"M. Eker\u00e5, J. H\u00e5stad, Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. in Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings. Ed. by T. Lange, T. Takagi. Vol.\u00a010346. Lecture Notes in Computer Science. (Springer, 2017), pp.\u00a0347\u2013363.https:\/\/doi.org\/10.1007\/978-3-319-59879-6_20","DOI":"10.1007\/978-3-319-59879-6_20"},{"issue":"3","key":"9572_CR21","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.86.032324","volume":"86","author":"AG Fowler","year":"2012","unstructured":"A.G. Fowler et al, Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A. 86(3), 032324 (2012).https:\/\/doi.org\/10.1103\/physreva.86.032324. ISSN: 1094-1622.","journal-title":"Phys. Rev. A."},{"issue":"4","key":"9572_CR22","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T El Gamal","year":"1985","unstructured":"T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469\u2013472 (1985). https:\/\/doi.org\/10.1109\/TIT.1985.1057074.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9572_CR23","doi-asserted-by":"publisher","unstructured":"C. Gidney, Asymptotically Efficient Quantum Karatsuba Multiplication. (2019). https:\/\/doi.org\/10.48550\/ARXIV.1904.07356.","DOI":"10.48550\/ARXIV.1904.07356"},{"key":"9572_CR24","unstructured":"C. Gidney, Comment on Scott Aaronson\u2019s blog. (2023). https:\/\/scottaaronson.blog\/?p=7489#comment-1953303."},{"key":"9572_CR25","doi-asserted-by":"publisher","unstructured":"C. Gidney, Factoring with n+2 clean qubits and n-1 dirty qubits. (2017). https:\/\/doi.org\/10.48550\/ARXIV.1706.07884.","DOI":"10.48550\/ARXIV.1706.07884"},{"key":"9572_CR26","unstructured":"C. Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits. (2025). arXiv: 2505.15917 [quant-ph]."},{"key":"9572_CR27","doi-asserted-by":"publisher","unstructured":"C. Gidney, Windowed quantum arithmetic. (2019). https:\/\/doi.org\/10.48550\/ARXIV.1905.07682.","DOI":"10.48550\/ARXIV.1905.07682"},{"key":"9572_CR28","doi-asserted-by":"publisher","unstructured":"C. Gidney, M. Eker\u00e5, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433 (2021). https:\/\/doi.org\/10.22331\/q-2021-04-15-433.","DOI":"10.22331\/q-2021-04-15-433"},{"key":"9572_CR29","doi-asserted-by":"publisher","unstructured":"L. Grover, T. Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. (2002). https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0208112.","DOI":"10.48550\/ARXIV.QUANT-PH\/0208112"},{"key":"9572_CR30","doi-asserted-by":"publisher","unstructured":"T. H\u00e4ner, M. Roetteler, K.M. Svore. Factoring using $$2n+2$$ qubits with Toffoli based modular multiplication. Quantum Inf. Comput. 17(7&8), 673\u2013684 (2017). https:\/\/doi.org\/10.26421\/QIC17.7-8-7.","DOI":"10.26421\/QIC17.7-8-7"},{"issue":"2","key":"9572_CR31","doi-asserted-by":"publisher","first-page":"563","DOI":"10.4007\/annals.2021.193.2.4","volume":"193","author":"D Harvey","year":"2021","unstructured":"D. Harvey, J. van der Hoeven. Integer multiplication in time $${O}(n\\log n)$$. Annal. Math. 193(2), 563-617 (2021). https:\/\/doi.org\/10.4007\/annals.2021.193.2.4.","journal-title":"Annal. Math."},{"key":"9572_CR32","doi-asserted-by":"publisher","unstructured":"G.D. Kahanamoku-Meyer, S. Ragavan, K. Van Kirk. Parallel Spooky Pebbling Makes Regev Factoring More Practical. (2025). https:\/\/doi.org\/10.48550\/ARXIV.2510.08432. arXiv:2510.08432 [quant-ph].","DOI":"10.48550\/ARXIV.2510.08432"},{"key":"9572_CR33","doi-asserted-by":"publisher","unstructured":"G.D. Kahanamoku-Meyer, N.Y. Yao. Fast quantum integer multiplication with zero ancillas. (2024). https:\/\/doi.org\/10.48550\/ARXIV.2403.18006.","DOI":"10.48550\/ARXIV.2403.18006"},{"key":"9572_CR34","unstructured":"B.S. Kaliski Jr. A Quantum \u201cMagic Box\u201d for the Discrete Logarithm Problem. Cryptology ePrint Archive, Paper 2017\/745. (2017). https:\/\/eprint.iacr.org\/2017\/745."},{"key":"9572_CR35","doi-asserted-by":"publisher","unstructured":"B. S. Kaliski Jr. Targeted Fibonacci Exponentiation. (2017). https:\/\/doi.org\/10.48550\/ARXIV.1711.02491.","DOI":"10.48550\/ARXIV.1711.02491"},{"key":"9572_CR36","unstructured":"A.A. Karatsuba, Y.P. Ofman. Multiplication of many-digital numbers by automatic computers\u201d. Doklady Akademii Nauk. Vol.\u00a0145. Russian Academy of Sciences. pp.\u00a0293\u2013294 (1962). https:\/\/www.mathnet.ru\/php\/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng."},{"issue":"6","key":"9572_CR37","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.ipl.2007.11.016","volume":"106","author":"ST Klein","year":"2008","unstructured":"S.T. Klein. Should one always use repeated squaring for modular exponentiation? Inf. Proc. Lett. 106(6), 232\u2013237 (2008), https:\/\/doi.org\/10.1016\/j.ipl.2007.11.016.","journal-title":"Inf. Proc. Lett."},{"key":"9572_CR38","doi-asserted-by":"publisher","unstructured":"A.K. Lenstra, H.W. Lenstra, L. Lov\u00e1sz. Factoring polynomials with rational coefficients. Math. Annalen 261(4), 515\u2013534, (1982), ISSN: 1432-1807. https:\/\/doi.org\/10.1007\/bf01457454.","DOI":"10.1007\/bf01457454"},{"key":"9572_CR39","doi-asserted-by":"publisher","unstructured":"A.K. Lenstra et\u00a0al. The Number Field Sieve. in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA. Ed. by H.Ortiz. ACM, pp.\u00a0564\u2013572 (1990). https:\/\/doi.org\/10.1145\/100216.100295.","DOI":"10.1145\/100216.100295"},{"key":"9572_CR40","doi-asserted-by":"publisher","unstructured":"R.Y. Levine, A.T. Sherman, A Note on Bennett\u2019s Time-Space Tradeoff for Reversible Computation. SIAM Journal on Computing 19(4), 673\u2013677 (1990). Publisher: Society for Industrial and Applied Mathematics, ISSN: 0097-5397. https:\/\/doi.org\/10.1137\/0219046.","DOI":"10.1137\/0219046"},{"key":"9572_CR41","doi-asserted-by":"publisher","unstructured":"N. Meloni. New Point Addition Formulae for ECC Applications. in Arithmetic of Finite Fields. Springer Berlin Heidelberg, pp.\u00a0189\u2013201. 9783540730743. https:\/\/doi.org\/10.1007\/978-3-540-73074-3_15.","DOI":"10.1007\/978-3-540-73074-3_15"},{"key":"9572_CR42","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1090\/S0025-5718-07-02017-0","volume":"77","author":"N M\u00f6ller","year":"2008","unstructured":"N. M\u00f6ller. On Sch\u00f6nhage\u2019s algorithm and subquadratic integer GCD computation. Math. Comput. 77, 589\u2013607 (2008).","journal-title":"Math. Comput."},{"key":"9572_CR43","doi-asserted-by":"publisher","unstructured":"C. Pilatte, Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms. (2024).https:\/\/doi.org\/10.48550\/ARXIV.2404.16450.","DOI":"10.48550\/ARXIV.2404.16450"},{"key":"9572_CR44","doi-asserted-by":"publisher","unstructured":"C. Pomerance, The expected number of random elements to generate a finite abelian group. Periodica Mathematica Hungarica 43(1\u20132), 191\u2013198 (2002). https:\/\/doi.org\/10.1023\/a:1015250102792. ISSN: 1588-2829.","DOI":"10.1023\/a:1015250102792"},{"key":"9572_CR45","doi-asserted-by":"publisher","unstructured":"J. Proos, C. Zalka. Shor\u2019s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. 3(4) 317\u2013344 (2003). https:\/\/doi.org\/10.26421\/QIC3.4-3.","DOI":"10.26421\/QIC3.4-3"},{"key":"9572_CR46","unstructured":"S. Ragavan. Regev Factoring Beyond Fibonacci: Optimizing Prefactors. Cryptology ePrint Archive, Paper 2024\/636. https:\/\/eprint.iacr.org\/2024\/636. (2024)."},{"key":"9572_CR47","doi-asserted-by":"publisher","unstructured":"S. Ragavan, V. Vaikuntanathan. Space-Efficient and Noise-Robust Quantum Factoring. in Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VI. Ed. by L. Reyzin, D. Stebila. Vol.\u00a014925. Lecture Notes in Computer Science. (Springer, 2024), pp.\u00a0107\u2013140. https:\/\/doi.org\/10.1007\/978-3-031-68391-6_4.","DOI":"10.1007\/978-3-031-68391-6_4"},{"key":"9572_CR48","doi-asserted-by":"publisher","unstructured":"O. Regev, An Efficient Quantum Factoring Algorithm. J. ACM 72(1), (2025). ISSN: 0004-5411.https:\/\/doi.org\/10.1145\/3708471.","DOI":"10.1145\/3708471"},{"key":"9572_CR49","doi-asserted-by":"publisher","unstructured":"O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1\u201334:40 (2009). https:\/\/doi.org\/10.1145\/1568318.1568324.","DOI":"10.1145\/1568318.1568324"},{"key":"9572_CR50","unstructured":"M. Remaud. Personal communication. (2024)."},{"key":"9572_CR51","doi-asserted-by":"publisher","unstructured":"R. Rines, I. Chuang, High Performance Quantum Modular Multipliers (2018). https:\/\/doi.org\/10.48550\/ARXIV.1801.01081.","DOI":"10.48550\/ARXIV.1801.01081"},{"issue":"2","key":"9572_CR52","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"R.L. Rivest, A. Shamir, L.M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978). https:\/\/doi.org\/10.1145\/359340.359342.","journal-title":"Commun. ACM"},{"key":"9572_CR53","doi-asserted-by":"publisher","unstructured":"M. Roetteler et\u00a0al., Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. in Advances in Cryptology \u2013 ASIACRYPT 2017. (Springer International Publishing, 2017), pp.\u00a0241\u2013270. ISBN: 9783319706979. https:\/\/doi.org\/10.1007\/978-3-319-70697-9_9.","DOI":"10.1007\/978-3-319-70697-9_9"},{"issue":"2","key":"9572_CR54","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/bf00289520","volume":"1","author":"A Sch\u00f6nhage","year":"1971","unstructured":"A. Sch\u00f6nhage. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica 1(2), 139\u2013144 (1971).https:\/\/doi.org\/10.1007\/bf00289520. ISSN: 1432-0525","journal-title":"Acta Informatica"},{"key":"9572_CR55","doi-asserted-by":"publisher","unstructured":"A. Sch\u00f6nhage, V. Strassen. Schnelle Multiplikation gro\u00dfer Zahlen. Computing 7(3\u20134), 281\u2013292, (1971), ISSN: 1436-5057. https:\/\/doi.org\/10.1007\/bf02242355.","DOI":"10.1007\/bf02242355"},{"key":"9572_CR56","doi-asserted-by":"publisher","unstructured":"J.-P. Seifert, Using Fewer Qubits in Shor\u2019s Factorization Algorithm via Simultaneous Diophantine Approximation. in Topics in Cryptology \u2014 CT-RSA 2001. (Springer Berlin Heidelberg, 2001), pp.\u00a0319\u2013327. ISBN: 9783540453536. https:\/\/doi.org\/10.1007\/3-540-45353-9_24.","DOI":"10.1007\/3-540-45353-9_24"},{"key":"9572_CR57","doi-asserted-by":"publisher","unstructured":"P.W. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring. in 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994. (IEEE Computer Society, 1994), pp.\u00a0124\u2013134.https:\/\/doi.org\/10.1109\/SFCS.1994.365700.","DOI":"10.1109\/SFCS.1994.365700"},{"issue":"5","key":"9572_CR58","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"P.W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997). https:\/\/doi.org\/10.1137\/S0097539795293172.","journal-title":"SIAM J. Comput."},{"key":"9572_CR59","doi-asserted-by":"crossref","unstructured":"Y. Takahashi, N. Kunihiro, A quantum circuit for Shor\u2019s factoring algorithm using $$2n+2$$ qubits. Quantum Info. Comput. 6(2), 184\u2013192 (2006). ISSN: 1533-7146.","DOI":"10.26421\/QIC6.2-4"},{"key":"9572_CR60","unstructured":"K. Thull, C.K. Yap, A Unified Approach to HGCD Algorithms for polynomials and integers. (1990)."},{"key":"9572_CR61","unstructured":"A.L. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers. in Doklady Akademii Nauk. Vol.\u00a0150. 3. Russian Academy of Sciences. (1963), pp.\u00a0496\u2013498. https:\/\/www.mathnet.ru\/eng\/dan\/v150\/i3\/p496."},{"key":"9572_CR62","doi-asserted-by":"publisher","unstructured":"R.Van Meter, K.M. Itoh, Fast quantum modular exponentiation. Phys. Rev. A. 71(5), (2005). ISSN: 1094-1622. https:\/\/doi.org\/10.1103\/physreva.71.052320.","DOI":"10.1103\/physreva.71.052320"},{"key":"9572_CR63","doi-asserted-by":"publisher","unstructured":"R. D. Van Meter. Architecture of a Quantum Multicomputer Optimized for Shor\u2019s Factoring Algorithm. (2006). https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0607065.","DOI":"10.48550\/ARXIV.QUANT-PH\/0607065"},{"key":"9572_CR64","doi-asserted-by":"publisher","unstructured":"V. Vedral, A. Barenco, A. Ekert, Quantum networks for elementary arithmetic operations. Phys. Rev. A. 54(1) 147\u2013153 (1996), https:\/\/doi.org\/10.1103\/physreva.54.147, ISSN: 1094-1622","DOI":"10.1103\/physreva.54.147"},{"key":"9572_CR65","doi-asserted-by":"publisher","unstructured":"C. Zalka, Shor\u2019s algorithm with fewer (pure) qubits. (2006). https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0601097","DOI":"10.48550\/ARXIV.QUANT-PH\/0601097"},{"key":"9572_CR66","unstructured":"E. Zeckendorf, Repr\u00e9sentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. French. Bull. Soc. R. Sci. Li\u00e8ge 41, 179\u2013182 (1972). ISSN: 0037-9565."}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-026-09572-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-026-09572-x","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-026-09572-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T17:20:35Z","timestamp":1770225635000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-026-09572-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,4]]},"references-count":66,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["9572"],"URL":"https:\/\/doi.org\/10.1007\/s00145-026-09572-x","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,4]]},"assertion":[{"value":"13 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"14"}}