An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields (Q818142): Difference between revisions

The paper presents some new results about the bilinear complexity of the multiplication in a finite field \(\mathbb{F}_{q^n}\), \(q\) a prime power, obtaining algorithms better than known ones. In applications such as Public Key Cryptography or Computational Algebra one has to performs arithmetic operations (in particular multiplication) in very large finite fields. It is then crucial to do such computations in the most efficient way. Most of the techniques to minimize the number of bit operations of an arithmetic operation in \(\mathbb{F}_{q^n}\) are based in the representation of the field elements in a suitable basis of the \(\mathbb{F}_q\)-vector space \(\mathbb{F}_{q^n}\), such as optimal normal basis, (see the book of [\textit{A. J. Menezes}, Applications of finite fields. Kluwer Academic Publishers (1993; Zbl 0779.11059)]). Another approach comes from an interpolation on algebraic curves due to \textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky} [J. Complexity 4, 285--316 (1988; Zbl 0668.68040)]. The multiplication in the \(\mathbb{F}_q\)-vector space \(\mathbb{F}_{q^n}\) can be represented by a tensor \(t=\sum_{i=1}^\lambda a_i\bigotimes b_i\bigotimes c_i \in\mathbb{F}_{q^n}^{*}\bigotimes \mathbb{F}_{q^n}^{*}\bigotimes \mathbb{F}_q\), (the product of \((x,y)\in F_{q^n}\) is then computed as \(x.y=\sum_{i=1}^\lambda a_i(x)b_i(y)c_i\)). The minimum value \(\mu_q(n)\) of these \(\lambda\) is called the bilinear complexity of multiplication in \( \mathbb{F}_{q^n}\) over \( \mathbb{F}_q\). Several authors, the author of the present paper among them, have given bounds and estimates for \(\mu_q(n)\). Section 1 of the paper collects such known results and Section 2 gives an improvement (Theorem 2.2) of some previous results of the author (quoted here as Theorem 1.3). In Section 3 the author applies Theorem 2.2 to several algebraic function fields (rational function fields, elliptic function fields and hyperelliptic function fields of genus 2) to deduce known as well as new results about \(\mu_q(n)\) (in particular he improves the efficiency of multiplication in the extension \(\mathbb{F}_{16^{16}}|\mathbb{F}_{16}\)). The final Section 4 studies some towers of algebraic function fields having good properties (Garcia-Stichtenoth towers of Artin-Schreier extensions and Garcia-Stichtenoth-Rück towers of Kummer extensions). Supposing these towers satisfy certain reasonable conjectures the author obtains bounds for \(\mu_q(n)\) near the best asymptotic bound of \textit{I. E. Shparlinski, M. A. Tsfasman, S. G. Vladut} [Coding theory and algebraic geometry, Proc. Int. Workshop, Luminy/Fr. 1991, Lect. Notes Math. 1518, 145--169 (1992; Zbl 0805.14028)].