On the scalar complexity of Chudnovsky^2 multiplication algorithm in finite fields

DOI10.1007/978-3-030-21363-3_6MaRDI QIDQ2175409zbMATH OpenOpenAlexFDO

Authors S. Ballet, Alexis Bonnecaze, Thanh-Hung Dang

Publication date 29 April 2020

Full work available at URL https://doi.org/10.1007/978-3-030-21363-3_6

zbMATH Keywords

algebraic complexityalgebraic function fieldfinite fieldscalar complexity

Mathematics Subject Classification ID

Arithmetic theory of algebraic function fields (11R58) Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Review text

The paper under review deals with the multiplicative complexity of multiplication in a finite field \(F_{q^n}\) which is the number of multiplications required to multiply in the \(F_q\)-vector space \(F_{q^n}\). The types of multiplications in \(F_q\) are the scalar multiplication and the bilinear one. The scalar multiplication is the multiplication by a constant in \(F_q\). The bilinear multiplication is a multiplication that depends on the elements of \(F_{q^n}\) that are multiplied. D. V. and G. V. Chudnovsky, generalizing interpolation algorithms on the projective line over \(F_q\) to algebraic curves of higher genus over \(F_q\), provided a method which enabled to prove the linearity of the bilinear complexity of multiplication in finite extensions of a finite field [\textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky}, J. Complexity 4, No. 4, 285--316 (1988; Zbl 0668.68040)]. This is the so-called Chudnovsky\(^2\) algorithm. In this paper, a new method of construction with an objective to reduce the scalar complexity of Chudnovsky\(^2\) multiplication algorithms is proposed. An optimized basis representation of the Riemann-Roch space \(L(2D)\) is sought in order to minimize the number of scalar multiplications in the algorithm. In particular, the Baum-Shokrollahi construction for multiplication in \(F_{256}/F_4\) based on the elliptic Fermat curve \(x^3 + y^3 = 1\) is improved. For the entire collection see [Zbl 1428.68013].

Recommendations

• Optimization of the scalar complexity of Chudnovsky\(^2\) multiplication algorithms in finite fields
• A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line
• Chudnovsky-type algorithms over the projective line using generalized evaluation maps
• Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
• Finding optimal Chudnovsky-Chudnovsky multiplication algorithms
• Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
• Quasi-optimal algorithms for multiplication in the extensions of \(\mathbb F_{16}\) of degree 13, 14 and 15
• An optimal algorithm for multiplication in \(\mathbb{F}_{256}/\mathbb{F}_ 4\)
• Chaining multiplications in finite fields with Chudnovsky-type algorithms and tensor rank of the k-multiplication
• Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)

Cited in

(7)

• Optimization of the scalar complexity of Chudnovsky\(^2\) multiplication algorithms in finite fields
• On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields
• Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
• On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
• Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm
• Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm
• A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line

This page was built for publication: On the scalar complexity of Chudnovsky\(^2\) multiplication algorithm in finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175409)