{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:24:43Z","timestamp":1761582283144,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100010418","name":"Institute for Information and Communications Technology Promotion","doi-asserted-by":"publisher","award":["No.2019-0-00033"],"award-info":[{"award-number":["No.2019-0-00033"]}],"id":[{"id":"10.13039\/501100010418","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"abstract":"Abstract<\/jats:title>In the previous research on solving the elliptic curve discrete logarithm problem, quantum resources were concretely estimated. In Banegas et al. (IACR Trans Cryptogr Hardw Embed Syst 2021(1):451\u2013472, 2020. https:\/\/doi.org\/10.46586\/tches.v2021.i1.451-472<\/jats:ext-link>), the quantum algorithm was optimized for binary elliptic curves, with the main optimization target being the number of the logical qubits. The division algorithm was primarily optimized in Banegas et al. (2020) since every ancillary qubit is used in the division algorithm. In this paper, we propose a new quantum division algorithm on the binary field that uses fewer qubits. Specifically, for elements in a field of $$2^n$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, our algorithm saves $$n - 3\\lfloor \\log {n} \\rfloor - 2$$<\/jats:tex-math>\n \n n<\/mml:mi>\n -<\/mml:mo>\n 3<\/mml:mn>\n \u230a<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n \u230b<\/mml:mo>\n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> qubits instead of using $$n^2 - 64n\\lfloor \\log (n) \\rfloor + O(n)$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n 64<\/mml:mn>\n n<\/mml:mi>\n \n \u230a<\/mml:mo>\n log<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u230b<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> more Toffoli gates, which leads to a more space-efficient quantum algorithm for binary elliptic curves. For the small size n<\/jats:italic> of 16, 127, 163, 233, 283 and 571, both the number of qubits and the number of Toffoli gates are actually reduced. When the size n<\/jats:italic> is 571, the reduction in ancillary qubits amounts to approximately 23% compared to the previous algorithm.<\/jats:p>","DOI":"10.1007\/s11128-023-03991-6","type":"journal-article","created":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T05:13:00Z","timestamp":1686114780000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["New space-efficient quantum algorithm for binary elliptic curves using the optimized division algorithm"],"prefix":"10.1007","volume":"22","author":[{"given":"Hyeonhak","family":"Kim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7506-4023","authenticated-orcid":false,"given":"Seokhie","family":"Hong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"key":"3991_CR1","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134 (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365700","DOI":"10.1109\/SFCS.1994.365700"},{"key":"3991_CR2","doi-asserted-by":"crossref","unstructured":"Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates for computing elliptic curve discrete logarithms. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 241\u2013270. Springer (2017)","DOI":"10.1007\/978-3-319-70697-9_9"},{"issue":"1","key":"3991_CR3","doi-asserted-by":"publisher","first-page":"451","DOI":"10.46586\/tches.v2021.i1.451-472","volume":"2021","author":"G Banegas","year":"2020","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","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"3991_CR4","unstructured":"Larasati, H.T., Putranto, D.S.C., Wardhani, R.W., Kim, H.: Reducing the Depth of Quantum FLT-Based Inversion Circuit. Cryptology ePrint Archive, Paper 2022\/463 (2022). https:\/\/eprint.iacr.org\/2022\/463"},{"key":"3991_CR5","unstructured":"Putranto, D.S.C., Wardhani, R.W., Larasati, H.T., Kim, H.: Another Concrete Quantum Cryptanalysis of Binary Elliptic Curves. Cryptology ePrint Archive, Paper 2022\/501. https:\/\/eprint.iacr.org\/2022\/501 (2022)"},{"key":"3991_CR6","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Yang, B.-Y.: Fast constant-time GCD computation and modular inversion. IACR Trans. Cryptogr. Hardw. Embed. Syst. 340\u2013398 (2019)","DOI":"10.46586\/tches.v2019.i3.340-398"},{"key":"3991_CR7","doi-asserted-by":"publisher","unstructured":"Kerry, C.F., Gallagher, P.D.: Security requirements for cryptographic modules. Technical Report Federal Information Processing Standards Publications (FIPS PUBS) 186-4, July 19, 2013. U.S. Department of Commerce, Washington, D.C. (2013). https:\/\/doi.org\/10.6028\/nist.fips.186-4","DOI":"10.6028\/nist.fips.186-4"},{"issue":"17","key":"3991_CR8","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)","journal-title":"Phys. Rev. Lett."},{"key":"3991_CR9","unstructured":"Developers, T.S.: SageMath, the Sage Mathematics Software System (Version 8.0) (2017). http:\/\/www.sagemath.org"},{"key":"3991_CR10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.8.041015","volume":"8","author":"R Babbush","year":"2018","unstructured":"Babbush, R., Gidney, C., Berry, D.W., Wiebe, N., McClean, J., Paler, A., Fowler, A., Neven, H.: Encoding electronic spectra in quantum circuits with linear t complexity. Phys. Rev. X 8, 041015 (2018). https:\/\/doi.org\/10.1103\/PhysRevX.8.041015","journal-title":"Phys. Rev. X"},{"key":"3991_CR11","unstructured":"Gidney, C.: Constructing Large Increment Gates. http:\/\/algassert.com\/circuits\/2015\/06\/12\/Constructing-Large-Increment-Gates.html. Last accessed 20 April 2022"},{"key":"3991_CR12","doi-asserted-by":"crossref","unstructured":"Van\u00a0Hoof, I.: Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count (2019). arXiv:1910.02849","DOI":"10.26421\/QIC20.9-10-1"},{"key":"3991_CR13","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7908587","author":"H Kim","year":"2023","unstructured":"Kim, H., Hong, S.: Space efficient quantum division algorithm in a binary field. Zenodo (2023). https:\/\/doi.org\/10.5281\/zenodo.7908587","journal-title":"Zenodo"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-03991-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-023-03991-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-03991-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T18:18:44Z","timestamp":1688667524000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-023-03991-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":13,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["3991"],"URL":"https:\/\/doi.org\/10.1007\/s11128-023-03991-6","relation":{},"ISSN":["1573-1332"],"issn-type":[{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"23 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"237"}}