Algorithmique des réseaux euclidiens et applications
Master
d'informatique fondamentale de l'École Normale Supérieure
de Lyon, Automne 2007.
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:
- 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.
NEWS
- [05/11] Rendu des rapports: damien point stehle at ens-lyon point fr.
- [08-09/11] Soutenances, en salle du conseil (au 3e étage,
après l'amphi B).
- [13/11] Séminaire du LIP.
- [14/11] Début du cours de C-P Jeannerod.
- Invariants des réseaux euclidiens : pdf.
- Théorème de Blichfeld : pdf.
- Algorithme de Gauss : pdf.
- Configuration de sortie de l'algorithme LLL : pdf.
- Relations linéaires entières entre nombres réels :
code Magma.
- Notes de cours d'étudiants scribes disponibles sur la page de Florian Hatat.
- Horaires : mercredi de 8h à 10h et jeudi de 10h15
à 12h15 (sauf exceptions).
- Responsable : Damien Stehlé,
bureau Sud 329.
- Évaluation : rapport et exposé de présentation d'un article avec question de cours.
- L'article est à aller retirer dans mon bureau : Sud 329.
- Évaluation : rapport et soutenance à partir
d'un article, avec petite question de cours lors de la soutenance.
- Date limite pour le rapport : 05/11.
- Le rapport fera au plus 3 pages. Il est rédigé
en Anglais ou en Francais. Il ne s'agit pas uniquement d'un
résumé de l'article, un avis critique est très
souhaité.
- La soutenance est constituée de 20 minutes de
présentation de l'article, en Anglais ou en Francais, sur
n'importe quel support; puis de questions, dont une petite question de
cours.
- Voici une tentative d'emploi du temps pour les soutenances.
Si vous n'apparaissez pas, c'est que vous n'avez pas retiré
d'article pour le moment (il est encore temps de le faire!). Si les
horaires ne vous conviennent pas, merci de me l'indiquer, avec des
permutations possibles.
- Jeudi 08/11, matin : Mioara (8h), Mihai (8h30), Planul (9h),
Donzel (9h30), Mouilleron (10h), Orgerie (10h30), Funke (11h).
- Jeudi 08/11, après-midi : Marc (13h30), Keller (14h),
Schwander (14h30), Panhaleux (15h), Derouet-Jourdan (15h30), Lassalle
(16h), Delacourt (16h30), Provillard (17h), Aubrun (17h30).
- Vendredi 09/11, matin : Dufosse (8h), Rieg (8h30), Hatat (9h),
Fouche (9h30), Pujol (10h), Briquel (10h30), Benureau (11h).
Notes de cours
Livres
- Modern computer Algebra, chapitres 16 et 17.
Joachim von zur Gathen et Jurgen Gerhard, Cambridge University Press.
- An Algorithmic Theory of Numbers, Graphs, and Convexity.
László Lovász, CBMS-NSF Regional Conference Series
in Applied Mathematics.
- Complexity of Lattice Problems, A Cryptographic Perspective,
Shafi Goldwasser et Daniele Micciancio, Kluwer Academic Publishers.
Thèses
Autres
- Lattices, un survey de Hendrik Lenstra.
- NTL et MAGMA contiennent des implantations de LLL efficaces.