New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields

Pieltant, Julia; Randriam, Hugues

doi:10.1090/S0025-5718-2015-02921-4

New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields
HTML articles powered by AMS MathViewer

by Julia Pieltant and Hugues Randriam PDF

Math. Comp. 84 (2015), 2023-2045 Request permission

Abstract:

We obtain new uniform upper bounds for the tensor rank of the multiplication in the extensions of the finite fields $\mathbb {F}_q$ for any prime power $q$; moreover, these uniform bounds lead to new asymptotic bounds as well. In addition, we also give purely asymptotic bounds which are substantially better by using a family of Shimura curves defined over $\mathbb {F}_q$, with an optimal ratio of $\mathbb {F}_{q^t}$-rational places to their genus, where $q^t$ is a square.

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, Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of ${\Bbb F}_q$, Finite Fields Appl. 9 (2003), no. 4, 472–478. MR 2007465, DOI 10.1016/S1071-5797(03)00026-1
Stéphane Ballet, On the tensor rank of the multiplication in the finite fields, J. Number Theory 128 (2008), no. 6, 1795–1806. MR 2419195, DOI 10.1016/j.jnt.2007.06.010
Stéphane Ballet and Jean Chaumine, On the bounds of the bilinear complexity of multiplication in some finite fields, Appl. Algebra Engrg. Comm. Comput. 15 (2004), no. 3-4, 205–211. MR 2104295, DOI 10.1007/s00200-004-0155-7
Stéphane Ballet, Jean Chaumine, and Julia Pieltant, Shimura modular curves and asymptotic symmetric tensor rank of multiplication in any finite field, In Traian Muntean, Dimitrios Poulakis, and Robert Rolland, editors, Algebraic Informatics – 5th International Conference, CAI 2013, Porquerolles, France, September 3-6, 2013, Proceedings, volume 8080 of Lecture Notes in Computer Science, pp. 160–172. Springer, 2013.
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 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
Stéphane Ballet and Robert Rolland, Families of curves over any finite field attaining the generalized Drinfeld-Vladut bound, Actes de la Conférence “Théorie des Nombres et Applications”, Publ. Math. Besançon Algèbre Théorie Nr., vol. 2011, Presses Univ. Franche-Comté, Besançon, 2011, pp. 5–18 (English, with English and French summaries). MR 2894265
Ulrich Baum and Mohammad Amin Shokrollahi, An optimal algorithm for multiplication in $\textbf {F}_{256}/\textbf {F}_4$, Appl. Algebra Engrg. Comm. Comput. 2 (1991), no. 1, 15–20. MR 1209240, DOI 10.1007/BF01810851
Ignacio Cascudo, Ronald Cramer, Chaoping Xing, and An Yang, Asymptotic bound for multiplication complexity in the extensions of small finite fields, IEEE Trans. Inform. Theory 58 (2012), no. 7, 4930–4935. MR 2949863, DOI 10.1109/TIT.2011.2180696
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
David Chudnovsky and Gregory Chudnovsky, Algebraic complexities and algebraic curves over finite fields, Journal of Complexity, 4:285–316, 1988.
Hans F. de Groote, Characterization of division algebras of minimal rank and the structure of their algorithm varieties, SIAM J. Comput. 12 (1983), no. 1, 101–117. MR 687805, DOI 10.1137/0212007
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
Arnaldo Garcia, Henning Stichtenoth, and Hans-Georg Rück, On tame towers over finite fields, J. Reine Angew. Math. 557 (2003), 53–80. MR 1978402, DOI 10.1515/crll.2003.034
Hugues Randriambololona, Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method, J. Complexity 28 (2012), no. 4, 489–517. MR 2925903, DOI 10.1016/j.jco.2012.02.005
Mohammad Amin Shokrollahi, Optimal algorithms for multiplication in certain finite fields using elliptic curves, SIAM J. Comput. 21 (1992), no. 6, 1193–1198. MR 1192302, DOI 10.1137/0221071
Igor E. Shparlinski, Michael A. Tsfasman, and Serge G. Vladut, Curves with many points and multiplication in finite fields, Coding theory and algebraic geometry (Luminy, 1991) Lecture Notes in Math., vol. 1518, Springer, Berlin, 1992, pp. 145–169. MR 1186422, DOI 10.1007/BFb0087999
S. Winograd, On multiplication in algebraic extension fields, Theoret. Comput. Sci. 8 (1979), no. 3, 359–377. MR 532476, DOI 10.1016/0304-3975(79)90017-3