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.

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]

Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Des informations de cet article ou section devraient être mieux reliées aux sources mentionnées dans la bibliographie, sources ou liens externes (mars 2016).

Améliorez sa vérifiabilité en les associant par des références à l'aide d'appels de notes.