Scalar complexity of Chudnovsky-type algorithms of multiplication in finite fields

Complexité scalaire des algorithmes de type Chudnovsky de multiplication dans les corps finis L’algorithme de type évaluation-interpolation sur des courbes algébriques, introduit par D.V et G.V Chudnovsky en 1987, est à la base des techniques algorithmiques fournissant actuellement les meilleures bornes de la complexité bilinéaire de la multiplication dans les corps finis. En particulier, ces algorithmes sont connus pour avoir asymptotiquement une complexité bilinéaire linéaire ou quasi linéaire. Mais jusqu’à présent aucun travail ne s’était attaqué à l’analyse de leur complexité scalaire. Aussi, s’intéresse-t-on dans cette thèse à la complexité scalaire de ces algorithmes. Plus précisément, nous présentons une stratégie générique permettant d’obtenir des algorithmes de type Chudnovsky ayant une complexité scalaire optimisée. Cette complexité est directement liée à une représentation des espaces de Riemann-Roch sous-jacents visant à l’obtention de matrices creuses. Les résultats théoriques et numériques obtenus suggèrent que notre stratégie d’optimisation est indépendante du choix du diviseur permettant de construire les espaces de Riemann-Roch. En utilisant cette stratégie, nous améliorons de 27% la complexité scalaire de la construction de Baum-Shokrollahi (1992) sur le corps F256/F4. De plus, pour ce corps, notre construction est la meilleure connue en termes de complexité totale. Les sources des programmes Magma utilisés dans cette thèse sont données en appendice.