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
Additional Information
- Julia Pieltant
- Affiliation: Inria Saclay, LIX, École Polytechnique, 91128 Palaiseau Cedex, France
- Email: pieltant@lix.polytechnique.fr
- Hugues Randriam
- Affiliation: ENST (“Telecom ParisTech”), 46 rue Barrault, F-75634 Paris Cedex 13, France
- MR Author ID: 684200
- Email: randriam@telecom-paristech.fr
- Received by editor(s): May 22, 2013
- Received by editor(s) in revised form: November 22, 2013
- Published electronically: January 16, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 2023-2045
- MSC (2010): Primary 14H05; Secondary 11Y16, 12E20
- DOI: https://doi.org/10.1090/S0025-5718-2015-02921-4
- MathSciNet review: 3335902