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

Julia Pieltant (1, 2) , Hugues Randriambololona (3, 4)

1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 LTCI - Laboratoire Traitement et Communication de l'Information
4 Télécom ParisTech

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.

Keywords: tower of function fields; algebraic function field; tensor rank; algorithm; finite field

Domains: Algebraic Geometry [math.AG]; Number Theory [math.NT]; Computational Complexity [cs.CC]

Julia Pieltant, Hugues Randriambololona. New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields. Mathematics of Computation, 2015, 84 (294), pp.2023-2045. ⟨10.1090/S0025-5718-2015-02921-4⟩. ⟨hal-00828153⟩