Algorithmique des réseaux Euclidiens et Applications
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Damien Stehlé (Damien.Stehle)
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 [1], 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:
-
Théorie algorithmique des nombres : factorisation de polynômes,
équations diophantiennes, calculs dans les corps de nombres, ...
- Cryptanalyse : cassage des chiffrements de type “sac-à-dos”,
cryptanalyses modernes de RSA, ...
- Cryptographie : cryptosystèmes reposant sur la difficulté algorithmique
de problèmes liés aux réseaux (Ajtai-Dwork, GGH, NTRU)
- Arithmétique des ordinateurs : arrondi des fonctions élémentaires,
approximation polynomiale à coefficients contraints
- Mais aussi : optimisation combinatoire, théorie de l'information,
théorie algorithmique des groupes, ...
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
en cryptographie et en arithmétique des ordinateurs.
Bibliographie
-
A. Lenstra, H. Lenstra, and L. Lovász, Factoring
polynomials with rational coefficients. Mathematische Annalen 261 (4).
- A. May, Using LLL-Reduction for Solving RSA and
Factorization Problems: A Survey, disponible à l'URL:
http://www.informatik.tu-darmstadt.de/KP/alex.html
- H. Cohen, A course in computational algebraic number theory.
Springer.
- Notes de cours de D. Micciancio:
http://www.cse.ucsd.edu/classes/sp07/cse206a
- Notes de cours de O. Regev:
http://www.cs.tau.ac.il/ odedr/teaching/lattices_fall_2004/index.html
- S. Goldwasser, and D. Micciancio,
Complexity of Lattice problems: a cryptographic perspective. Kluwer.