On The Effective Construction of Asymmetric Chudnovsky Multiplication Algorithms in Finite Fields Without Derivated Evaluation

2016/11/09 by Stéphane Ballet, Nicolas Baudru, Ballet, Stéphane +5
Computer Science · Engineering · #Algebraic Geometry (math.AG) #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #Polynomial and algebraic computation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1611.02883

openalex publication_date 2016/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Chudnovsky and Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear whith respect to the degree of the extension. Recently, Randriambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. We describe the effective algorithm of this asymmetric method, without derivated evaluation. Finally, we give examples with the finite field \F_16¹³ using only rational places, \F_4¹³ using also places of degree two and \F_2¹³ using also places of degree four.

Related

• Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
• On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields
• Multiplication in finite fields with Chudnovsky-type algorithms on the projective line
• On Chudnovsky-Based Arithmetic Algorithms in Finite Fields
• Optimization of the scalar complexity of Chudnovsky² multiplication algorithms in finite fields