On the scalar complexity of Chudnovsky multiplication algorithm in finite fields

Sur la complexité scalaire de l'algorithme de multiplication de type Chudnovsky dans les corps finis

Stéphane Ballet (1) , Alexis Bonnecaze (1) , Thanh-Hung Dang

1 I2M - Institut de Mathématiques de Marseille

We propose a new construction for the multiplication algorithm of D.V. and G.V. Chudnovsky in order to improve scalar algebraic complexity. In particular, we improve the Baum-Shokrollahi construction for multiplication in F256/F4 based on the elliptic Fermat curve x 3 + y 3 = 1.

Mots clés: Algebraic function field; Finite field; Algebraic complexity

Domaines: Géométrie algébrique [math.AG]

Stéphane Ballet, Alexis Bonnecaze, Thanh-Hung Dang. On the scalar complexity of Chudnovsky multiplication algorithm in finite fields. International Conference on Algebraic Informatics, CAI 2019, Jun 2019, Niš, Serbia. pp.64-75. ⟨hal-02187320⟩