Chaining Multiplications in Finite Fields with Chudnovsky-type Algorithms and Tensor Rank of the k-multiplication

2024/10/16 by Stéphane Ballet, Ballet, Stéphane, Robert Rolland +1
Computer Science · Mathematics · #Algebraic Geometry (math.AG) #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #Tensor decomposition and applications #advanced mathematical theories

paper · doi:10.48550/arxiv.2410.12383

openalex publication_date 2024/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We design a class of Chudnovsky-type algorithms multiplying k elements of a finite extension of order n a finite field K. We prove that these algorithms give a tensor decomposition of the k-multiplication for which the rank is linear in n uniformly in q. We give uniform upper bounds of the rank of k-multiplication in finite fields. They use interpolation on algebraic curves which transforms the problem in computing the Hadamard product of k vectors with components in K. This generalization of the widely studied case of k=2 is based on a modification of the Riemann-Roch spaces involved and the use of towers of function fields having a lot of places of high degree.

Related

• On The Effective Construction of Asymmetric Chudnovsky Multiplication Algorithms in Finite Fields Without Derivated Evaluation
• Multiplication in finite fields with Chudnovsky-type algorithms on the projective line
• On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
• On Chudnovsky-Based Arithmetic Algorithms in Finite Fields
• On the tensor rank of multiplication in finite extensions of finite fields