Algorithme LLL

Cet article est une ébauche concernant l’informatique. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

L'algorithme LLL, des initiales de A. Lenstra, H. Lenstra et L. Lovász, est un algorithme de réduction de réseau (en) qui s'exécute en temps polynomial (cf. théorie de la complexité). L'algorithme LLL prend en entrée un nombre d de vecteurs de base d'un réseau, tels que ces vecteurs sont de dimension n et de norme inférieure à B. L'algorithme retourne en sortie une base de réseau LLL-réduite, c'est-à-dire presque orthogonale, en temps

$O(d^5n\log^3 B)\,$.

À 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, notamment en cryptographie à clé publique, par exemple avec RSA, les cryptosystèmes basés sur le problème du sac à dos et NTRUEncrypt.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lenstra–Lenstra–Lovász lattice basis reduction algorithm » (voir la liste des auteurs)

• (en) A. Lenstra, H. Lenstra et L. Lovász, « Factoring polynomials with rational coefficients », dans Mathematische Annalen, vol. 261, n^o 4, 1982, p. 515–534 [texte intégral, lien DOI]  MR0682664

• (en) Peter Borwein (en), 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