Algorithme LLL

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

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

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

  Si B est réduite
    retourne B
  Sinon
    ${\displaystyle i\leftarrow min(\lbrace j\in [1,n]~|~||e_{j+1}+a_{j+1,j}e_{j}||^{2}<{\dfrac {3}{4}}||e_{j}||^{2}\rbrace )}$
    echanger(${\displaystyle e_{i}}$,${\displaystyle e_{i+1}}$)
    retourne LLL(B)