Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\) (Q1808846)

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 than \((2n+2g-2)\) \(\mathbb F_q\)-rational points; (II) The construction of infinitely many curves satisfying both the hypothesis (a) and (b) provided that \(q\) is a square, \(q\geq 9\), and \(n>q/2+1\). In addition, \(\mathbb F_q\)-maximal curves do satisfy (a) above as their genera \(g\) fulfill \(g\leq (\sqrt{q}-1)^2/4\) or \(g=\sqrt{q}(\sqrt{q}-1)/2\) [\textit{R. Fuhrmann} and \textit{F. Torres}, Manuscr. Math. 89, 103-106 (1996; Zbl 0857.11032)]. Therefore \(2n\leq \mu_q(n)\leq 2n+g-1\) whenever \(q/2+1<n<(q+3)/2+(\sqrt{q}-1)g\) with \(g\) being the genus of a \(\mathbb F_q\)-maximal curve. The proof of (I) uses the same method as in \textit{D. V.} and \textit{G. V. Chudnovsky}'s paper [Zbl 0668.68040]; (II) is proved by using a \textit{Garcia-Stichtenoth} optimal tower [\textit{G. Garcia} and \textit{H. Stichtenoth}, Invent. Math. 121, 211-222 (1995; Zbl 0822.11078)] as a building block. Finally, the author applies these results to show that for each \(q\), \(\mu_n(q)\) is upper bounded by a linear function of \(n\).