{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T06:36:13Z","timestamp":1770705373077,"version":"3.49.0"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031627453","type":"print"},{"value":"9783031627460","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-62746-0_10","type":"book-chapter","created":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T09:02:26Z","timestamp":1718010146000},"page":"211-242","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Extending Regev\u2019s Factoring Algorithm to\u00a0Compute Discrete Logarithms"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7061-2374","authenticated-orcid":false,"given":"Martin","family":"Eker\u00e5","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3724-2914","authenticated-orcid":false,"given":"Joel","family":"G\u00e4rtner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"10_CR1","unstructured":"Coppersmith, D.: An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph\/0201067 (2002). (Also IBM Research Report RC\u00a019642)"},{"key":"10_CR2","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":"11","key":"10_CR3","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)","journal-title":"Des. Codes Cryptogr."},{"issue":"1","key":"10_CR4","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)","journal-title":"J. Math. Cryptol."},{"issue":"205","key":"10_CR5","first-page":"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. Proc. 20(205), 1\u201314 (2021)","journal-title":"Quantum Inf. Proc."},{"key":"10_CR6","doi-asserted-by":"publisher","unstructured":"Eker\u00e5, M.: On the success probability of quantum order finding. ACM Trans. Quantum Comput. 5(2), Article no. 11, 1\u201340 (2024). https:\/\/doi.org\/10.1145\/3655026","DOI":"10.1145\/3655026"},{"key":"10_CR7","unstructured":"Eker\u00e5, M.: Revisiting Shor\u2019s quantum algorithm for computing general discrete logarithms. arXiv:1905.09084v3 (2019\u20132023)"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Eker\u00e5, M.: On the success probability of the quantum algorithm for the short DLP. arXiv:2309.01754v1 (2023)","DOI":"10.1145\/3655026"},{"key":"10_CR9","unstructured":"Eker\u00e5, M., G\u00e4rtner, J.: Simulating Regev\u2019s quantum factoring algorithm and Eker\u00e5\u2013G\u00e4rtner\u2019s extensions to discrete logarithm finding, order finding and factoring via order finding. GitHub repository ekera\/regevnum (2023\u20132024)"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"433","DOI":"10.22331\/q-2021-04-15-433","volume":"5","author":"C Gidney","year":"2021","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)","journal-title":"Quantum"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Hhan, M., Yamakawa, T., Yun, A.: Quantum complexity for discrete logarithms and related problems. arXiv:2307.03065 (2023)","DOI":"10.1007\/978-3-031-68391-6_1"},{"key":"10_CR12","unstructured":"Kaliski, B.S., Jr.: A Quantum \u201cMagic Box\u201d for the Discrete Logarithm Problem. IACR ePrint 2017\/745 (2017)"},{"key":"10_CR13","unstructured":"Litinski, D.: How to compute a 256-bit elliptic curve private key with only 50\u00a0million Toffoli gates. arXiv:2306.08585v1 (2023)"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"13","author":"GL Miller","year":"1976","unstructured":"Miller, G.L.: Riemann\u2019s hypothesis and tests for primality. J. Comput. Syst. Sci. 13(3), 300\u2013317 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10_CR16","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/TIT.1978.1055817","volume":"24","author":"S Pohlig","year":"1978","unstructured":"Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF($$p$$) and its cryptographic significance. IEEE Trans. Inf. Theory 24(1), 106\u2013110 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20132","key":"10_CR17","first-page":"191","volume":"43","author":"C Pomerance","year":"2001","unstructured":"Pomerance, C.: The expected number of random elements to generate a finite Abelian group. Period. Math. Hungar. 43(1\u20132), 191\u2013198 (2001)","journal-title":"Period. Math. Hungar."},{"key":"10_CR18","unstructured":"Ragavan, S., Vaikuntanathan, V.: Optimizing space in Regev\u2019s factoring algorithm. arXiv:2310.00899v1 (2023)"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Ragavan, S., Vaikuntanathan, V.: Space-efficient and noise-robust quantum factoring. arXiv:2310.00899v3 (2024)","DOI":"10.1007\/978-3-031-68391-6_4"},{"key":"10_CR20","unstructured":"Regev, O.: An efficient quantum factoring algorithm. arXiv:2308.06572v3 (2023)"},{"key":"10_CR21","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":"1\u20133","key":"10_CR22","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"C-P Schnorr","year":"1994","unstructured":"Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(1\u20133), 181\u2013199 (1994)","journal-title":"Math. Program."},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS\u00a01994, pp. 124\u2013134 (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"issue":"5","key":"10_CR24","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)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-62746-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T13:18:32Z","timestamp":1732195112000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-62746-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031627453","9783031627460"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-62746-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"11 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"PQCrypto","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Post-Quantum Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Oxford","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pqcrypto2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.maths.ox.ac.uk\/events\/conferences\/pqcrypto-2024","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}