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

Atighehchi, Kevin; Ballet, Stéphane; Bonnecaze, Alexis; Rolland, Robert

doi:10.1090/mcom/3230

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