LLLAlgorithmus

Der LLL-Algorithmus, abgekürzt LLL, ist ein Algorithmus zur Reduktion von Basisvektoren eines Gitters. Ein Gitter ist eine diskrete Untermenge von R^n, erzeugt durch ganzzahlige Linearkombinationen einer Basis. Ziel des Verfahrens ist es, eine LLL-reduzierte Basis zu finden, bei der die Basisvektoren kurz und weitgehend orthogonal erscheinen.

Eingabe und Parameter: Gegeben sei eine Gitterbasis B = {b1, …, bn} in R^m mit ganzzahligen Koordinaten. Es wird ein Parameter δ gewählt mit 1/2 < δ < 1, häufig δ = 3/4. Das Ausgangsergebnis ist eine neue Basis, die LLL-reduziert ist, wobei die Vektoren an Länge und Struktur möglichst vorteilhaft sind.

Funktionsweise: Das Verfahren nutzt die Gram-Schmidt-Orthogonalisierung. Für die Koeffizienten μ_{i j} = ⟨b_i, b_j^*⟩ / ||b_j^*||^2 wird eine Size-Reduktion durchgeführt, d. h. b_i := b_i − round(μ_{i j}) b_j für alle j < i. Anschließend wird die Lovász-Bedingung δ ||b_{i−1}^*||^2 ≤ ||b_i^*||^2 überprüft. Falls sie verletzt ist, werden zwei benachbarte Basisvektoren getauscht und der Prozess fortgesetzt. Durch wiederholte Size-Reductions und Vertauschungen entsteht eine LLL-reduzierte Basis.

Eigenschaften und Komplexität: Die Ausgabe erfüllt die LLL-Kriterien. Das erste Basisvektormaß liegt innerhalb einer bekannten Grenze von 2^{(n−1)/2} × λ1, wobei λ1 die Länge des kürzesten Vektors des Gitters ist. Die Laufzeit ist polynomiell in der Eingabemenge, insbesondere für festgelegte Dimension n; bei wachsender n wächst der Aufwand exponenziell.

Anwendungen und Varianten: LLL wird in der Zahlentheorie, Kryptanalyse, zum Finden kurzer Vektoren in Gittern, zur Erkennung von Näherungsbeziehungen und als Baustein in fortgeschrittenen Verfahren wie BKZ eingesetzt. Historisch stammt der Algorithmus aus dem Jahr 1982 von Lenstra, Lenstra und Lovász.