Ein Algorithmus zur Gitterreduktion in Polynomialzeit, der zu einer gegebenen Basis eines euklidischen Gitters eine reduzierte Basis liefert, deren Vektoren relativ kurz und nach der Lovász-Bedingung nahezu orthogonal sind; vielfach eingesetzt in algorithmischer Zahlentheorie, Algebra und Kryptanalyse.

Prinzip

Nutzt Gram–Schmidt-Orthogonalisierung und lokale Size-Reduction-Schritte, gesteuert durch die Lovász-Ungleichung, um Basisvektoren iterativ durch kürzere Linearkombinationen zu ersetzen, bis eine reduzierte Basis erreicht ist.

Demonstration

Für ein ganzzahliges Gitter, erzeugt von den Zeilen einer Matrix, führt die Anwendung der LLL-Tausch- und Reduktionsoperationen zu einer Basis, die häufig einen kurzen Vektor enthält, der beim Faktorisieren von Polynomen über den Rationalen oder beim Angriff auf Rucksackinstanzen nützlich ist.

Fehlanwendung

LLL als deterministischen Shortest-Vector-Solver verwenden: die Ausgabe als den exakten kürzesten Gittervektor zu behandeln, obwohl LLL nur eine Approximation garantiert, kann zu falschen Sicherheits- oder algorithmischen Schlüssen führen.

Konsequenz

Bei korrekter Anwendung ergibt sich eine effizient berechenbare approximativ reduzierte Basis, die praktische Lösungen für Probleme wie rationale Rekonstruktion, Polynomberechnung, diophantische Approximation und das Brechen schwacher gitterbasierter Kryptosysteme ermöglicht.

Umkehrung

Das Gegenstück wäre, beliebige, nicht reduzierte Gitterbasen zu akzeptieren: lange, stark schiefe Basen, die kurze Vektoren verbergen und weitere Rechnungen ineffizient oder numerisch instabil machen.

Abgrenzung

Gilt für euklidische Gitter über Z oder Q mit moderater Dimension; schließt exakte Garantien für den kürzesten Vektor und sehr hochdimensionale Gitter aus, bei denen der Approximationsfaktor groß wird und andere Algorithmen (BKZ, exakte SVP-Solver) nötig sind.

Semantische Spannung

LLL wird häufig mit exakten SVP-Algorithmen oder mit heuristischen Gitter-Tamisierungsverfahren verwechselt; die Spannung besteht zwischen praktischer Approximation, beweisbaren Polynomialzeitgrenzen und dem Streben nach besserer Reduktionsqualität.

Synthese

Der LLL-Algorithmus ist ein in Polynomialzeit arbeitendes Verfahren, das Gram–Schmidt-Projektionen und lokale Lovász-Reduktionsschritte nutzt, um eine gegebene Gitterbasis in eine nachweislich reduzierte, praktisch nützliche Basis mit relativ kurzen, nahezu orthogonalen Vektoren zu verwandeln.