CONSTRUCTION OF ASYMMETRIC CHUDNOVSKY ALGORITHMS WITHOUT DERIVATED EVALUATION FOR MULTIPLICATION IN FINITE FIELDS

Abstract : The Chudnovsky and Chudnovsky algorithm 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, Ran-driambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. In this article, we first translate this generalization into the language of algebraic function fields. Then, we propose a strategy to effectively construct asymmetric 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [195 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02115213
Contributor : Alexis Bonnecaze <>
Submitted on : Tuesday, April 30, 2019 - 10:27:43 AM
Last modification on : Friday, May 3, 2019 - 1:32:29 AM

File

AsymANMJSoumis.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02115213, version 1

Collections

Citation

Stéphane Ballet, Nicolas Baudru, Alexis Bonnecaze, Mila Tukumuli. CONSTRUCTION OF ASYMMETRIC CHUDNOVSKY ALGORITHMS WITHOUT DERIVATED EVALUATION FOR MULTIPLICATION IN FINITE FIELDS. 2019. ⟨hal-02115213⟩

Share

Metrics

Record views

63

Files downloads

27