Soutenance de thèse de Thanh-Hung DANG

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 travaux 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 $mathbb{F}_{256}/mathbb{F}_4$. De plus, pour ce corps, notre construction est la meilleure connue en terme de complexité totale. Les sources des programmes Magma utilisés dans cette thèse sont données en appendice.

The evaluation-interpolation algorithm on algebraic curves, introduced by D.V. and G.V. Chudnovsky in 1987, is the basis of algorithmic techniques currently providing the best bounds of the bilinear complexity of multiplication in finite fields. In particular, these algorithms are known to have asymptotically linear or quasi-linear bilinear complexity. But until now no work has been done on the analysis of their scalar complexity. Therefore, in this thesis we are interested in the scalar complexity of these algorithms. More precisely, we present a generic strategy to obtain Chudnovsky-type algorithms with optimized scalar complexity. This complexity is directly related to a representation of the underlying Riemann-Roch spaces aimed at obtaining sparse matrices. The theoretical and numerical results obtained suggest that our optimization strategy is independent of the choice of the divisor used to construct the Riemann-Roch spaces. Using this strategy, we improve by 27% the scalar complexity of the construction of Baum-Shokrollahi (1992) on the field $mathbb{F}_{256}/mathbb{F}_4$. Moreover, for this field, our construction is the best known in terms of total complexity. The sources of the Magma programs used in this thesis are given in appendix.