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?)


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