Les personnes qui possèdent un compte PLM-Mathrice sont invités à l'utiliser.
Séminaire Protection de l'Information, Codage, Cryptographie

Le logarithme discret dans les corps finis

by Mrs. Cécile Pierrot

lundi 14 novembre 2016 de au (Europe/Paris)
at Limoges ( XR203 )
Description
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.