{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T01:06:05Z","timestamp":1793063165838,"version":"4.5.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032252906","type":"print"},{"value":"9783032252913","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-25291-3_13","type":"book-chapter","created":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T14:53:52Z","timestamp":1778165632000},"page":"371-401","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reducing the\u00a0Number of\u00a0Qubits in\u00a0Quantum Discrete Logarithms on\u00a0Elliptic Curves"],"prefix":"10.1007","author":[{"given":"Cl\u00e9mence","family":"Chevignard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4997-2276","authenticated-orcid":false,"given":"Pierre-Alain","family":"Fouque","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1329-8630","authenticated-orcid":false,"given":"Andr\u00e9","family":"Schrottenloher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,8]]},"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":"publisher","unstructured":"Banegas, G., Bernstein, D.J., van Hoof, I., Lange, T.: Concrete quantum cryptanalysis of binary elliptic curves. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2021(1), 451\u2013472 (2020). https:\/\/doi.org\/10.46586\/tches.v2021.i1.451-472, https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/8741","DOI":"10.46586\/tches.v2021.i1.451-472"},{"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."},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"208","DOI":"10.22331\/Q-2019-12-02-208","volume":"3","author":"DW Berry","year":"2019","unstructured":"Berry, D.W., Gidney, C., Motta, M., McClean, J.R., Babbush, R.: Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization. Quantum 3, 208 (2019). https:\/\/doi.org\/10.22331\/Q-2019-12-02-208","journal-title":"Quantum"},{"key":"13_CR6","doi-asserted-by":"publisher","unstructured":"Chen, L., Moody, D., Regenscheid, A., Robinson, A., Randall, K.: Recommendations for discrete logarithm-based cryptography: elliptic curve domain parameters. Technical report, NIST (2023). https:\/\/doi.org\/10.6028\/NIST.SP.800-186","DOI":"10.6028\/NIST.SP.800-186"},{"key":"13_CR7","doi-asserted-by":"publisher","unstructured":"Chevignard, C., Fouque, P., Schrottenloher, A.: Reducing the number of qubits in quantum factoring. In: CRYPTO (2). LNCS, vol. 16001, pp. 384\u2013415. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-032-01878-6_13","DOI":"10.1007\/978-3-032-01878-6_13"},{"key":"13_CR8","unstructured":"Chevignard, C., Fouque, P.A., Schrottenloher, A.: Reducing the number of qubits in quantum discrete logarithms on elliptic curves. Cryptology ePrint Archive, Paper 2026\/280 (2026). https:\/\/eprint.iacr.org\/2026\/280"},{"key":"13_CR9","unstructured":"Eker\u00e5, M.: Revisiting shor\u2019s quantum algorithm for computing general discrete logarithms. CoRR abs\/1905.09084 (2019). http:\/\/arxiv.org\/abs\/1905.09084"},{"issue":"11","key":"13_CR10","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":"1","key":"13_CR11","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_CR12","unstructured":"Eker\u00e5, M.: On factoring integers, and computing discrete logarithms and orders, quantumly. Ph.D. thesis, KTH Royal Institute of Technology (2024)"},{"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"},{"issue":"2","key":"13_CR14","doi-asserted-by":"publisher","first-page":"1242","DOI":"10.1109\/TIT.2011.2170054","volume":"58","author":"RR Farashahi","year":"2012","unstructured":"Farashahi, R.R., Shparlinski, I.E.: Pseudorandom bits from points on elliptic curves. IEEE Trans. Inf. Theory 58(2), 1242\u20131247 (2012). https:\/\/doi.org\/10.1109\/TIT.2011.2170054","journal-title":"IEEE Trans. Inf. Theory"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"74","DOI":"10.22331\/Q-2018-06-18-74","volume":"2","author":"C Gidney","year":"2018","unstructured":"Gidney, C.: Halving the cost of quantum addition. Quantum 2, 74 (2018). https:\/\/doi.org\/10.22331\/Q-2018-06-18-74","journal-title":"Quantum"},{"key":"13_CR16","unstructured":"Gidney, C.: Spooky pebble games and irreversible uncomputation (2019). https:\/\/algassert.com\/post\/1905"},{"key":"13_CR17","unstructured":"Gidney, C.: How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv preprint arXiv:2505.15917 (2025)"},{"key":"13_CR18","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":"4","key":"13_CR19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.131.040602","volume":"131","author":"\u00c9 Gouzien","year":"2023","unstructured":"Gouzien, \u00c9., Ruiz, D., Le R\u00e9gent, F.M., Guillaud, J., Sangouard, N.: Performance analysis of a repetition cat code architecture: computing 256-bit elliptic curve logarithm in 9 hours with 126 133 cat qubits. Phys. Rev. Lett. 131(4), 040602 (2023)","journal-title":"Phys. Rev. Lett."},{"key":"13_CR20","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_CR21","doi-asserted-by":"publisher","unstructured":"Jang, K., Srivastava, V., Baksi, A., Sarkar, S., Seo, H.: New quantum cryptanalysis of binary elliptic curves. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2025(2), 781\u2013804 (2025). https:\/\/doi.org\/10.46586\/tches.v2025.i2.781-804, https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/12065","DOI":"10.46586\/tches.v2025.i2.781-804"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-77026-8_4","volume-title":"Progress in Cryptology \u2013 INDOCRYPT 2007","author":"D Jao","year":"2007","unstructured":"Jao, D., Jetchev, D., Venkatesan, R.: On the bits of elliptic curve Diffie-Hellman keys. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 33\u201347. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-77026-8_4"},{"key":"13_CR23","unstructured":"Kahanamoku-Meyer, G.D., Blue, J., Bergamaschi, T., Gidney, C., Chuang, I.L.: A log-depth in-place quantum Fourier transform that rarely needs ancillas. arXiv preprint arXiv:2505.00701 (2025)"},{"key":"13_CR24","unstructured":"Kahanamoku-Meyer, G.D., Yao, N.Y.: Fast quantum integer multiplication with zero ancillas (2024)"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Kornerup, N., Sadun, J., Soloveichik, D.: Tight bounds on the spooky pebble game: Recycling qubits with measurements. Quantum 9, 1636 (2025). https:\/\/doi.org\/10.22331\/Q-2025-02-18-1636","DOI":"10.22331\/Q-2025-02-18-1636"},{"issue":"1","key":"13_CR26","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1038\/srep00260","volume":"2","author":"J Li","year":"2012","unstructured":"Li, J., Peng, X., Du, J., Suter, D.: An efficient exact quantum algorithm for the integer square-free decomposition problem. Sci. Rep. 2(1), 260 (2012)","journal-title":"Sci. Rep."},{"key":"13_CR27","unstructured":"Litinski, D.: How to compute a 256-bit elliptic curve private key with only 50 million toffoli gates. arXiv preprint arXiv:2306.08585 (2023)"},{"key":"13_CR28","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"},{"key":"13_CR29","doi-asserted-by":"publisher","unstructured":"Pornin, T.: A prime-order group with complete formulas from even-order elliptic curves. IACR Commun. Cryptol. 1(1), 10 (2024). https:\/\/doi.org\/10.62056\/AKMP-4C2H","DOI":"10.62056\/AKMP-4C2H"},{"key":"13_CR30","doi-asserted-by":"publisher","unstructured":"Proos, J., Zalka, C.: 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":"13_CR31","doi-asserted-by":"publisher","unstructured":"Regev, O.: An efficient quantum factoring algorithm. J. ACM 72(1), 10:1\u201310:13 (2025). https:\/\/doi.org\/10.1145\/3708471","DOI":"10.1145\/3708471"},{"key":"13_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-662-49890-3_16","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Renes","year":"2016","unstructured":"Renes, J., Costello, C., Batina, L.: Complete addition formulas for prime order elliptic curves. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 403\u2013428. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49890-3_16"},{"key":"13_CR33","unstructured":"Rines, R., Chuang, I.L.: High performance quantum modular multipliers. CoRR abs\/1801.01081 (2018). http:\/\/arxiv.org\/abs\/1801.01081"},{"key":"13_CR34","doi-asserted-by":"publisher","unstructured":"Rodier, F., Caullery, F., F\u00e9rard, E.: Periodic autocorrelation of sequences. Cryptogr. Commun. 16(2), 445\u2013458 (2024). https:\/\/doi.org\/10.1007\/S12095-023-00680-0","DOI":"10.1007\/S12095-023-00680-0"},{"key":"13_CR35","doi-asserted-by":"publisher","unstructured":"Shallit, J.O., Sorenson, J.: A binary algorithm for the Jacobi symbol. SIGSAM Bull. 27(1), 4\u201311 (1993). https:\/\/doi.org\/10.1145\/152379.152384","DOI":"10.1145\/152379.152384"},{"issue":"5","key":"13_CR36","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."},{"key":"13_CR37","unstructured":"Zalka, C.: Fast versions of Shor\u2019s quantum factoring algorithm. arXiv preprint quant-ph\/9806084 (1998)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2026"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-25291-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T14:54:03Z","timestamp":1778165643000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-25291-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032252906","9783032252913"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-25291-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"8 May 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 May 2026","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":"eurocrypt2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}