Multiplication dans les corps finis avec des algorithmes de type Chudnovsky sur la droite projective

Les utilisations des corps finis, que ce soit dans le cadre d'études théoriques aussi bien que dans des applications, motivent à en avoir une arithmétique efficace. A l'instar de la généralisation de Goppa des codes de Reed-Solomon aux codes de géométrie algébrique, David et Gregory Chudnovsky ont proposé une méthode étendant l'interpolation polynomiale à celle sur les courbes algébriques. Dans cet exposé, nous proposons une construction récursive générique d'algorithmes d'interpolation sur la droite projective pour multiplier dans une extension de degré quelconque d'un corps fini. Il s'agit d'une spécialisation de la méthode introduite par les frères Chudnovsky. Nous utiliserons des généralisations de cette méthode, notamment l'évaluation à des places de degrés arbitraires. Nos algorithmes correspondent aux techniques usuelles d'interpolation polynomiale dans les petites extensions, et sont définis récursivement lorsque le degré de l'extension augmente. Nous verrons que leur complexité bilinéaire est compétitive, et qu'ils sont constructibles en temps polynomial. Au long de l'exposé, nous présenterons également les liens entre ces algorithmes et les codes correcteurs d'erreurs,  et discuterons de l’optimisation de leur complexité totale.