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

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^{13}}$ using only rational places, $\F_{4^{13}}$ using also places of degree two and $\F_{2^{13}}$ using also places of degree four.
Keywords : complexity
Type de document :
Article dans une revue
Comptes Rendus Mathématique, Elsevier Masson, 2017, 355 (7), pp.729 - 733. 〈10.1016/j.crma.2017.06.002〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01620346
Contributeur : Aigle I2m <>
Soumis le : vendredi 20 octobre 2017 - 14:25:48
Dernière modification le : jeudi 18 janvier 2018 - 02:05:50

Identifiants

Collections

Citation

Stéphane Ballet, Nicolas Baudru, Alexis Bonnecaze, Mila Tukumuli. On The Effective Construction of Asymmetric Chudnovsky Multiplication Algorithms in Finite Fields Without Derivated Evaluation. Comptes Rendus Mathématique, Elsevier Masson, 2017, 355 (7), pp.729 - 733. 〈10.1016/j.crma.2017.06.002〉. 〈hal-01620346〉

Partager

Métriques

Consultations de la notice

36