https://almasty.lip6.fr/~pierrot

PIERROT Cécile

Docteur
Équipe : ALMASTY
Date de départ : 31/12/2016
https://almasty.lip6.fr/~pierrot
Direction de recherche : Antoine JOUX

Le logarithme discret dans les corps finis

La cryptologie consiste en l’étude des techniques utilisées par deux entités pour communiquer en secret en présence d’une troisième. Ces techniques sont conçues autour de problèmes calculatoires réputés difficiles. Les propriétés mathématiques sous-jacentes à ces problèmes garantissent que l’attaque de tels algorithmes reste infaisable en pratique par un adversaire malveillant. Ainsi, les protocoles cryptographiques s’appuient sur diverses hypothèses, comme la difficulté présumée de factoriser de grands entiers, ou de calculer le logarithme discret d’un élément arbitraire dans certains groupes.
Cette thèse porte sur l’étude du problème du logarithme discret dans le groupe multiplicatif des éléments inversibles d'un corps fini.
Dans cet exposé nous proposerons un algorithme quasipolynomial par représentation de Frobenius, qui permet de résoudre le problème si le corps présente une caractéristique de petite taille, relativement à l’ordre total de celui-ci. En pratique et pour l'exemple, le record actuel de calcul de logarithme discret en caractéristique 3 fait maintenant appel à ce résultat.
Lorsque la caractéristique grandit, une autre méthode est requise. Nous présenterons d'abord le crible par corps de nombres multiples (MNFS) qui obtient à ce jour les complexités asymptotiques les plus basses pour un corps arbitraire de moyenne ou grande caractéristique. Enfin, nous introduirons la notion de matrice presque creuse, pour esquisser les grandes lignes d’un algorithme spécifique permettant d’expliciter le noyau d’une telle matrice. En pratique, celui-ci facilite l’étape d’algèbre linéaire sous-jacente à toute variante du crible par corps de nombres.
Soutenance : 25/11/2016 - 14h30 - Campus Jussieu- Tour Zamansky Salle 24è étage
Membres du jury :
Reynald Lercier (Université Rennes 1) [rapporteur]
Daniel Augot (Inria, Ecole Polytechnique)
Ronald Cramer (CWI, Amsterdam)
Guillaume Hanrot (ENS Lyon)
Antoine Joux (Fondation partenariale de l'UPMC)
Ariane Mézard (UPMC)
David Naccache (ENS Paris)

Publications 2013-2016

 Mentions légales
Carte du site |