{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T06:59:32Z","timestamp":1777964372938,"version":"3.51.4"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032018779","type":"print"},{"value":"9783032018786","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-032-01878-6_13","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T18:08:58Z","timestamp":1755367738000},"page":"384-415","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Reducing the\u00a0Number of\u00a0Qubits in\u00a0Quantum Factoring"],"prefix":"10.1007","author":[{"given":"Cl\u00e9mence","family":"Chevignard","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4997-2276","authenticated-orcid":false,"given":"Pierre-Alain","family":"Fouque","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1329-8630","authenticated-orcid":false,"given":"Andr\u00e9","family":"Schrottenloher","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"issue":"4","key":"13_CR1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.8.041015","volume":"8","author":"R Babbush","year":"2018","unstructured":"Babbush, R., et al.: Encoding electronic spectra in quantum circuits with linear t complexity. Phys. Rev. X 8(4), 041015 (2018). https:\/\/doi.org\/10.1103\/PhysRevX.8.041015","journal-title":"Phys. Rev. X"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Beauregard, S.: Circuit for Shor\u2019s algorithm using $$2n+ 3$$ qubits. arXiv preprint quant-ph\/0205095 (2002)","DOI":"10.26421\/QIC3.2-8"},{"key":"13_CR3","unstructured":"Bernstein, D.J.: Multidigit modular multiplication with the explicit Chinese remainder theorem. Chapter 4 in \u201cDetecting perfect powers in essentially linear time, and other studies in computational number theory\u201d, Ph.D. dissertation, University of California at Berkeley (1995). https:\/\/cr.yp.to\/papers\/mmecrt-19950518-retypeset20220326.pdf"},{"issue":"257","key":"13_CR4","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1090\/S0025-5718-06-01849-7","volume":"76","author":"DJ Bernstein","year":"2007","unstructured":"Bernstein, D.J., Sorenson, J.P.: Modular exponentiation via the explicit Chinese remainder theorem. Math. Comput. 76(257), 443\u2013454 (2007). https:\/\/doi.org\/10.1090\/S0025-5718-06-01849-7","journal-title":"Math. Comput."},{"issue":"5","key":"13_CR5","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.V.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"key":"13_CR6","unstructured":"Chevignard, C., Fouque, P., Schrottenloher, A.: Reducing the number of qubits in quantum factoring. IACR Cryptol. ePrint Arch. p.\u00a0222 (2024). https:\/\/eprint.iacr.org\/2024\/222"},{"key":"13_CR7","unstructured":"Draper, T.G.: Addition on a quantum computer. arXiv preprint quant-ph\/0008033 (2000)"},{"issue":"11","key":"13_CR8","doi-asserted-by":"publisher","first-page":"2313","DOI":"10.1007\/S10623-020-00783-2","volume":"88","author":"M Eker\u00e5","year":"2020","unstructured":"Eker\u00e5, M.: On post-processing in the quantum algorithm for computing short discrete logarithms. Des. Codes Cryptogr. 88(11), 2313\u20132335 (2020). https:\/\/doi.org\/10.1007\/S10623-020-00783-2","journal-title":"Des. Codes Cryptogr."},{"issue":"6","key":"13_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/S11128-021-03069-1","volume":"20","author":"M Eker\u00e5","year":"2021","unstructured":"Eker\u00e5, M.: On completely factoring any integer efficiently in a single run of an order-finding algorithm. Quantum Inf. Process. 20(6), 205 (2021). https:\/\/doi.org\/10.1007\/S11128-021-03069-1","journal-title":"Quantum Inf. Process."},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1515\/JMC-2020-0006","volume":"15","author":"M Eker\u00e5","year":"2021","unstructured":"Eker\u00e5, M.: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. J. Math. Cryptol. 15(1), 359\u2013407 (2021). https:\/\/doi.org\/10.1515\/JMC-2020-0006","journal-title":"J. Math. Cryptol."},{"key":"13_CR11","doi-asserted-by":"publisher","unstructured":"Eker\u00e5, M.: On the success probability of the quantum algorithm for the short DLP. CoRR abs\/2309.01754 (2023). https:\/\/doi.org\/10.48550\/ARXIV.2309.01754","DOI":"10.48550\/ARXIV.2309.01754"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Eker\u00e5, M., G\u00e4rtner, J.: Extending regev\u2019s factoring algorithm to compute discrete logarithms pp. 211\u2013242 (2024)","DOI":"10.1007\/978-3-031-62746-0_10"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-319-59879-6_20","volume-title":"Post-Quantum Cryptography","author":"M Eker\u00e5","year":"2017","unstructured":"Eker\u00e5, M., H\u00e5stad, J.: Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 347\u2013363. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-59879-6_20"},{"key":"13_CR14","unstructured":"Gidney, C.: Factoring with $$n+ 2$$ clean qubits and $$n-1$$ dirty qubits. arXiv preprint arXiv:1706.07884 (2017)"},{"key":"13_CR15","unstructured":"Gidney, C.: Approximate encoded permutations and piecewise quantum adders. arXiv preprint arXiv:1905.08488 (2019)"},{"key":"13_CR16","unstructured":"Gidney, C.: Windowed quantum arithmetic. arXiv preprint arXiv:1905.07682 (2019)"},{"key":"13_CR17","doi-asserted-by":"publisher","unstructured":"Gidney, C., Eker\u00e5, M.: 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"},{"issue":"17","key":"13_CR18","doi-asserted-by":"publisher","first-page":"3228","DOI":"10.1103\/PhysRevLett.76.3228","volume":"76","author":"RB Griffiths","year":"1996","unstructured":"Griffiths, R.B., Niu, C.S.: Semiclassical Fourier transform for quantum computation. Phys. Rev. Lett. 76(17), 3228 (1996). https:\/\/doi.org\/10.1103\/PhysRevLett.76.3228","journal-title":"Phys. Rev. Lett."},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/978-3-030-44223-1_23","volume-title":"Post-Quantum Cryptography","author":"T H\u00e4ner","year":"2020","unstructured":"H\u00e4ner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M.: Improved quantum circuits for elliptic curve discrete logarithms. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 425\u2013444. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-44223-1_23"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"H\u00e4ner, T., Roetteler, M., Svore, K.M.: Factoring using $$2n+ 2$$ qubits with toffoli based modular multiplication. arXiv preprint arXiv:1611.07995 (2016)","DOI":"10.26421\/QIC17.7-8-7"},{"issue":"2","key":"13_CR21","doi-asserted-by":"publisher","first-page":"563","DOI":"10.4007\/annals.2021.193.2.4","volume":"193","author":"D Harvey","year":"2021","unstructured":"Harvey, D., Van Der Hoeven, J.: Integer multiplication in time $$\\cal{O} (n \\log n)$$. Ann. Math. 193(2), 563\u2013617 (2021)","journal-title":"Ann. Math."},{"key":"13_CR22","unstructured":"Kahanamoku-Meyer, G.D., Yao, N.Y.: Fast quantum integer multiplication with zero ancillas (2024)"},{"key":"13_CR23","doi-asserted-by":"publisher","unstructured":"May, A., Schlieper, L.: Quantum period finding is compression robust. IACR Trans. Symmetric Cryptol. 2022(1), 183\u2013211 (2022). https:\/\/doi.org\/10.46586\/TOSC.V2022.I1.183-211","DOI":"10.46586\/TOSC.V2022.I1.183-211"},{"issue":"190","key":"13_CR24","first-page":"839","volume":"54","author":"PL Montgomery","year":"1990","unstructured":"Montgomery, P.L., Silverman, R.D.: An FFT extension to the $$p-1$$ factoring algorithm. Math. Comput. 54(190), 839\u2013854 (1990)","journal-title":"Math. Comput."},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Nielsen, M.A., Chuang, I.: Quantum computation and quantum information (2002)","DOI":"10.1119\/1.1463744"},{"key":"13_CR26","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/bf01933667","volume":"15","author":"JM Pollard","year":"1975","unstructured":"Pollard, J.M.: A monte Carlo method for factorization. BIT Numer. Math. 15, 331\u2013334 (1975). https:\/\/doi.org\/10.1007\/bf01933667","journal-title":"BIT Numer. Math."},{"key":"13_CR27","doi-asserted-by":"publisher","unstructured":"Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023). https:\/\/doi.org\/10.5281\/zenodo.2573505","DOI":"10.5281\/zenodo.2573505"},{"key":"13_CR28","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-031-68391-6_4","volume-title":"CRYPTO 2024","author":"S Ragavan","year":"2024","unstructured":"Ragavan, S., Vaikuntanathan, V.: Space-efficient and noise-robust quantum factoring. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024. LNCS, vol. 14925, pp. 107\u2013140. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-68391-6_4"},{"key":"13_CR29","unstructured":"Regev, O.: An efficient quantum factoring algorithm. CoRR abs\/2308.06572 (2023)"},{"key":"13_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/3-540-45353-9_24","volume-title":"Topics in Cryptology \u2014 CT-RSA 2001","author":"J-P Seifert","year":"2001","unstructured":"Seifert, J.-P.: Using fewer qubits in Shor\u2019s factorization algorithm via simultaneous Diophantine approximation. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 319\u2013327. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45353-9_24"},{"issue":"5","key":"13_CR31","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: 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."},{"issue":"5","key":"13_CR32","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"DR Simon","year":"1997","unstructured":"Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474\u20131483 (1997)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"13_CR33","first-page":"184","volume":"6","author":"Y Takahashi","year":"2006","unstructured":"Takahashi, Y., Kunihiro, N.: A quantum circuit for Shor\u2019s factoring algorithm using $$2n+ 2$$ qubits. Quantum Inf. Comput. 6(2), 184\u2013192 (2006)","journal-title":"Quantum Inf. Comput."},{"key":"13_CR34","unstructured":"Zalka, C.: Fast versions of Shor\u2019s quantum factoring algorithm. arXiv preprint quant-ph\/9806084 (1998)"},{"key":"13_CR35","unstructured":"Zalka, C.: Shor\u2019s algorithm with fewer (pure) qubits. arXiv preprint quant-ph\/0601097 (2006)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01878-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T15:13:06Z","timestamp":1757430786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01878-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032018779","9783032018786"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01878-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}