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.

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 $O (d^{5} n \log^{3} B)$ .

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 base  $B = (e_{1}, ..., e_{n})$ 
Sortie : Une base réduite issue de  $B$ 
LLL(B):
  B =  $(e_{1}, ..., e_{n}) \leftarrow$  ReducFaible(B)

  *On fait Gram-Schmidt*
  Pour i=1 à n :                      
     Pour j= 1 à i-1 :
         $a_{i, j} \leftarrow \frac{< e_{i}, e_{j} >}{< e_{j}, e_{j} >}$ 
       $e_{i} \leftarrow e_{i} - \sum_{j < i} a_{i, j} e_{j}$ 

  Si B est réduite
    retourne B
  Sinon
     $i \leftarrow m i n ({j \in [1, n] | | | e_{j + 1} + a_{j + 1, j} e_{j} | |^{2} < \frac{3}{4} | | e_{j} | |^{2}})$ 
    echanger( $e_{i}$ , $e_{i + 1}$ )
    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, 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. Il sert également dans le cas des réseaux euclidiens.

Notes et 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).

↑ 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).
↑ Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris/58-Clamecy, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 6 (« La méthode du sac à dos »), p. 538-539.

Bibliographie

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Les informations figurant dans cet article ou cette section doivent être reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (mars 2016).

Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.

(en) A. Lenstra, H. Lenstra et L. Lovász, « Factoring polynomials with rational coefficients », Mathematische Annalen, vol. 261, n^o 4,‎ 1982, 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 $ℤ [X]$ », Exposé de maîtrise proposé par François Loeser,‎ 20 juin 2007 (lire en ligne)

Portail de la cryptologie

Portail de l'informatique théorique

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

[boyer-2] Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris/58-Clamecy, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 6 (« La méthode du sac à dos »), p. 538-539.