Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

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

Login to get access
share
SHARE

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.
go back to reference Atighehchi K., Ballet S., Bonnecaze A., Rolland R.: On Chudnovsky-based arithmetic algorithms in finite fields. Math. Comput. 86(308), 2975–3000 (2017). CrossRef 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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). 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.
go back to reference Ballet S.: Curves with many points and multiplication complexity in any extension of \(_{q}\). Finite Fields Their Appl. 5(4), 364–377 (1999). MathSciNetCrossRef Ballet S.: Curves with many points and multiplication complexity in any extension of \(_{q}\). Finite Fields Their Appl. 5(4), 364–377 (1999). MathSciNetCrossRef
7.
go back to reference 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). MathSciNetCrossRef 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). MathSciNetCrossRef
8.
go back to reference 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). MathSciNetCrossRef 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). MathSciNetCrossRef
9.
go back to reference Ballet S., Pieltant J.: On the tensor rank of multiplication in any extension of \( _{2} \). J. Complex. 27, 230–245 (2011). MathSciNetCrossRef Ballet S., Pieltant J.: On the tensor rank of multiplication in any extension of \( _{2} \). J. Complex. 27, 230–245 (2011). MathSciNetCrossRef
10.
go back to reference Ballet S., Rolland R.: Multiplication algorithm in a finite field and tensor rank of the multiplication. J. Algebra 272(1), 173–185 (2004). MathSciNetCrossRef Ballet S., Rolland R.: Multiplication algorithm in a finite field and tensor rank of the multiplication. J. Algebra 272(1), 173–185 (2004). MathSciNetCrossRef
11.
go back to reference 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). MathSciNetCrossRef 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). MathSciNetCrossRef
12.
go back to reference 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). MathSciNetCrossRef 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). MathSciNetCrossRef
13.
go back to reference Baum U., Shokrollahi M.A.: An optimal algorithm for multiplication in \(_{256}/ _{4} \). Appl. Algebra Eng. Commun. Comput. 2, 15–20 (1991). CrossRef Baum U., Shokrollahi M.A.: An optimal algorithm for multiplication in \(_{256}/ _{4} \). Appl. Algebra Eng. Commun. Comput. 2, 15–20 (1991). CrossRef
14.
go back to reference Bosma W., Cannon J., Playoust C.: The Magma Algebra System I. The user language. Journal of Symbolic Computation 24 3–4, 235–265 (1997). MathSciNetCrossRef Bosma W., Cannon J., Playoust C.: The Magma Algebra System I. The user language. Journal of Symbolic Computation 24 3–4, 235–265 (1997). MathSciNetCrossRef
15.
go back to reference Bshouty N.H.: Multilinear complexity is equivalent to optimal tester size. Electronic Colloquium on Computational Complexity, Report No11 (2013) Bshouty N.H.: Multilinear complexity is equivalent to optimal tester size. Electronic Colloquium on Computational Complexity, Report No11 (2013)
17.
go back to reference Chudnovsky D.V., Chudnovsky G.V.: Algebraic complexities and algebraic curves over finite fields. J. Complex. 4, 285–316 (1988). MathSciNetCrossRef Chudnovsky D.V., Chudnovsky G.V.: Algebraic complexities and algebraic curves over finite fields. J. Complex. 4, 285–316 (1988). MathSciNetCrossRef
18.
go back to reference 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). MathSciNetMATH 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). MathSciNetMATH
19.
go back to reference 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). 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.
go back to reference Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and Its Applications, p. 20. Cambridge University Press, Cambridge (2000). Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and Its Applications, p. 20. Cambridge University Press, Cambridge (2000).
21.
go back to reference 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). MathSciNetCrossRef 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). MathSciNetCrossRef
22.
go back to reference Randriambololona H.: Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method. J. Complex. 28, 489–517 (2012). MathSciNetCrossRef Randriambololona H.: Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method. J. Complex. 28, 489–517 (2012). MathSciNetCrossRef
23.
go back to reference 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 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.
go back to reference Shabat G. V.: Curves with many points. PhD Thesis, Amsterdam (2001) Shabat G. V.: Curves with many points. PhD Thesis, Amsterdam (2001)
25.
go back to reference 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. 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.
go back to reference Stichtenoth H.: Algebraic Function Fields and Codes. Springer, Berlin (1993). MATH Stichtenoth H.: Algebraic Function Fields and Codes. Springer, Berlin (1993). MATH
Metadata
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

Premium Partner