Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm


Authors: Kevin Atighehchi, Stéphane Ballet, Alexis Bonnecaze and Robert Rolland
Journal: Math. Comp. 86 (2017), 2975-3000
MSC (2010): Primary 12Y05, 14Q05, 14Q20
DOI: https://doi.org/10.1090/mcom/3230
Published electronically: March 29, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \mathbb{F}_{16^{13}}$.


References [Enhancements On Off] (What's this?)

  • [1] Stéphane Ballet, Curves with many points and multiplication complexity in any extension of $ {\bf F}_q$, Finite Fields Appl. 5 (1999), no. 4, 364-377. MR 1711833, https://doi.org/10.1006/ffta.1999.0255
  • [2] Stéphane Ballet, Quasi-optimal algorithms for multiplication in the extensions of $ \mathbb{F}_{16}$ of degree 13, 14 and 15, J. Pure Appl. Algebra 171 (2002), no. 2-3, 149-164. MR 1904474, https://doi.org/10.1016/S0022-4049(01)00137-2
  • [3] Stéphane Ballet, Alexis Bonnecaze, and Mila Tukumuli, On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields, J. Algebra Appl. 15 (2016), no. 1, 1650005, 26. MR 3393934, https://doi.org/10.1142/S0219498816500055
  • [4] S. Ballet and D. Le Brigand, On the existence of non-special divisors of degree $ g$ and $ g-1$ in algebraic function fields over $ \mathbb{F}_q$, J. Number Theory 116 (2006), no. 2, 293-310. MR 2195927, https://doi.org/10.1016/j.jnt.2005.04.009
  • [5] Stéphane Ballet, Dominique Le Brigand, and Robert Rolland, On an application of the definition field descent of a tower of function fields, Arithmetics, geometry, and coding theory (AGCT 2005), Sémin. Congr., vol. 21, Soc. Math. France, Paris, 2010, pp. 187-203. MR 2856567
  • [6] Stéphane Ballet and Julia Pieltant, On the tensor rank of multiplication in any extension of $ \mathbb{F}_2$, J. Complexity 27 (2011), no. 2, 230-245. MR 2776494, https://doi.org/10.1016/j.jco.2011.01.008
  • [7] S. Ballet, C. Ritzenthaler, and R. Rolland, On the existence of dimension zero divisors in algebraic function fields defined over $ \mathbb{F}_q$, Acta Arith. 143 (2010), no. 4, 377-392. MR 2652586, https://doi.org/10.4064/aa143-4-4
  • [8] S. Ballet and R. Rolland, Multiplication algorithm in a finite field and tensor rank of the multiplication, J. Algebra 272 (2004), no. 1, 173-185. MR 2029030, https://doi.org/10.1016/j.jalgebra.2003.09.031
  • [9] Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235-265. Computational algebra and number theory (London, 1993). MR 1484478, https://doi.org/10.1006/jsco.1996.0125
  • [10] Murat Cenk and Ferruh Özbudak, On multiplication in finite fields, J. Complexity 26 (2010), no. 2, 172-186. MR 2607731, https://doi.org/10.1016/j.jco.2009.11.002
  • [11] D. V. Chudnovsky and G. V. Chudnovsky, Algebraic complexities and algebraic curves over finite fields, J. Complexity 4 (1988), no. 4, 285-316. MR 974928, https://doi.org/10.1016/0885-064X(88)90012-X
  • [12] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 1-6, New York, NY, USA, 1987. ACM.
  • [13] Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251-280. MR 1056627, https://doi.org/10.1016/S0747-7171(08)80013-2
  • [14] Jean-Marc Couveignes and Reynald Lercier, Elliptic periods for finite fields, Finite Fields Appl. 15 (2009), no. 1, 1-22. MR 2468989, https://doi.org/10.1016/j.ffa.2008.07.004
  • [15] Shuhong Gao, Normal bases over finite fields, ProQuest LLC, Ann Arbor, MI, 1993. Thesis (Ph.D.)-University of Waterloo (Canada). MR 2689945
  • [16] Shuhong Gao, Joachim Von Zur Gathen, Daniel Panario, and Victor Shoup, Algorithms for exponentiation in finite fields, J. Symbolic Comput. 29 (2000), no. 6, 879-889. MR 1765928, https://doi.org/10.1006/jsco.1999.0309
  • [17] Arnaldo García and Henning Stichtenoth, A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vlăduţ bound, Invent. Math. 121 (1995), no. 1, 211-222. MR 1345289, https://doi.org/10.1007/BF01884295
  • [18] Hillel Gazit and Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Inform. Process. Lett. 28 (1988), no. 2, 61-65. MR 948859, https://doi.org/10.1016/0020-0190(88)90164-0
  • [19] S. Lakshmivarahan and S. K. Dhall,
    Analysis and Design of Parallel Algorithms: Arithmetic and Matrix Problems.
    McGraw-Hill, Inc., New York, NY, USA, 1990.
  • [20] Mun-Kyu Lee, Yoonjeong Kim, Kunsoo Park, and Yookun Cho, Efficient parallel exponentiation in $ {\rm GF}(q^n)$ using normal basis representations, J. Algorithms 54 (2005), no. 2, 205-221. MR 2111908, https://doi.org/10.1016/j.jalgor.2004.06.005
  • [21] Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
  • [22] Chae Hoon Lim and Pil Joong Lee, More flexible exponentiation with precomputation, Advances in cryptology--CRYPTO '94 (Santa Barbara, CA, 1994) Lecture Notes in Comput. Sci., vol. 839, Springer, Berlin, 1994, pp. 95-107. MR 1316405, https://doi.org/10.1007/3-540-48658-5_11
  • [23] J. Pieltant,
    Tours de corps de fonctions algébriques et rang de tenseur de la multiplication dans les corps finis,
    PhD thesis, Université d'Aix-Marseille, Institut de Mathématiques de Luminy, 2012.
  • [24] Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
  • [25] Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633-672. MR 1127177
  • [26] M. Tukumuli,
    Étude de la construction effective des algorithmes de type Chudnovsky pour la multiplication dans les corps finis.
    PhD thesis, Université d'Aix-Marseille, Institut de Mathématiques de Luminy, 2013.
  • [27] Joachim von zur Gathen, Efficient and optimal exponentiation in finite fields, Comput. Complexity 1 (1991), no. 4, 360-394. MR 1172675, https://doi.org/10.1007/BF01212964
  • [28] Joachim von zur Gathen, Processor-efficient exponentiation in finite fields, Inform. Process. Lett. 41 (1992), no. 2, 81-86. MR 1156831, https://doi.org/10.1016/0020-0190(92)90259-X

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 14Q05, 14Q20

Retrieve articles in all journals with MSC (2010): 12Y05, 14Q05, 14Q20


Additional Information

Kevin Atighehchi
Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, LIF, Marseille, France
Email: Kevin.Atighehchi@univ-amu.fr

Stéphane Ballet
Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
Email: Stephane.Ballet@univ-amu.fr

Alexis Bonnecaze
Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
Email: Alexis.Bonnecaze@univ-amu.fr

Robert Rolland
Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
Email: Robert.Rolland@univ-amu.fr

DOI: https://doi.org/10.1090/mcom/3230
Received by editor(s): October 7, 2015
Received by editor(s) in revised form: June 13, 2016
Published electronically: March 29, 2017
Article copyright: © Copyright 2017 by the authors

American Mathematical Society