Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)
type: Item
instance of: scholarly article
title: Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)
zbMATH Open document ID: 0953.11022
author: S. Ballet
published in: Finite Fields and their Applications
publication date: 2000-02-10T00:00:00Z
review text: The subject of this paper concerns bounds for the bilinear complexity \(\mu_n(q)\) of multiplication in the finite field \(\mathbb F_{q^n}\) viewed as an \({\mathbb F_q}\)-algebra. An essential tool is \textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky}'s approach to the construction of fast bilinear multiplication algorithms via algebraic curves [J. Complexity 4, 285-316 (1988; Zbl 0668.68040)] (see also \textit{I. E. Shparlinski, M. A. Tsfasman} and \textit{S. G. Vladut} [Coding theory and algebraic geometry, Proc. Int. Workshop, Luminy/Fr. 1991, Lect. Notes Math. 1518, 145-169 (1992; Zbl 0805.14028)]). It is known that \(\mu_n(q)\geq 2n-1\) with equality holding if and only if \(q\geq 2n-2\) [see \textit{H. F. de Groote}, SIAM J. Comput. 12, 101-117 (1983; Zbl 0513.68039)]. The optimal algorithms realizing the lower bound \(2n-1\) all can be viewed as certain algorithms on the projective line over \(\mathbb F_q\); [cf. \textit{S. Winograd}, Theor. Comput. Sci. 8, 359-377 (1979; Zbl 0404.12016) and \textit{D. V.} and \textit{G. V. Chudnovsky}, Proc. Natl. Acad. Sci. USA 84, 1739-1743 (1987; Zbl 0644.68066)]. The aforementioned optimal algorithms were generalized to (projective, geometrically irreducible, non-singular algebraic) curves satisfying certain arithmetical conditions; cf. \textit{D. V.} and \textit{G. V. Chudnovsky} [Zbl 0668.68040], \textit{I. E. Shparlinski} et al. [Zbl 0805.14028]. Using a slightly modified version of these algorithms on elliptic curves \textit{M. A. Shokrollahi} [SIAM J. Comput. 21, 1193-1198 (1992; Zbl 0778.11075)] noticed that \(\mu_n(q)=2n\) provided that \(q/2+1<n<N_q(1)/2\), where \(N_q(1)\) is the number of \(\mathbb F_q\)-rational points of an optimal elliptic curve over \(\mathbb F_q\). The main results of this paper are: (I) A generalization of Shokrollahi's result, namely: \(\mu_q(n)\leq 2n+g-1\) whenever there exists a curve of genus \(g\) such that (a) it has at least one point of degree \(n\), and (b) it has more tha…
reviewed by: Fernando Torres
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 14H25
zbMATH DE Number: 1369827
zbMATH Keywords: bilinear complexity
zbMATH Keywords: finite fields
zbMATH Keywords: algebraic function fields
zbMATH Keywords: algebraic curves
MaRDI profile type: Publication
full work available at URL: ffta.1999.0255
OpenAlex ID: W1998210995
cites work: Q4331740
cites work: Algebraic complexities and algebraic curves over finite fields
cites work: Lectures on the theory of algebraic functions of one variable
cites work: The genus of curves over finite fields with many rational points
cites work: A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
cites work: On the complexity of multiplication in finite fields
cites work: Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
cites work: Q4027646
cites work: Algebraic function fields and codes
cites work: Abelian varieties over finite fields
cites work: On multiplication in algebraic extension fields
DOI: 10.1006/FFTA.1999.0255
description: scientific article; zbMATH DE number 1369827