- Algorithmus von Lenstra, Lenstra und Lovasz (1982)
- Gram-Schmidt-Koeffizienten
μij =
Gram-Schmidt-Basisvektoren
bi* = bi -
μijbj*
- Basis heißt size reduced,
wenn
∀i, j : | μij|≤1/2
d.h., kann durch keinen Austausch
bi' = bi - c⋅bj
verbessert werden
- LLL reduced, wenn außerdem
(3/4)| bi*|2≤| μi+1, ibi* - bi+1*|2
- LLL-Algorithmus konstruiert solche Basis
durch Reduzieren und Vertauschen, b1 ist dann kurz:
| b1|≤2(n-1)/2λ1, wobei
λ1 = min{| v| : v∈L(B)
{0}}
- O. Regev:
https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf