Algorithme LLL
L’algorithme LLL, des initiales de A. Lenstra, H. Lenstra et L. Lovász, est un algorithme de réduction de réseau qui s'exécute en temps polynomial.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/27/Lattice-reduction.svg/220px-Lattice-reduction.svg.png)
Présentation
L'algorithme LLL procède à une réduction de base de réseau. Il prend en entrée un nombre d de vecteurs de base d'un réseau, tels que ces vecteurs soient de dimension n et de norme inférieure à B, et retourne en sortie une base de réseau LLL-réduite, c'est-à-dire presque orthogonale, en temps .
Pseudo-code
L'algorithme LLL repose sur l'algorithme de réduction faible de bases, qui permet de rendre une base presque orthogonale.
Entrée : Une baseSortie : Une base réduite issue de
LLL(B): B =
ReducFaible(B) *On fait Gram-Schmidt* Pour i=1 à n : Pour j= 1 à i-1 :
![]()
Si B est réduite retourne B Sinon
echanger(
,
) retourne LLL(B)
Applications
À l'origine, les applications consistaient en la production d'un algorithme de factorisation des polynômes à coefficients rationnels en produits de polynômes irréductibles, ainsi qu'en la résolution des problèmes d'optimisation linéaire avec solutions entières et dimensions fixes. D'autres applications ont été découvertes en cryptographie[1], notamment en cryptographie à clé publique, par exemple avec RSA, les cryptosystèmes basés sur le problème du sac à dos et NTRUEncrypt. En particulier l'algorithme LLL a rendu inefficaces tous les cryptosystèmes utilisant le problème du sac à dos[2]. Il sert également dans le cas des réseaux euclidiens.
Notes et références
Bibliographie
- (en) A. Lenstra, H. Lenstra et L. Lovász, « Factoring polynomials with rational coefficients », Mathematische Annalen, vol. 261, no 4, , p. 515–534 (DOI 10.1007/BF01457454, MR 0682664, lire en ligne)
- (en) Peter Borwein, Computational Excursions in Analysis and Number Theory, Springer, 2002 (ISBN 978-0-387-95444-8) : contient une description complète de l'algorithmes ainsi que des implémentations en pseudocode
- Abuaf Roland, Boyer Ivan, « Factorisation dans
», Exposé de maîtrise proposé par François Loeser, (lire en ligne)