Curves with many points and multiplication complexity in any extension of F_q
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\).
- scientific article; zbMATH DE number 125907
- On the bilinear complexity of the multiplication in small finite fields
- 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
- A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
- Abelian varieties over finite fields
- Algebraic complexities and algebraic curves over finite fields
- Algebraic function fields and codes
- scientific article; zbMATH DE number 125907 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- Lectures on the theory of algebraic functions of one variable
- On multiplication in algebraic extension fields
- On the complexity of multiplication in finite fields
- Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
- The genus of curves over finite fields with many rational points
- Efficient randomized generation of optimal algorithms for multiplication in certain finite fields
- 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.
- A tower with non-Galois steps which attains the Drinfeld-Vladut bound
- 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
- 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
- Optimization of the scalar complexity of Chudnovsky\(^2\) multiplication algorithms in finite fields
- The existence of \(\mathbb{F}_q\)-primitive points on curves using freeness
- On the scalar complexity of Chudnovsky\(^2\) multiplication algorithm in finite fields
- 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
- On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields
- Singular curves with line bundles L defined over F_q and with H^0(L)=H^1(L)=0
- An exhaustive computer search for finding new curves with many points among fibre products of two Kummer covers over \(\mathbb F_{5}\) and \(\mathbb F_{7}\)
- Finding optimal Chudnovsky-Chudnovsky multiplication algorithms
- Multiplication in small finite fields using elliptic curves
- scientific article; zbMATH DE number 125907 (Why is no real title available?)
- Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
- scientific article; zbMATH DE number 606784 (Why is no real title available?)
- 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
- Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm
- New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields
- Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm
- On some bounds for symmetric tensor rank of multiplication in finite fields
- scientific article; zbMATH DE number 5239033 (Why is no real title available?)
- Algebraic complexities and algebraic curves over finite fields
- Algebraic complexities and algebraic curves over finite fields
- Chudnovsky-type algorithms over the projective line using generalized evaluation maps
- Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity
- Finite field arithmetic in large characteristic for classical and post-quantum cryptography
- Determinantal polynomials and the base polynomial of a square matrix over a finite field
- Multiplication in finite fields with Chudnovsky-type algorithms over the projective line
- Explicit Riemann-Roch spaces in the Hilbert class field
- Elliptic butterflies
- 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 complexity in any extension of \(\mathbb{F}_q\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1808846)
