Dense families of modular curves, prime numbers and uniform symmetric tensor rank of multiplication in certain finite fields

Designs, Codes and Cryptography. 2019. Vol. 87. P. 517–525.

Zykin A. I., Ballet S.

We obtain new uniform bounds for the symmetric tensor rank of multiplication in finite extensions of any finite field F_p or F_{p^2} where p denotes a prime number ≥5. In this aim, we use the symmetric Chudnovsky-type generalized algorithm applied on sufficiently dense families of modular curves defined over F_{p_2} attaining the Drinfeld–Vladuts bound and on the descent of these families to the definition field F_p. These families are obtained thanks to prime number density theorems of type Hoheisel, in particular a result due to Dudek (Funct Approx Commmentarii Math, 55(2):177–197, 2016).

Keywords: algorithm, finite field, modular curves, tensor rank, Algebraic function field, Tower of function fields, Shimura curve