Algorithmes rapides : de la théorie des types à la théorie des nombres

En dépit du titre pompeux et grandiloquent, cet exposé va suivre une ligne de recherche bien précise et délimitée, que j'ai suivie pendant ma thèse. Je vais commencer par parler de transposition de circuits arithmétiques et de son application à la transposition de code. Ensuite, je vais aborder des questions d'arithmétique des corps finis, et des tours d'extension d'Artin-Schreier en particulier ; les résultats sur la transposition de code vont me permettre de construire des familles de tours d'Artin-Schreier asymptotiquement optimales. Enfin, je vais montrer comment ces résultats permettent d'améliorer le calcul d'isogénies entre courbes elliptiques et je vais en discuter les implications en cryptologie. Le fil conducteur de l'exposé est la recherche d'algorithmes quasi-optimaux ou rapides (à la fois asymptotiquement et en pratique) pour les problèmes auquels je m'intéresse. Pour chacune des parties je vais présenter mes résultats et je vais citer les problèmes encore ouverts et les perspectives.