Bilinear Complexity of the Multiplication in a Finite Extention of a Finite Field

Опубликовано 6 сентября 2016, 17:50

Let $q=p^r$ be a prime power and $\F_q$ be the finite field with $q$ elements. We study the multiplication of two polynomials in $\F_q [X]$, with degree $\leq n-1$, modulo an irreducible polynomial of degree $n$, namely the multiplication in the finite field $\F_{q^n}$. We want to find a multiplication algorithm involving two variables in $\F_{q^n}$ minimizing the number of bilinear multiplications (i.e. involving two variables) in $\F_q$. We don't take in account multiplications of a variable in $\F_q$ by a constant in $\F_q$ (However these linear operations have a cost). It turns out that the number of bilinear operations is related to a tensor expression of the multiplication and that the problem is to find the rank of this tensor. We will give, using interpolation on algebraic curves over the finite field $\F_q$, a sharp estimate for this bilinear complexity.