Algorithmique des réseaux euclidiens et applications

Master Pro ISFA, filière Codes, Cryptographie et Sécurité, Hiver 2008.


Un réseau euclidien est une grille de points régulièrement espacés dans Rn pour un certain n. L'étude mathématique de ces objets date de la fin du 19e siècle, avec les travaux de Hermite et Minkowski sur la géométrie des nombres. Leur étude informatique remonte au début des années 1980, avec l'article fondateur de Arjen Lenstra, Hendrik Lenstra et Laszló Lovász, dans lequel ils décrivent ce qui est maintenant connu sous le nom d'algorithme LLL. L'algorithmique des réseaux a alors connu un essor considérable, qui s'explique par la grande diversité de ses applications: Dans ce cours, nous introduirons les réseaux euclidiens, les problèmes algorithmiques qui leur sont propres et les principaux algorithmes qui leur sont consacrés. Nous insisterons particulièrement sur les applications (destructives et constructives) en cryptographie.


Beaucoup de matériel lié au cours se trouve .
Un exemple d'exécution de l'algorithme LLL.

Travaux pratiques

Voici du code PARI/GP de solutions possibles.