On the scalar complexity of Chudnovsky\(^2\) multiplication algorithm in finite fields (Q2175409)

The paper under review deals with the multiplicative complexity of multiplication in a finite field \(F_{q^n}\) which is the number of multiplications required to multiply in the \(F_q\)-vector space \(F_{q^n}\). The types of multiplications in \(F_q\) are the scalar multiplication and the bilinear one. The scalar multiplication is the multiplication by a constant in \(F_q\). The bilinear multiplication is a multiplication that depends on the elements of \(F_{q^n}\) that are multiplied. D. V. and G. V. Chudnovsky, generalizing interpolation algorithms on the projective line over \(F_q\) to algebraic curves of higher genus over \(F_q\), provided a method which enabled to prove the linearity of the bilinear complexity of multiplication in finite extensions of a finite field [\textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky}, J. Complexity 4, No. 4, 285--316 (1988; Zbl 0668.68040)]. This is the so-called Chudnovsky\(^2\) algorithm. In this paper, a new method of construction with an objective to reduce the scalar complexity of Chudnovsky\(^2\) multiplication algorithms is proposed. An optimized basis representation of the Riemann-Roch space \(L(2D)\) is sought in order to minimize the number of scalar multiplications in the algorithm. In particular, the Baum-Shokrollahi construction for multiplication in \(F_{256}/F_4\) based on the elliptic Fermat curve \(x^3 + y^3 = 1\) is improved. For the entire collection see [Zbl 1428.68013].