Le logarithme discret dans les corps finis

par Mme Cécile Pierrot

lundi 14 nov. 2016, 14:00 → 15:00 Europe/Paris

XR203 (Limoges)

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. Cet exposé porte sur l’étude du problème du logarithme discret dans le groupe multiplicatif des éléments inversibles d'un corps fini. Je vous présenterai tout d'abord 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. Point de vue théorique, je vous exposerai les grandes lignes du 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, je propose d'introduire 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. Point de vue pratique cette fois-ci, celui-ci facilite l’étape d’algèbre linéaire sous-jacente à toute variante du crible par corps de nombres. Les résultats d'algèbre linéaire et en petite caractéristique sont issus d'un travail commun avec Antoine Joux, les travaux en moyenne caractéristique ont été réalisés de manière indépendante, et ceux en grande caractéristique sont le fruit d'une collaboration avec Razvan Barbulescu.