LLL-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der LLL-Algorithmus ist ein nach Arjen Lenstra, Hendrik Lenstra und László Lovász benannter Algorithmus, der für ein Gitter eine Basis aus möglichst kurzen Vektoren berechnet. Diese Vektoren sind Approximationen für die kürzesten voneinander linear unabhängigen Vektoren des Gitters. Bei seiner Entdeckung war der LLL-Algorithmus der erste effiziente Gitterreduktionsalgorithmus.

Kurze Gittervektoren[Bearbeiten]

Eine Gitterbasis lässt sich als Matrix B = [b_1, \dots, b_n] \in \mathbb R^m angeben. Der kürzeste Gittervektor minimiert die Norm des Vektors \textstyle \sum_{i=1}^n t_i b_i, wobei t_1, \dots, t_n \in \mathbb Z nicht alle gleich 0 sind. Der LLL-Algorithmus führt diese Minimierung bezüglich der euklidischen Norm durch.

LLL-Basen[Bearbeiten]

Definition[Bearbeiten]

Üblicherweise werden LLL-Basen über ihre QR-Zerlegung B = QR definiert. Eine LLL-Basis B = QR zum Reduktionsfaktor \delta \in [0.25, 1] wird über folgende zwei Eigenschaften definiert:

  1. 2|r_{i, j}| \le r_{j, j}, 1 \le j < i \le n (Längenreduktion),
  2. \delta r_{i, i}^2 \le r_{i+1, i}^2 + r_{i+1, i+1}^2, 1 \le i < n (LLL-Eigenschaft)

Dabei sind r_{i, j} die Einträge der Matrix R. Es wird angenommen, dass die QR-Zerlegung von B so durchgeführt wird, dass die Hauptdiagonale von R keine negativen Elemente enthält.

Der Reduktionsfaktor \delta gibt die Stärke der Reduktion an: Je näher er an 1 liegt, desto kürzer sind die Vektoren der reduzierten Basis. Für \delta=1 ist nicht bekannt, ob es einen effizienten Algorithmus gibt.

Eigenschaften[Bearbeiten]

LLL-reduzierte Basen approximieren die kürzesten Vektoren mit einem Approximationsfaktor, der exponentiell in der Anzahl der Vektoren ist. Im Folgenden sei \alpha := \tfrac1{\delta-\frac14}. Offensichtlich ist \alpha \ge \tfrac43. Der i-te LLL-reduzierte Vektor b_i approximiert das i-te sukzessive Minimum \lambda_i auf folgende Weise: \tfrac{||b_i||^2}{\lambda_i^2} \le \alpha^{n-1}, wobei das i-te sukzessive Minimum die Länge des i-ten kürzesten Vektors ist, der von keiner Menge kürzerer Vektoren linear abhängig ist.

Algorithmus[Bearbeiten]

  1. Berechne die erste Spalte von R.
  2. Setze k := 2 (k ist die Spalte, die gerade bearbeitet werden soll; die ersten k-1 Spalten sind immer LLL-reduziert)
  3. Solange k \le n wiederhole: Berechne die k-te Spalte von R, längenreduziere sie (Algorithmus siehe unten). Prüfe, ob die LLL-Eigenschaft für die Spalten k-1 und k erfüllt ist.
  4. Falls ja: Setze k := k+1
  5. Falls nein: Vertausche Spalten k-1 und k, setze k := max(k-1, 2).

Der Algorithmus folgt unmittelbar aus der Definition: Erzwinge Spalte für Spalte, dass B eine LLL-Basis ist. Längenreduktion lässt sich leicht herbeiführen. Lediglich die LLL-Eigenschaft ist kompliziert, weil sie indirekt weit voneinander entfernte Spalten in Beziehung bringt. Darum ist es nötig, Spalten zu vertauschen und wieder einen Schritt zurückzugehen.

Längenreduktion[Bearbeiten]

Die Matrix R ist eine obere Dreiecksmatrix mit positiver Diagonale. Ziel der Längenreduktion ist es, alle Nicht-Diagonalelemente möglichst (betragsmäßig) klein zu machen, ohne das Gitter zu verändern. Jede Zeile von R hat folgenden Aufbau: null oder mehr Nullen, das Diagonalelement, null oder mehr weitere Elemente. Dabei besitzen die Nullen schon den kleinstmöglichen Betrag. Die LLL-Eigenschaft sorgt dafür, dass das Diagonalelement nicht allzu groß sein kann. Die Längenreduktion bewirkt nun für alle folgenden Elemente, dass sie betragsmäßig höchsten halb so groß wie das Diagonalelement sind. Das lässt sich dadurch herbeiführen, dass für jedes zu große Nicht-Diagonalelement die Spalte, die das entsprechende Diagonalelement enthält, so oft addiert oder subtrahiert wird, bis das zu große Element betragsmäßig minimal ist. Der folgende Algorithmus längenreduziert die k-te Spalte von R:

  1. Für i = k-1, \dots, 1 wiederhole:
  2. R_i := R_i - [\frac{r_{i,k}}{r_{k,k}}] R_k

Dabei ist R_i der i-te Spaltenvektor von R und [\cdot] die Rundungsfunktion, die auf die nächste ganze Zahl rundet. Es ist wichtig, dass Schritt 2. mit fallendem und nicht mit steigendem i ausgeführt wird.

Anwendungen[Bearbeiten]

Der Algorithmus findet Anwendung in vielen Bereichen, teilweise in modifizierter Version. Er lässt sich auch auf zum \mathbb Z ^n isometrisch isomorphen Gittern anwenden, wobei die Reduktion dann bezüglich des dortigen Skalarprodukts durchgeführt wird. Ein eher unerwartetes Beispiel hierfür ist der Algorithmus von Unger[1] aus der Gruppentheorie, der zum Finden von irreduziblen Charakteren einer Gruppe verwendet wird.

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. William R. Unger: Computing the character table of a finite group, Journal of Symbolic Computation 41 (2006) No. 8, 847–862

Weblinks[Bearbeiten]