{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T12:10:32Z","timestamp":1780920632041,"version":"3.54.1"},"reference-count":41,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Complexity"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1016\/j.jco.2026.102046","type":"journal-article","created":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T16:23:04Z","timestamp":1774023784000},"page":"102046","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Elliptic butterflies"],"prefix":"10.1016","volume":"95","author":[{"given":"Jean-Marc","family":"Couveignes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reynald","family":"Lercier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.jco.2026.102046_br0010","series-title":"CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation","author":"Avanzi","year":"2024"},{"key":"10.1016\/j.jco.2026.102046_br0020","series-title":"CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation","author":"Bai","year":"2024"},{"issue":"1","key":"10.1016\/j.jco.2026.102046_br0030","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.jalgebra.2003.09.031","article-title":"Multiplication algorithm in a finite field and tensor rank of the multiplication","volume":"272","author":"Ballet","year":"2004","journal-title":"J. Algebra"},{"issue":"4","key":"10.1016\/j.jco.2026.102046_br0040","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1006\/ffta.1999.0255","article-title":"Curves with many points and multiplication complexity in any extension of Fq","volume":"5","author":"Ballet","year":"1999","journal-title":"Finite Fields Appl."},{"key":"10.1016\/j.jco.2026.102046_br0050","series-title":"Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"700","article-title":"Elliptic curve fast Fourier transform (ECFFT). I: low-degree extension in time O(nlog\u2061n) over all finite fields","author":"Ben-Sasson","year":"2023"},{"key":"10.1016\/j.jco.2026.102046_br0060","series-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security","first-page":"1006","article-title":"Frodo: take off the ring! Practical, quantum-secure key exchange from LWE","author":"Bos","year":"2016"},{"key":"10.1016\/j.jco.2026.102046_br0070","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Bosma","year":"1997","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jco.2026.102046_br0080","series-title":"Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation","first-page":"37","article-title":"Tellegen's principle into practice","author":"Bostan","year":"2003"},{"issue":"4","key":"10.1016\/j.jco.2026.102046_br0090","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.jco.2004.09.009","article-title":"Polynomial evaluation and interpolation on special sets of points","volume":"21","author":"Bostan","year":"2005","journal-title":"J. Complex."},{"key":"10.1016\/j.jco.2026.102046_br0100","series-title":"Algebraic Complexity Theory, vol. 315","author":"B\u00fcrgisser","year":"1997"},{"key":"10.1016\/j.jco.2026.102046_br0110","first-page":"343","article-title":"Multiplication in Small Finite Fields Using Elliptic Curves","volume":"vol. 5","author":"Chaumine","year":"2008"},{"issue":"4","key":"10.1016\/j.jco.2026.102046_br0120","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0885-064X(88)90012-X","article-title":"Algebraic complexities and algebraic curves over finite fields","volume":"4","author":"Chudnovsky","year":"1988","journal-title":"J. Complex."},{"key":"10.1016\/j.jco.2026.102046_br0130","series-title":"Number Theory","first-page":"12","article-title":"Computational problems in arithmetic of linear differential equations. Some Diophantine applications","volume":"vol. 1383","author":"Chudnovsky","year":"1989"},{"key":"10.1016\/j.jco.2026.102046_br0140","author":"Couveignes"},{"issue":"1","key":"10.1016\/j.jco.2026.102046_br0150","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ffa.2008.07.004","article-title":"Elliptic periods for finite fields","volume":"15","author":"Couveignes","year":"2009","journal-title":"Finite Fields Appl."},{"key":"10.1016\/j.jco.2026.102046_br0160","author":"Couveignes"},{"key":"10.1016\/j.jco.2026.102046_br0170","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF02940746","article-title":"Die Typen der Multiplikatorenringe elliptischer Funktionenk\u00f6rper","volume":"14","author":"Deuring","year":"1941","journal-title":"Abh. Math. Semin. Univ. Hans."},{"issue":"1","key":"10.1016\/j.jco.2026.102046_br0180","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF01884295","article-title":"A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound","volume":"121","author":"Garc\u00eda","year":"1995","journal-title":"Invent. Math."},{"key":"10.1016\/j.jco.2026.102046_br0190","series-title":"Modern Computer Algebra","author":"von zur Gathen","year":"2013"},{"issue":"6","key":"10.1016\/j.jco.2026.102046_br0200","first-page":"1289","article-title":"Codes on algebraic curves","volume":"259","author":"Goppa","year":"1981","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"4","key":"10.1016\/j.jco.2026.102046_br0210","first-page":"762","article-title":"Algebraic-geometric codes","volume":"46","author":"Goppa","year":"1982","journal-title":"Izv. Akad. Nauk SSSR, Ser. Mat."},{"key":"10.1016\/j.jco.2026.102046_br0220","series-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing","first-page":"212","article-title":"A fast quantum mechanical algorithm for database search","author":"Grover","year":"1996"},{"issue":"2","key":"10.1016\/j.jco.2026.102046_br0230","doi-asserted-by":"crossref","DOI":"10.1145\/3505584","article-title":"Polynomial multiplication over finite fields in time O(nlog\u2061n)","volume":"69","author":"Harvey","year":"2022","journal-title":"J. ACM"},{"key":"10.1016\/j.jco.2026.102046_br0240","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF00348431","article-title":"Gauss and the history of the fast Fourier transform","volume":"34","author":"Heideman","year":"1985","journal-title":"Arch. Hist. Exact Sci."},{"issue":"3","key":"10.1016\/j.jco.2026.102046_br0250","first-page":"721","article-title":"Some remarks on the number of rational points of algebraic curves over finite fields","volume":"28","author":"Ihara","year":"1981","journal-title":"J. Fac. Sci., Univ. Tokyo, Sect. 1A, Math."},{"issue":"3","key":"10.1016\/j.jco.2026.102046_br0260","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0196-6774(88)90026-0","article-title":"Addition requirements for matrix and transposed matrix products","volume":"9","author":"Kaminski","year":"1988","journal-title":"J. Algorithms"},{"issue":"6","key":"10.1016\/j.jco.2026.102046_br0270","doi-asserted-by":"crossref","DOI":"10.1145\/2535925","article-title":"On ideal lattices and learning with errors over rings","volume":"60","author":"Lyubashevsky","year":"2013","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.jco.2026.102046_br0280","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1561\/0400000074","article-title":"A decade of lattice cryptography","volume":"10","author":"Peikert","year":"2016","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"4","key":"10.1016\/j.jco.2026.102046_br0290","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/j.jco.2012.02.005","article-title":"Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method","volume":"28","author":"Randriambololona","year":"2012","journal-title":"J. Complex."},{"key":"10.1016\/j.jco.2026.102046_br0300","series-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing","first-page":"84","article-title":"On lattices, learning with errors, random linear codes, and cryptography","author":"Regev","year":"2005"},{"key":"10.1016\/j.jco.2026.102046_br0310","series-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC)","first-page":"84","article-title":"On lattices, learning with errors, random linear codes, and cryptography","author":"Regev","year":"2009"},{"issue":"6","key":"10.1016\/j.jco.2026.102046_br0320","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1137\/0221071","article-title":"Optimal algorithms for multiplication in certain finite fields using elliptic curves","volume":"21","author":"Shokrollahi","year":"1992","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10.1016\/j.jco.2026.102046_br0330","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"26","author":"Shor","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jco.2026.102046_br0340","series-title":"Coding Theory and Algebraic Geometry","first-page":"145","article-title":"Curves with many points and multiplication in finite fields","volume":"vol. 1518","author":"Shparlinski","year":"1992"},{"key":"10.1016\/j.jco.2026.102046_br0350","series-title":"7th IEEE Consumer Communications and Networking Conference","first-page":"1","article-title":"FNT-based Reed-Solomon erasure codes","author":"Soro","year":"2010"},{"issue":"1","key":"10.1016\/j.jco.2026.102046_br0360","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0019-9958(75)90090-X","article-title":"A method for solving key equation for decoding Goppa codes","volume":"27","author":"Sugiyama","year":"1975","journal-title":"Inf. Control"},{"key":"10.1016\/j.jco.2026.102046_br0370","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/mana.19821090103","article-title":"Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound","volume":"109","author":"Tsfasman","year":"1982","journal-title":"Math. Nachr."},{"key":"10.1016\/j.jco.2026.102046_br0380","first-page":"A238","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","author":"V\u00e9lu","year":"1971","journal-title":"C. R. Acad. Sci. Paris, Ser. A"},{"key":"10.1016\/j.jco.2026.102046_br0390","article-title":"Courbes elliptiques munies d'un sous-groupe Z\/nZ\u00d7\u03bcn","volume":"57","author":"V\u00e9lu","year":"1978","journal-title":"Bull. Soc. Math. Fr., Suppl. M\u00e9m."},{"key":"10.1016\/j.jco.2026.102046_br0400","doi-asserted-by":"crossref","first-page":"521","DOI":"10.24033\/asens.1183","article-title":"Abelian varieties over finite fields","volume":"2","author":"Waterhouse","year":"1969","journal-title":"Ann. Sci. \u00c9c. Norm. Sup\u00e9r. (4)"},{"key":"10.1016\/j.jco.2026.102046_br0410","author":"Wikipedia"}],"container-title":["Journal of Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X26000312?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X26000312?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T11:41:04Z","timestamp":1780918864000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0885064X26000312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":41,"alternative-id":["S0885064X26000312"],"URL":"https:\/\/doi.org\/10.1016\/j.jco.2026.102046","relation":{},"ISSN":["0885-064X"],"issn-type":[{"value":"0885-064X","type":"print"}],"subject":[],"published":{"date-parts":[[2026,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Elliptic butterflies","name":"articletitle","label":"Article Title"},{"value":"Journal of Complexity","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jco.2026.102046","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"102046"}}