Calcul des racines de polynômes dans les corps finis de Fourier

La recherche des racines d'un polynôme à coefficients dans un corps fini est une brique de base en calcul formel, utilisé pour des problèmes tels que l'interpolation creuse. On connaît des algorithmes probabilistes polynomiaux pour ce problème depuis une quarantaine d'années, mais on ne dispose à l'heure actuelle d'aucun algorithme déterministe de complexité polynomiale.
Dans mon exposé, je présenterai plusieurs algorithmes (déterministe, probabiliste et heuristique) basés sur une nouvelle approche du problème qui utilise un outil appelé transformée de Graeffe. Ces algorithmes sont particulièrement efficaces dans le cas de corps finis dits de Fourier, c'est-à-dire dont l'ordre du groupe multiplicatif est divisible par une grande puissance de 2. Ces corps finis apparaissent naturellement en calcul formel dans des approches modulaires car ils sont adaptés à l'utilisation de transformées de Fourier rapide.