An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields
type: Item
instance of: scholarly article
title: An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields
zbMATH Open document ID: 1099.11073
published in: Theoretical Computer Science
publication date: 2006-03-24T00:00:00Z
review text: 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 …
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 5015108
zbMATH Keywords: algorithms
zbMATH Keywords: bilinear complexity
zbMATH Keywords: finite fields
zbMATH Keywords: algebraic function fields
zbMATH Keywords: algebraic curves
author: S. Ballet
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.11.045
OpenAlex ID: W2068589874
cites work: Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)
cites work: Quasi-optimal algorithms for multiplication in the extensions of \(\mathbb F_{16}\) of degree 13, 14 and 15
cites work: Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of \(\mathbb F_q\)
cites work: Multiplication algorithm in a finite field and tensor rank of the multiplication.
cites work: On the bounds of the bilinear complexity of multiplication in some finite fields
cites work: On the existence of non-special divisors of degree \(g\) and \(g-1\) in algebraic function fields over \(\mathbb{F}_2\)
cites work: Q3000307
cites work: An optimal algorithm for multiplication in \(\mathbb{F}_{256}/\mathbb{F}_ 4\)
cites work: On the bilinear complexity of the multiplication in small finite fields
cites work: Algebraic complexities and algebraic curves over finite fields
cites work: Characterization of Division Algebras of Minimal Rank and the Structure of their Algorithm Varieties
cites work: Lectures on the theory of algebraic functions of one variable
cites work: A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
cites work: On tame towers over finite fields
cites work: Q3216750
cites work: Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
cites work: Q4027646
cites work: On multiplication in algebraic extension fields
DOI: 10.1016/J.TCS.2005.11.045
description: scientific article; zbMATH DE number 5015108