Algorithmes de type Chudnovsky sur la droite projective pour la multiplication dans les corps finis

ll existe différents modèles permettant de mesurer la complexité d'un algorithme de multiplication dans une extension finie d'un corps fini. La complexité bilinéaire d'un tel algorithme est le nombre de multiplications bilinéaires, dépendant des deux éléments que l'on souhaite multiplier, qu'il exécute.

La méthode de D.V. et G.V. Chudnovsky (1988) permet de construire des algorithmes ayant une bonne complexité bilinéaire. Ce sont des algorithmes d'évaluation/interpolation utilisant les points rationnels de courbes algébriques, i.e. les places rationnelles d'un corps de fonctions. Cette méthode a depuis été généralisée de différentes manières, et notamment à l'évaluation en des places de degrés arbitraires.

Dans cet exposé, nous proposons une construction générique récursive d'algorithmes de type Chudnovsky sur le corps des fonctions rationnelles, évaluant sur des places de degrés croissants. Notre construction permet d'obtenir des algorithmes d'interpolation polynomiale constructibles en temps polynomial et ayant une complexité bilinéaire intéressante, pour un degré d'extension quelconque.

Prépublication : https://arxiv.org/abs/2007.16082