Curves with many points and multiplication in finite fields
bilinear multiplication algorithmcodescurves over finite fields with many pointsmultiplicative complexityShimura curvessupercodes
Curves over finite and local fields (11G20) Finite ground fields in algebraic geometry (14G15) Arithmetic ground fields for curves (14H25) Computational aspects of algebraic curves (14Q05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)
[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.
- Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)
- On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
- An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields
- Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
- scientific article; zbMATH DE number 606784
- A formula for constructing curves over finite fields with many rational points
- Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of F_q
- Multiplication algorithm in a finite field and tensor rank of the multiplication.
- Quasi-optimal algorithms for multiplication in the extensions of \(\mathbb F_{16}\) of degree 13, 14 and 15
- Tower of algebraic function fields with maximal Hasse-Witt invariant and tensor rank of multiplication in any extension of \(\mathbb{F}_2\) and \(\mathbb{F}_3\)
- Dense families of modular curves, prime numbers and uniform symmetric tensor rank of multiplication in certain finite fields
- Gaps between prime numbers and tensor rank of multiplication in finite fields
- On the bounds of the bilinear complexity of multiplication in some finite fields
- Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)
- Arcs and curves over a finite field
- Curves with many points and configurations of hyperplanes over finite fields
- An improvement of bilinear complexity bounds in some finite fields.
- On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation
- Construction of asymmetric Chudnovsky-type algorithms for multiplication in finite fields
- Curves with more than one inner Galois point
- Trisymmetric multiplication formulae in finite fields
- On the tensor rank of multiplication in any extension of \(\mathbb F_2\)
- On the bilinear complexity of the multiplication in small finite fields
- The equivariant complexity of multiplication in finite field extensions
- scientific article; zbMATH DE number 5896947 (Why is no real title available?)
- Faster polynomial multiplication via discrete Fourier transforms
- Group-theoretic lower bounds for the complexity of matrix multiplication
- Multiplication in small finite fields using elliptic curves
- scientific article; zbMATH DE number 5529005 (Why is no real title available?)
- Complexity of computation in finite fields
- scientific article; zbMATH DE number 606784 (Why is no real title available?)
- Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
- On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
- The quadratic hull of a code and the geometric view on multiplication algorithms
- New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields
- On some bounds for symmetric tensor rank of multiplication in finite fields
- Multiplication of polynomials modulo \(x^n\)
- A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line
- Algebraic complexities and algebraic curves over finite fields
- scientific article; zbMATH DE number 7758331 (Why is no real title available?)
- Chaining multiplications in finite fields with Chudnovsky-type algorithms and tensor rank of the k-multiplication
- Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity
- Lower bounds for additive complexity of linear operators and bilinear algorithms for matrix and polynomial multiplication over GF(2)
- Four families of squares of BCH codes and their complements
- The complete weight enumerator of the square of one-weight irreducible cyclic codes
- Introducing locality in some generalized AG codes
- On the square code of group codes
- Multiplication in finite fields with Chudnovsky-type algorithms over the projective line
- Explicit Riemann-Roch spaces in the Hilbert class field
- Elliptic butterflies
- On the non-special divisors in algebraic function fields defined over finite fields
- The Schur products of some binary LCD BCH codes
- A closed formula for the Geil-Matsumoto bound on numerical semigroups via Apéry sets
- An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields
- On the tensor rank of the multiplication in the finite fields
- On multiplication in finite fields
This page was built for publication: Curves with many points and multiplication in finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027646)
