{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:15:49Z","timestamp":1776802549184,"version":"3.51.2"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"308","license":[{"start":{"date-parts":[[2018,3,29]],"date-time":"2018-03-29T00:00:00Z","timestamp":1522281600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Thanks to a new construction of the so-called Chudnovsky- Chudnovsky multiplication algorithm, we design efficient algorithms for both the exponentiation and the multiplication in finite fields. They are tailored to hardware implementation and they allow computations to be parallelized while maintaining a low number of bilinear multiplications. We give an example with the finite field\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper F Subscript 16 Sub Superscript 13\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:msup>\n                                <mml:mn>16<\/mml:mn>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mn>13<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_{16^{13}}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    .\n                  <\/p>","DOI":"10.1090\/mcom\/3230","type":"journal-article","created":{"date-parts":[[2017,3,29]],"date-time":"2017-03-29T10:06:44Z","timestamp":1490782004000},"page":"2975-3000","source":"Crossref","is-referenced-by-count":6,"title":["Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm"],"prefix":"10.1090","volume":"86","author":[{"given":"Kevin","family":"Atighehchi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Ballet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexis","family":"Bonnecaze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Rolland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2017,3,29]]},"reference":[{"issue":"4","key":"1","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1006\/ffta.1999.0255","article-title":"Curves with many points and multiplication complexity in any extension of \ud835\udc39_{\ud835\udc5e}","volume":"5","author":"Ballet, St\u00e9phane","year":"1999","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"issue":"2-3","key":"2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-4049(01)00137-2","article-title":"Quasi-optimal algorithms for multiplication in the extensions of \ud835\udd3d\u2081\u2086 of degree 13, 14 and 15","volume":"171","author":"Ballet, St\u00e9phane","year":"2002","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"1650005","DOI":"10.1142\/S0219498816500055","article-title":"On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields","volume":"15","author":"Ballet, St\u00e9phane","year":"2016","journal-title":"J. Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0219-4988","issn-type":"print"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.jnt.2005.04.009","article-title":"On the existence of non-special divisors of degree \ud835\udc54 and \ud835\udc54-1 in algebraic function fields over \ud835\udd3d_{\ud835\udd62}","volume":"116","author":"Ballet, S.","year":"2006","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"5","isbn-type":"print","first-page":"187","article-title":"On an application of the definition field descent of a tower of function fields","author":"Ballet, St\u00e9phane","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9782856292792"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/j.jco.2011.01.008","article-title":"On the tensor rank of multiplication in any extension of \ud835\udd3d\u2082","volume":"27","author":"Ballet, St\u00e9phane","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"377","DOI":"10.4064\/aa143-4-4","article-title":"On the existence of dimension zero divisors in algebraic function fields defined over \ud835\udd3d_{\ud835\udd62}","volume":"143","author":"Ballet, S.","year":"2010","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"1","key":"8","doi-asserted-by":"publisher","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, S.","year":"2004","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"issue":"3-4","key":"9","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Bosma, Wieb","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"2","key":"10","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.jco.2009.11.002","article-title":"On multiplication in finite fields","volume":"26","author":"Cenk, Murat","year":"2010","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"4","key":"11","doi-asserted-by":"publisher","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, D. V.","year":"1988","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"12","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC \u201987, pages 1\u20136, New York, NY, USA, 1987. ACM.","DOI":"10.1145\/28395.28396"},{"issue":"3","key":"13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith, Don","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ffa.2008.07.004","article-title":"Elliptic periods for finite fields","volume":"15","author":"Couveignes, Jean-Marc","year":"2009","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"key":"15","isbn-type":"print","volume-title":"Normal bases over finite fields","author":"Gao, Shuhong","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/9780315810778"},{"issue":"6","key":"16","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1006\/jsco.1999.0309","article-title":"Algorithms for exponentiation in finite fields","volume":"29","author":"Gao, Shuhong","year":"2000","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"1","key":"17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01884295","article-title":"A tower of Artin-Schreier extensions of function fields attaining the Drinfel\u2032d-Vl\u0103du\u0163 bound","volume":"121","author":"Garc\u00eda, Arnaldo","year":"1995","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(88)90164-0","article-title":"An improved parallel algorithm that computes the BFS numbering of a directed graph","volume":"28","author":"Gazit, Hillel","year":"1988","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"},{"key":"19","unstructured":"S. Lakshmivarahan and S. K. Dhall, Analysis and Design of Parallel Algorithms: Arithmetic and Matrix Problems. McGraw-Hill, Inc., New York, NY, USA, 1990."},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/j.jalgor.2004.06.005","article-title":"Efficient parallel exponentiation in \ud835\udc3a\ud835\udc39(\ud835\udc5e\u207f) using normal basis representations","volume":"54","author":"Lee, Mun-Kyu","year":"2005","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"21","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"Finite fields","volume":"20","author":"Lidl, Rudolf","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0201135191"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/3-540-48658-5_11","article-title":"More flexible exponentiation with precomputation","author":"Lim, Chae Hoon","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540583335"},{"key":"23","unstructured":"J. Pieltant, Tours de corps de fonctions alg\u00e9briques et rang de tenseur de la multiplication dans les corps finis, PhD thesis, Universit\u00e9 d\u2019Aix-Marseille, Institut de Math\u00e9matiques de Luminy, 2012."},{"key":"24","series-title":"Universitext","isbn-type":"print","volume-title":"Algebraic function fields and codes","author":"Stichtenoth, Henning","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540564896"},{"key":"25","isbn-type":"print","first-page":"633","article-title":"Algebraic complexity theory","author":"Strassen, Volker","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0444880712"},{"key":"26","unstructured":"M. Tukumuli, \u00c9tude de la construction effective des algorithmes de type Chudnovsky pour la multiplication dans les corps finis. PhD thesis, Universit\u00e9 d\u2019Aix-Marseille, Institut de Math\u00e9matiques de Luminy, 2013."},{"issue":"4","key":"27","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/BF01212964","article-title":"Efficient and optimal exponentiation in finite fields","volume":"1","author":"von zur Gathen, Joachim","year":"1991","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(92)90259-X","article-title":"Processor-efficient exponentiation in finite fields","volume":"41","author":"von zur Gathen, Joachim","year":"1992","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2017-86-308\/S0025-5718-2017-03230-0\/S0025-5718-2017-03230-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-308\/S0025-5718-2017-03230-0\/S0025-5718-2017-03230-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:22:42Z","timestamp":1776799362000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-308\/S0025-5718-2017-03230-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,29]]},"references-count":28,"journal-issue":{"issue":"308","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["S0025-5718-2017-03230-0"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3230","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2017,3,29]]}}}