Finite fields have a central role in cryptography, since many protocols use them
as their foundation. Therefore, it is crucial to have efficient arithmetic
operations, e.g. multiplication and addition, over finite fields. Multiplication is usually quite
expensive, hence there has been extensive research to find Karatsuba-like
formulas reducing the number of multiplications involved when computing a bilinear
map over a finite field. The minimal number of multiplications in such formulas is
called the bilinear complexity, and it is also of theoretical interest to
asymptotically understand it. Moreover, when the bilinear maps admit some kind of
invariance, it is also desirable to find formulas keeping the same invariance. In this talk, we study
trisymmetric, hypersymmetric, and Galois invariant multiplication formulas
over finite fields, and we give an algorithm to find such formulas.
We also generalize the result that the bilinear complexity and symmetric
bilinear complexity of the two-variable multiplication in an extension field
are linear in the degree of the extension, to trisymmetric bilinear
complexity, and to the complexity of t-variable multiplication for any t ≥ 3.