Edouard Rousseau soutient sa thèse intitulée « Arithmétique efficace des extensions de corps finis », dirigée par Luca DE FEO, Hugues RANDRIAMBOLOLONA et Eric SCHOST le 12 juillet 2021.
La soutenance aura lieu à 15h en Amphi E, bâtiment Descartes.
Résumé : Les corps finis sont omniprésents en cryptographie et en théorie des codes, deux domaines de première importance dans les communications modernes. Ainsi, il est crucial de représenter les corps finis et d’y faire des calculs de la façon la plus efficace possible. Dans cette thèse, nous travaillons sur l’arithmétique des extensions de corps finis, de deux manières différentes et indépendantes.
Dans la première partie, nous étudions l’arithmétique d’une unique extension de corps fini Fpk. Une manière d’estimer la complexité d’un algorithme dans une extension est de compter le nombre de multiplications effectuées dans le corps de base Fp. Ce modèle est connu sous le nom de complexité bilinéaire. Dans cette thèse, nous généralisons les résultats connus pour la complexité bilinéaire à un nouveau type de complexité, qualifiée d’hypersymétrique. Nous fournissons un algorithme pour calculer la complexité hypersymétrique de la multiplication dans l’extension Fpk, ainsi qu’une implémentation et son analyse. Nous généralisons également aux cas hypersymétrique et multilinéaire des résultats asymptotiques connus dans le cas de la complexité bilinéaire classique.
Dans la seconde partie, notre but est de construire une structure de donnée efficace pour représenter plusieurs extensions simultanément, ainsi que les plongements entre elles. Ces plongements sont rarement uniques, et il faut donc s’assurer que les choix effectués soient compatibles, c’est-à-dire que dès lors que trois corps finis sont en jeu, le plongement calculé est indépendant du chemin parcouru. Nous donnons une implémentation de l’algorithme de Bosma-Canon-Steel, qui permet d’obtenir des plongements compatibles, et qui était uniquement disponible dans MAGMA, mais est désormais disponible dans le système de calcul formel Nemo. Nous proposons également une nouvelle construction nommée réseau standard de corps finis compatiblement plongés, inspirée de l’algorithme de Bosma-Canon-Steel et des polynômes de Conway, qui sont à la base d’une autre méthode populaire pour obtenir la compatibilité. Contrairement à l’utilisation des polynômes de Conway, notre méthode permet d’utiliser des corps finis définis de manière arbitraire, tout en restant efficace. Nous analysons en détails la complexité de nos algorithmes, et donnons une implémentation montrant que notre construction peut être utilisée en pratique.