main-content

20-01-2022

# Construction of asymmetric Chudnovsky-type algorithms for multiplication in finite fields

Authors: Stéphane Ballet, Nicolas Baudru, Alexis Bonnecaze, Mila Tukumuli

Published in: Designs, Codes and Cryptography

## Abstract

The original algorithm of D.V. Chudnovsky and G.V. Chudnovsky for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear with respect to the degree of the extension. Recently, Randriambololona generalized the method, allowing asymmetry in the interpolation procedure. The aim of this article is to make effective this method. We first make explicit this generalization in order to construct the underlying asymmetric algorithms. Then, we propose a generic strategy to construct these algorithms using places of higher degrees and without derivated evaluation. Finally, we provide examples of three multiplication algorithms along with their Magma implementation: in $$\mathbb {F}_{16^{13}}$$ using only rational places, in $$\mathbb {F}_{4^{5}}$$ using also places of degree two, and in $$\mathbb {F}_{2^{5}}$$ using also places of degree four.
Appendix
Available only for authorised users
Literature
1.
Atighehchi K., Ballet S., Bonnecaze A., Rolland R.: On Chudnovsky-based arithmetic algorithms in finite fields. Math. Comput. 86(308), 2975–3000 (2017). CrossRef
2.
Ballet S., Chaumine J., Pieltant J., Rambaud M., Randriambololona H., Rolland R.: On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry, Uspekhi Mathematichskikh Nauk (Russian Math. Surveys), 76:1, 31–94 (29–89) (2021)
3.
Ballet S., Chaumine J., Pieltant J.: Shimura modular curves and asymptotic symmetric tensor rank of multiplication in any finite field. In: Proceedings of the conference algebraic informatics, Lecture Notes in Computer Science, 8080, Springer, Heidelberg, 160–172 (2013)
4.
Ballet S., Le Brigand D., Rolland R.: On an application of the definition field descent of a tower of function fields. Arithmetics, geometry, and coding theory (AGCT 2005), 187-203, Sémin. Congr., 21, Soc. Math. France, Paris (2010)
5.
Ballet S., Rolland R.: Families of curves over any finite field attaining the generalized Drinfeld-Vladut bound. In: Actes de la Conférence “Théorie des Nombres et Applications”, 5-18, Publ. Math. Besançon Algèbre Théorie Nr., Presses Univ. Franche-Comté, Besançon (2011).
6.
Ballet S.: Curves with many points and multiplication complexity in any extension of $$_{q}$$. Finite Fields Their Appl. 5(4), 364–377 (1999).
7.
Ballet S.: Quasi-optimal algorithms for multiplication in the extensions of $$_{16}$$ of degree $$13, 14 \text{ and } 15$$. J. Pure Appl. Algebra 171(2–3), 149–164 (2002).
8.
Ballet S., Le Brigand D.: On the existence of non special divisor of degree $$g$$ and $$g-1$$ in algebraic function fields over $$_{q}$$. J. Number Theory 116, 293–310 (2006).
9.
Ballet S., Pieltant J.: On the tensor rank of multiplication in any extension of $$_{2}$$. J. Complex. 27, 230–245 (2011).
10.
Ballet S., Rolland R.: Multiplication algorithm in a finite field and tensor rank of the multiplication. J. Algebra 272(1), 173–185 (2004).
11.
Ballet S., Ritzenthaler C., Rolland R.: On the existence of dimension zero divisors in algebraic function fields defined over $$_q$$. Acta Arithmetica 143(4), 377–392 (2010).
12.
Ballet S., Bonnecaze A., Tukumuli M.: On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields. J. Algebra Its Appl. 15(1), 1650005 (2016).
13.
Baum U., Shokrollahi M.A.: An optimal algorithm for multiplication in $$_{256}/ _{4}$$. Appl. Algebra Eng. Commun. Comput. 2, 15–20 (1991). CrossRef
14.
Bosma W., Cannon J., Playoust C.: The Magma Algebra System I. The user language. Journal of Symbolic Computation 24 3–4, 235–265 (1997).
15.
Bshouty N.H.: Multilinear complexity is equivalent to optimal tester size. Electronic Colloquium on Computational Complexity, Report No11 (2013)
16.
Cenk M., Özbudak F.: On multiplication in finite fields. J. Complex. 26, 172–186 (2010).
17.
Chudnovsky D.V., Chudnovsky G.V.: Algebraic complexities and algebraic curves over finite fields. J. Complex. 4, 285–316 (1988).
18.
Ihara Y.: Some remarks on the number of rational points of algebraic curves over finite fields. J. Fac. Sci. Univ. Tokyo Sect. IA Math. 28, 721–724 (1982).
19.
Julia P.: Tours de corps de fonctions algébriques et rang de tenseur de la multiplication dans les corps finis. PhD of Université d’Aix-Marseille, Institut de Mathématiques de Luminy (2012).
20.
Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and Its Applications, p. 20. Cambridge University Press, Cambridge (2000).
21.
Pieltant J., Randriambololona H.: New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields. Math. Comput. 84, 2023–2045 (2015).
22.
Randriambololona H.: Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method. J. Complex. 28, 489–517 (2012).
23.
Serre J.-P.: Sur le nombre de points rationnels d’une courbe algébrique sur un corps fini. C. R. Acad. Sci. Paris, Sér. I Math 296.6, 397–402 (1983). MATH
24.
Shabat G. V.: Curves with many points. PhD Thesis, Amsterdam (2001)
25.
Shparlinski I., Tsfasman M., Vladut S.: Curves with many points and multiplication in finite fields. In: H. Stichtenoth, M.A. Tsfasman (eds) Coding Theory and Algebraic Geometry, number 1518 in Lectures Notes in Mathematics, pages 145–169, Berlin, 1992. Springer. Proceedings of AGCT-3 conference (1991) Luminy.
26.
Stichtenoth H.: Algebraic Function Fields and Codes. Springer, Berlin (1993). MATH
Title
Construction of asymmetric Chudnovsky-type algorithms for multiplication in finite fields
Authors
Stéphane Ballet
Nicolas Baudru
Alexis Bonnecaze
Mila Tukumuli
Publication date
20-01-2022
Publisher
Springer US
Published in
Designs, Codes and Cryptography
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00986-1