Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm
HTML articles powered by AMS MathViewer
- by Kevin Atighehchi, Stéphane Ballet, Alexis Bonnecaze and Robert Rolland PDF
- Math. Comp. 86 (2017), 2975-3000
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
- Stéphane Ballet, Curves with many points and multiplication complexity in any extension of $\textbf {F}_q$, Finite Fields Appl. 5 (1999), no. 4, 364–377. MR 1711833, DOI 10.1006/ffta.1999.0255
- Stéphane Ballet, Quasi-optimal algorithms for multiplication in the extensions of $\Bbb F_{16}$ of degree 13, 14 and 15, J. Pure Appl. Algebra 171 (2002), no. 2-3, 149–164. MR 1904474, DOI 10.1016/S0022-4049(01)00137-2
- 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, DOI 10.1142/S0219498816500055
- S. Ballet and D. Le Brigand, On the existence of non-special divisors of degree $g$ and $g-1$ in algebraic function fields over $\Bbb F_q$, J. Number Theory 116 (2006), no. 2, 293–310. MR 2195927, DOI 10.1016/j.jnt.2005.04.009
- 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 (English, with English and French summaries). MR 2856567
- Stéphane Ballet and Julia Pieltant, On the tensor rank of multiplication in any extension of $\Bbb F_2$, J. Complexity 27 (2011), no. 2, 230–245. MR 2776494, DOI 10.1016/j.jco.2011.01.008
- S. Ballet, C. Ritzenthaler, and R. Rolland, On the existence of dimension zero divisors in algebraic function fields defined over $\Bbb F_q$, Acta Arith. 143 (2010), no. 4, 377–392. MR 2652586, DOI 10.4064/aa143-4-4
- 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, DOI 10.1016/j.jalgebra.2003.09.031
- 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, DOI 10.1006/jsco.1996.0125
- Murat Cenk and Ferruh Özbudak, On multiplication in finite fields, J. Complexity 26 (2010), no. 2, 172–186. MR 2607731, DOI 10.1016/j.jco.2009.11.002
- 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, DOI 10.1016/0885-064X(88)90012-X
- 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.
- Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2
- Jean-Marc Couveignes and Reynald Lercier, Elliptic periods for finite fields, Finite Fields Appl. 15 (2009), no. 1, 1–22. MR 2468989, DOI 10.1016/j.ffa.2008.07.004
- Shuhong Gao, Normal bases over finite fields, ProQuest LLC, Ann Arbor, MI, 1993. Thesis (Ph.D.)–University of Waterloo (Canada). MR 2689945
- 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, DOI 10.1006/jsco.1999.0309
- Arnaldo García and Henning Stichtenoth, A tower of Artin-Schreier extensions of function fields attaining the Drinfel′d-Vlăduţ bound, Invent. Math. 121 (1995), no. 1, 211–222. MR 1345289, DOI 10.1007/BF01884295
- 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, DOI 10.1016/0020-0190(88)90164-0
- S. Lakshmivarahan and S. K. Dhall, Analysis and Design of Parallel Algorithms: Arithmetic and Matrix Problems. McGraw-Hill, Inc., New York, NY, USA, 1990.
- Mun-Kyu Lee, Yoonjeong Kim, Kunsoo Park, and Yookun Cho, Efficient parallel exponentiation in $\textrm {GF}(q^n)$ using normal basis representations, J. Algorithms 54 (2005), no. 2, 205–221. MR 2111908, DOI 10.1016/j.jalgor.2004.06.005
- 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
- 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, DOI 10.1007/3-540-48658-5_{1}1
- 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.
- Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
- Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633–672. MR 1127177
- 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.
- Joachim von zur Gathen, Efficient and optimal exponentiation in finite fields, Comput. Complexity 1 (1991), no. 4, 360–394. MR 1172675, DOI 10.1007/BF01212964
- Joachim von zur Gathen, Processor-efficient exponentiation in finite fields, Inform. Process. Lett. 41 (1992), no. 2, 81–86. MR 1156831, DOI 10.1016/0020-0190(92)90259-X
Additional Information
- Kevin Atighehchi
- Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, LIF, Marseille, France
- MR Author ID: 1147020
- Email: Kevin.Atighehchi@univ-amu.fr
- Stéphane Ballet
- Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
- MR Author ID: 654144
- Email: Stephane.Ballet@univ-amu.fr
- Alexis Bonnecaze
- Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
- MR Author ID: 352581
- Email: Alexis.Bonnecaze@univ-amu.fr
- Robert Rolland
- Affiliation: Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
- MR Author ID: 361503
- ORCID: 0000-0002-8028-3340
- Email: Robert.Rolland@univ-amu.fr
- Received by editor(s): October 7, 2015
- Received by editor(s) in revised form: June 13, 2016
- Published electronically: March 29, 2017
- © Copyright 2017 by the authors
- Journal: Math. Comp. 86 (2017), 2975-3000
- MSC (2010): Primary 12Y05, 14Q05, 14Q20
- DOI: https://doi.org/10.1090/mcom/3230
- MathSciNet review: 3667034