Conférence de Damien Stehlé organisée par le département d'informatique.
Un réseau est l’ensemble des combinaisons linéaires entières de vecteurs linéairement indépendants. Visuellement, le réseau forme une grille infinie de points régulièrement espacés. Les réseaux ont de nombreuses applications en informatique. Entre autres, ils apparaissent fréquemment en calcul formel, par exemple pour factoriser les polynômes à coefficients rationnels, et en cryptographie, aussi bien pour cryptanalyser que pour concevoir des protocoles. L’algorithme LLL, du nom de ses auteurs Arjen Lenstra, Hendriz Lenstra et László Lovász, permet de calculer une bonne représentation, ou base, d’un réseau donné. Cette représentation fournit de l’information intrinsèque sur le réseau manipulé. De nombreuses applications ont suivi la publication de l’algorithme LLL, et, du fait de ce succès, plusieurs accélérations algorithmiques ont par la suite été proposées. L’approche la plus efficace aujourd’hui repose, en interne, sur des calculs flottants en faible précision, donnant lieu à un algorithme hybride numérique-algébrique. Après avoir présenté les réseaux et quelques-unes de leurs applications, je décrirai l’approche hybride numérique-algébrique de l’algorithme LLL.
Catégories: Séminaire général du département d'informatique
Mot-clés : mathématiques, cryptographie, algorithme, cryptologie, Arithmétique, réseau euclidien, géométrie des nombres
Voir aussi
|
|
Cursus :
Damien Sthelé est enseignant-chercheur en informatique à l'ENS de Lyon. Médaille de bronze du CNRS 2012.
Cliquer ICI pour fermerDernière mise à jour : 13/10/2015
Tous droits réservés
@ 2011 ENS