Algorithme LLL
Outils
Général
Imprimer / exporter
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.
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 .
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)
À 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.
Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().
Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.