Gitterbasis-Reduktion: LLL

• Algorithmus von Lenstra, Lenstra und Lovasz (1982)

• Gram-Schmidt-Koeffizienten μ_ij = ${\frac{{\langle b_i,b_j\rangle}}{{\langle b_j,b_j\rangle}}}$

  Gram-Schmidt-Basisvektoren b_i^* = b_i - $\sum_{{j<i}}^{}$μ_ijb_j^*

• Basis heißt size reduced, wenn ∀i, j : | μ_ij|≤1/2

  d.h., kann durch keinen Austausch b_i' = b_i - c⋅b_j verbessert werden

• LLL reduced, wenn außerdem (3/4)| b_i^*|²≤| μ_{i+1, i}b_i^* - b_i+1^*|²
• LLL-Algorithmus konstruiert solche Basis durch Reduzieren und Vertauschen, b₁ ist dann kurz:

  | b₁|≤2^(n-1)/2λ₁, wobei λ₁ = min{| v| : v∈L(B) $\setminus$ {0}}

• O. Regev: https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf