Polynomial construction of Chudnovsky-type algorithms with a linear bilinear complexity

Construction polynomiale d'algorithmes de multiplication de type Chudnovsky de complexité bilinéaire linéaire La multiplication dans une extension finie d'un corps fini nécessite un certain nombre de multiplications bilinéaires, qui dépendent des deux éléments multipliés. L'étude de la complexité bilinéaire consiste à réduire ce nombre d'opérations.La méthode de D.V. et G.V. Chudnovsky (1988) permet de construire des algorithmes de multiplication ayant une bonne complexité bilinéaire. Ce sont des algorithmes d'évaluation/interpolation sur les courbes algébriques. Il existe deux stratégies pour construire de tels algorithmes lorsque le degré de l'extension grandit. La première est d'utiliser des courbes de genres croissants afin d'obtenir suffisamment de places rationnelles. Celle-ci fournit des algorithmes ayant une complexité bilinéaire linéaire en le degré de l'extension, mais dont la complexité de construction n'est pas connue à ce jour. L'autre stratégie consiste à fixer le genre et évaluer sur des places de degrés croissants. Dans le cas du genre 1, on obtient alors des algorithmes constructibles en temps polynomial, dont la complexité bilinéaire asymptotique est quasi-linéaire. Nous commençons par étudier la construction effective des algorithmes de type Chudnovsky sur la droite projective. Nous proposons des algorithmes constructibles génériquement et en temps polynomial, qui possèdent une complexité bilinéaire quasi-linéaire. Nous introduisons également une stratégie d'optimisation de la complexité totale de ces algorithmes. Enfin, nous proposons une méthode de construction hybride, et obtenons ainsi pour la première fois des algorithmes de type Chudnovsky ayant une complexité bilinéaire linéaire, et qui sont constructibles en temps polynomial.