On multiplication in finite fields

AbstractWe present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion M̂q(ℓ), which denotes the minimum number of multiplications needed in Fq in order to obtain the coefficients of the product of two arbitrary ℓ-term polynomials modulo xℓ in Fq[x]. We study our method for the finite fields Fqn, where 2≤n≤18 and q=2,3,4 and we improve or reach the currently best known bilinear complexities. We also give some applications in cryptography