Algorithme LLL

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Présentation[modifier | modifier le code]

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

.

Applications[modifier | modifier le code]

À 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. Il sert également dans le cas des réseaux Euclidiens.

Notes et références[modifier | modifier le code]

(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).

  1. Abderrahmane Nitaj, « Applications de l'algorithme LLL en cryptographie », sur Département de Mathématiques et Mécanique de l'Université de Caen Basse Normandie (UCBN).

Bibliographie[modifier | modifier le code]