Jean-Marc Couveignes
The algebraic complexity of multiplication in finite field extensions
Let K be a commutative field and let L/K be a finite extension of degree n.
The multiplication map × : L × L → L is K-bilinear and symmetric.
One way of evaluating the computational cost of multiplying two elements in L given by their coordinates in a given K-basis is to study the algebraic properties of the 3-tensor ×.
One defines the rank of a tensor to be the smallest integer r such that the tensor can be written as the sum of r pure tensors.
When K is a finite field with q elements, D.V. and G.V. Chudnovsky have shown how to bound from above the rank μq(n) of the multiplication tensor in L/K.
Their method relies on the existence of algebraic curves over K having many K-rational points (compared to their genus).
Tsfasman, Vladut, Shparlinski, Ballet, Rolland and others have obtained sharper and sharper estimates for μq(n) using families of curves with many points.
In this talk I will first recall these constructions. I will then introduce another invariant νq(n) called the equivariant complexity of multiplication in L/K.
This invariant controls the computational cost of multiplying two elements in L given by their coordinates in a normal basis over K.
I will present geometric constructions that provide upper bounds for this invariant. Joint work with Tony Ezome.