salle A. Turing CE4
24 juin 2013 - 14h00
Arithmétique rapide pour les tours d'extensions de corps finis
par Luca De Feo de UVSQ
Résumé : On se donne un corps fini F_q et un entier r, et on s'intéresse au
problème de représenter efficacement les éléments d'un corps fini
obtenu par une suite d'extensions de F_q de degré r. Par efficace on
entend une représentation dans laquelle les opérations arithmétiques
sur un ensemble quelconque d'éléments se font en temps
quasi-logarithmique en la taille de la plus petite extension de F_q
contenant tous les éléments. Cela peut être vu comme un premier pas
vers une représentation efficace de la clôture algébrique de F_p.
Le cas où r est égal à la caractéristique du corps a été résolu en
2009 par Schost et moi même, en utilisant les propriétés des
extensions d'Artin-Schreier et des techniques inspirées de la
résolution des systèmes polynomiaux. Le cas r = 2 a été résolu en 2012
par Doliskani et Schost, en utilisant des propriétés de la trace. Dans
un travail récent, avec Doliskani et Schost, nous présentons des
nouvelles solutions pour les cas q = ±1 mod r et r << q^(1/4). Ce
dernier travail repose sur des techniques de géométrie arithmétique et
fait le lien entre des idées de De Smit et Lenstra et d'autres de
Couveignes et Lercier.
Dans cet exposé je vais présenter les idées communes à ces différents
travaux, puis je vais essayer de faire un tour d'horizon des
techniques particulières à chacun, en me focalisant sur les plus
élégantes ou prometteuses.
