LLL Algorithm
Der LLL-Algorithmus reduziert eine Gitterbasis in Polynomialzeit zu einer nahezu orthogonalen; sein erster Vektor ist höchstens 2^((n-1)/2)-mal so lang wie der kürzeste Vektor.
Zweck
Führt approximative Gitterreduktion in Polynomialzeit durch; vielseitig in Kryptoanalyse und Zahlentheorie eingesetzt.
Mechanismus
Nach Gram-Schmidt-Orthogonalisierung prüft er die Lovász-Bedingung (|μ_{i,i-1}|≤1/2 und B_i≥(3/4-μ^2)B_{i-1}) und tauscht sowie reduziert, wenn sie verletzt ist. Der erste Vektor der Ausgabebasis hat die Länge ≤2^((n-1)/2) * λ_1.
Anwendungsfälle
- Gitter-Kryptoanalyse
- Polynomfaktorisierung
- CVP-Approximation