@inproceedings{8b7ff40de21f4606ab504dbf345c93e4,
title = "Finding optimal Chudnovsky-Chudnovsky multiplication algorithms",
abstract = "The Chudnovsky-Chudnovsky method provides today{\textquoteright}s best known upper bounds on the bilinear complexity of multiplication in large extension of finite fields. It is grounded on interpolation on algebraic curves: we give a theoretical lower threshold for the smallest bounds that one can expect from this method (with exceptions). This threshold appears often reachable: we moreover provide an explicit method for this purpose. We also provide new bounds for themultiplication in small-dimensional algebras over F2. Building on these ingredients, we: • explain how far elliptic curves can provide upper bounds for the multiplication over F2; • using these curves, improve the bounds for the multiplication in the NIST-size extensions of F2; • thus, turning to curves of higher genus, further improve these bounds with the well known family of classical modular curves. Although illustrated only over F2, the techniques introduced apply to all characteristics.",
keywords = "Chudnovsky-Chudnovsky interpolation, Ellipticmodular curves, Finite field arithmetic, Optimal algorithms, Tensor rank",
author = "Matthieu Rambaud",
note = "Publisher Copyright: {\textcopyright}Springer International Publishing Switzerland 2015.; 5th International Workshop on the Arithmetic of Finite Fields, WAIFI 2014 ; Conference date: 27-09-2014 Through 28-09-2014",
year = "2015",
month = jan,
day = "1",
doi = "10.1007/978-3-319-16277-5\_3",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "45--60",
editor = "Ko{\c c}, \{{\c C}etin Kaya\} and Sihem Mesnager and Erkay Sava{\c s}",
booktitle = "Arithmetic of Finite Fields - 5th International Workshop, WAIFI 2014, Revised Selected Papers",
}