Optimization of the scalar complexity of Chudnovsky\(^2\) multiplication algorithms in finite fields (Q2120984): Difference between revisions

\textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky} introduced multiplication algorithms for any extension of finite field based upon interpolation on some algebraic curves defined over finite fields [J. Complexity 4, No. 4, 285--316 (1988; Zbl 0668.68040)]. In this paper, the authors continue their study on these algorithms first initiated in [CAI 2019, Lect. Notes Comput. Sci. 11545, 64--75 (2019; Zbl 1456.11235)] and propose several constructions for the original multiplication algorithm of D. V. and G. V. Chudnovsky in order to improve its scalar complexity. For this purpose, they identify the set of fundamental generic strategies underlying the scalar complexity optimization and the relevant quantities related to it. Moreover, they significantly reduce the complexity of the complete optimization process. This analysis is applied to the construction of type elliptic Chudnovsky\(^2\) multiplication algorithms for small extensions. Furthermore, the Baum-Shokrollahi construction for multiplication in \(\mathbb{F}_{256}/\mathbb{F}_4\) is significantly improved.