Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


Authors: Julia Pieltant and Hugues Randriam
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
Published electronically: January 16, 2015
MathSciNet review: 3335902
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Stéphane Ballet, Curves with many points and multiplication complexity in any extension of $ {\bf F}_q$, Finite Fields Appl. 5 (1999), no. 4, 364-377. MR 1711833 (2001d:11065), https://doi.org/10.1006/ffta.1999.0255
  • [2] Stéphane Ballet, Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of $ {\mathbb{F}}_q$, Finite Fields Appl. 9 (2003), no. 4, 472-478. MR 2007465 (2004m:11191), https://doi.org/10.1016/S1071-5797(03)00026-1
  • [3] 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 (2009b:11103), https://doi.org/10.1016/j.jnt.2007.06.010
  • [4] 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 (2005g:11253), https://doi.org/10.1007/s00200-004-0155-7
  • [5] 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.
  • [6] Stéphane Ballet and Dominique Le Brigand, On the existence of non-special divisors of degree $ g$ and $ g-1$ in algebraic function fields over $ \mathbb{F}_q$, J. Number Theory 116 (2006), no. 2, 293-310. MR 2195927 (2006i:11136), https://doi.org/10.1016/j.jnt.2005.04.009
  • [7] 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 (2012j:11220)
  • [8] Stéphane Ballet and Julia Pieltant, On the tensor rank of multiplication in any extension of $ \mathbb{F}_2$, J. Complexity 27 (2011), no. 2, 230-245. MR 2776494 (2012c:11266), https://doi.org/10.1016/j.jco.2011.01.008
  • [9] Stéphane Ballet and Robert Rolland, Multiplication algorithm in a finite field and tensor rank of the multiplication, J. Algebra 272 (2004), no. 1, 173-185. MR 2029030 (2004i:11148), https://doi.org/10.1016/j.jalgebra.2003.09.031
  • [10] 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., Presses Univ. Franche-Comté, Besançon, 2011, pp. 5-18 (English, with English and French summaries). MR 2894265
  • [11] Ulrich Baum and Mohammad Amin Shokrollahi, An optimal algorithm for multiplication in $ {\bf F}_{256}/{\bf F}_4$, Appl. Algebra Engrg. Comm. Comput. 2 (1991), no. 1, 15-20. MR 1209240 (94a:11191), https://doi.org/10.1007/BF01810851
  • [12] 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, https://doi.org/10.1109/TIT.2011.2180696
  • [13] Murat Cenk and Ferruh Özbudak, On multiplication in finite fields, J. Complexity 26 (2010), no. 2, 172-186. MR 2607731 (2011b:68079), https://doi.org/10.1016/j.jco.2009.11.002
  • [14] David Chudnovsky and Gregory Chudnovsky, Algebraic complexities and algebraic curves over finite fields, Journal of Complexity, 4:285-316, 1988.
  • [15] 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 (84e:68036), https://doi.org/10.1137/0212007
  • [16] Arnaldo García and Henning Stichtenoth, A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vlăduţ bound, Invent. Math. 121 (1995), no. 1, 211-222. MR 1345289 (96d:11074), https://doi.org/10.1007/BF01884295
  • [17] 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 (2004e:11133), https://doi.org/10.1515/crll.2003.034
  • [18] Hugues Randriambololona, Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method, J. Complexity 28 (2012), no. 4, 489-517. MR 2925903, https://doi.org/10.1016/j.jco.2012.02.005
  • [19] 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 (93m:11138), https://doi.org/10.1137/0221071
  • [20] 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 (93h:11063), https://doi.org/10.1007/BFb0087999
  • [21] S. Winograd, On multiplication in algebraic extension fields, Theoret. Comput. Sci. 8 (1979), no. 3, 359-377. MR 532476 (80e:68081), https://doi.org/10.1016/0304-3975(79)90017-3

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14H05, 11Y16, 12E20

Retrieve articles in all journals with MSC (2010): 14H05, 11Y16, 12E20


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
Email: randriam@telecom-paristech.fr

DOI: https://doi.org/10.1090/S0025-5718-2015-02921-4
Keywords: Algebraic function field, tower of function fields, tensor rank, algorithm, finite field
Received by editor(s): May 22, 2013
Received by editor(s) in revised form: November 22, 2013
Published electronically: January 16, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society