Curves with many points and multiplication in finite fields (Q4027646)

[For the entire collection see Zbl 0745.00062.] The authors explain and develop an idea of \textit{D. V.} and \textit{G. V. Chudnovsky} [J. Complexity 4, No. 4, 285-316 (1988; Zbl 0668.68040)] on fast bilinear multiplication algorithms in high degree extensions of finite fields. This idea uses codes and curves over finite fields with many points. If the product \(xy\) in an extension \(\mathbb{F}_{q^ k}\) of the finite field \(\mathbb{F}_ q\) can be obtained by multiplications of the values \(a_ l (x)\) and \(b_ l(y)\) of \(\mathbb{F}_ q\)-linear forms \(a_ l\) and \(b_ l\), one speaks of a bilinear multiplication algorithm. The multiplicative complexity of multiplication in \(\mathbb{F}_{q^ k}\), denoted by \(\mu_{\mathbb{F}_ q} (\mathbb{F}_{q^ k}) = \mu_ q(k)\), is the minimum number of multiplications of the form \(a_ l (x).b_ l (y)\). Here the minimum is taken over all bilinear multiplication algorithms. The main object of this paper is to prove that \[ M_ q = \lim \sup_{k \to \infty} \mu_ q(k)/k\quad\text{and}\quad m_ q = \lim \inf_{k \to \infty} \mu_ q (k)/k \] are finite, which means that multiplicative complexity of multiplication is asymptotically linear in the degree of the extension. For that purpose the authors connect codes to bilinear multiplication algorithms and results on the complexity of these algorithms are obtained from coding theory. The other way around it appears that so-called supercodes \(S \subset \mathbb{F}_{q^ k} \oplus \mathbb{F}^ n_ q\) yield bilinear multiplication algorithms of multiplicative complexity \(n\). The idea of D. V. and G. V. Chudnovsky comes down to the fact that some algebraic geometric codes can be lifted to supercodes. By using results on \(A(q) = \lim \sup_{g \to \infty} N(q,g)/g\), where \(N(q,g)\) is the maximum number of \(\mathbb{F}_ q\)-rational points on a curve of genus \(g\) defined over \(\mathbb{F}_ q\), the authors derive upper bounds on \(m(q)\). By using Shimura curves the more interesting but more difficult problem of the finiteness of \(M_ q\) is solved. In the last section the authors compare their paper with the aforementioned paper of the Chudnovsky brothers.