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

  • Robert Rolland | ERISC and Institut de Mathematiques

Let q=pr be a prime power and Fq be the finite field with q elements. We study the multiplication of two polynomials in Fq [X], with degree ≤ n-1, modulo an irreducible polynomial of degree n, namely the multiplication in the finite field Fqn.

We want to find a multiplication algorithm involving two variables in Fqn minimizing the number of bilinear multiplications (i.e. involving two variables) in Fq. We don’t take in account multiplications of a variable in Fq by a constant in Fq (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 Fq, a sharp estimate for this bilinear complexity.

Speaker Details

Robert Rolland was Professor at the Université de la Méditerranée (Marseille – France) and researcher in the laboratory Institut de Mathématiques de Luminy. He is now honorary member of the laboratories ERISC and Institut de Mathématiques de Luminy. Its research domain is algebraic geometry over finite fields and applications.

Watch Next