1. Construction of asymmetric Chudnovsky-type algorithms for multiplication in finite fields.
- Author
-
Ballet, Stéphane, Baudru, Nicolas, Bonnecaze, Alexis, and Tukumuli, Mila
- Subjects
MULTIPLICATION ,ALGORITHMS ,ALGEBRAIC curves ,FINITE fields ,INTERPOLATION - Abstract
The original algorithm of D.V. Chudnovsky and G.V. Chudnovsky for the multiplication in extensions of finite fields provides a bilinear complexity which is uniformly linear with respect to the degree of the extension. Recently, Randriambololona generalized the method, allowing asymmetry in the interpolation procedure. The aim of this article is to make effective this method. We first make explicit this generalization in order to construct the underlying asymmetric algorithms. Then, we propose a generic strategy to construct these algorithms using places of higher degrees and without derivated evaluation. Finally, we provide examples of three multiplication algorithms along with their Magma implementation: in F 16 13 using only rational places, in F 4 5 using also places of degree two, and in F 2 5 using also places of degree four. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF