LLL-Algorithmus

Der LLL-Algorithmus ist ein nach Arjen Lenstra, Hendrik Lenstra und László Lovász benannter, 1982 veröffentlichter 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

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

LLL-Basen

Definition

Üblicherweise werden LLL-Basen über ihre QR-Zerlegung <math>B = QR</math> definiert. Eine LLL-Basis <math>B = QR</math> zum Reduktionsfaktor <math>\delta \in \left[\frac{1}{4}, 1\right]</math> wird über folgende zwei Eigenschaften definiert:

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

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

Der Reduktionsfaktor <math>\delta</math> 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 <math>\delta=1</math> ist nicht bekannt, ob es einen effizienten Algorithmus gibt.

Eigenschaften

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

Algorithmus

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

Der Algorithmus folgt unmittelbar aus der Definition: Erzwinge Spalte für Spalte, dass <math>B</math> 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

Die Matrix <math>R</math> 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 <math>R</math> 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öchstens 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 <math>k</math>-te Spalte von <math>R</math>:

Für <math>i = k-1, \dots, 1</math> wiederhole:
<math>R_i := R_i - \left[\frac{r_{i,k}}{r_{k,k}}\right] R_k</math>

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

Anwendungen

Eine erste hervorragende Anwendung erhielt der LLL-Algorithmus 1984 bei der Widerlegung der mit der Riemannschen Vermutung zusammenhängenden Mertensschen Vermutung durch Andrew Odlyzko und Herman te Riele.<ref>A. M. Odlyzko, H. J. J. te Riele: <templatestyles src="Webarchiv/styles.css" />{{#if:20130216174731

      | {{#ifeq: 20130216174731 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Disproof of the Mertens conjecture. | {{#invoke:WLink|getEscapedTitle|Disproof of the Mertens conjecture.}} | {{#invoke:Webarchiv|getdomain|http://oai.cwi.nl/oai/asset/1823/1823A.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20130216174731}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Disproof of the Mertens conjecture. | {{#invoke:WLink|getEscapedTitle|Disproof of the Mertens conjecture.}} | {{#invoke:Webarchiv|getdomain|http://oai.cwi.nl/oai/asset/1823/1823A.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20130216174731}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Disproof of the Mertens conjecture. | {{#invoke:WLink|getEscapedTitle|Disproof of the Mertens conjecture.}} | {{#invoke:Webarchiv|getdomain|http://oai.cwi.nl/oai/asset/1823/1823A.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Disproof of the Mertens conjecture. | {{#invoke:WLink|getEscapedTitle|Disproof of the Mertens conjecture.}} | {{#invoke:Webarchiv|getdomain|http://oai.cwi.nl/oai/asset/1823/1823A.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Disproof of the Mertens conjecture. | {{#invoke:WLink|getEscapedTitle|Disproof of the Mertens conjecture.}} | {{#invoke:Webarchiv|getdomain|http://oai.cwi.nl/oai/asset/1823/1823A.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Disproof of the Mertens conjecture. | {{#invoke:WLink|getEscapedTitle|Disproof of the Mertens conjecture.}} | {{#invoke:Webarchiv|getdomain|http://oai.cwi.nl/oai/asset/1823/1823A.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20130216174731|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://oai.cwi.nl/oai/asset/1823/1823A.pdf}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Disproof of the Mertens conjecture.
    | {{#if: {{#invoke:WLink|isBracketedLink|Disproof of the Mertens conjecture.}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://oai.cwi.nl/oai/asset/1823/1823A.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://oai.cwi.nl/oai/asset/1823/1823A.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://oai.cwi.nl/oai/asset/1823/1823A.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} J. reine angew. Math. 357 (1985), S. 138–160</ref> Dabei wurde ein Gitter der Dimension 70 konstruiert und seine Basis reduziert, das es erlaubte, ein Problem der mehrdimensionalen inhomogenen diophantischen Approximation mit ausgewählten nichttrivialen Nullstellen der Riemannschen Zetafunktion näherungsweise zu lösen.

2006 wurde die Berechnung an Gittern der Dimension um 100 wiederholt und die Ergebnisse verbessert.<ref>T. Kotnik, H. J. J. te Riele: Mertens conjecture revisited. ANTS 7 (Lecture Notes Computer Science 4076) (2006), S. 156–167</ref>

Der Algorithmus findet Anwendung in vielen Bereichen, teilweise in modifizierter Version. Er lässt sich auch auf zum <math>\mathbb Z ^n</math> 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<ref>William R. Unger: Computing the character table of a finite group, Journal of Symbolic Computation 41 (2006) No. 8, 847–862</ref> aus der Gruppentheorie, der zum Finden von irreduziblen Charakteren einer Gruppe verwendet wird.

Da in bestimmten Anwendungen des Algorithmus die anfangs vorliegenden Basisvektoren eine außerordentliche Länge aufweisen können, wurde angestrebt, seine Laufzeit in Abhängigkeit von dieser Länge zu verringern. Es wurden Varianten entwickelt, die eine quadratische Zeitkomplexität bezüglich der Bitlänge der Ausgangsdaten<ref>Phong Q. Nguyen, Damien Stehlé: {{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf
       | {{#if: An LLL algorithm with quadratic complexity. | An LLL algorithm with quadratic complexity. }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: 2022-11 | , festgestellt im {{#invoke:DateTime|format|2022-11|F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: 2022-11 | , festgestellt im {{#invoke:DateTime|format|2022-11|F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: An LLL algorithm with quadratic complexity.
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 2022-11
       | {{#if:{{#invoke:DateTime|format|2022-11|F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: 2022-11 | , festgestellt im {{#invoke:DateTime|format|2022-11|F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 2022-11
         | {{#if:{{#invoke:DateTime|format|2022-11|F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf }}

SIAM J. Comput. 39 (2009) Nr. 3, S. 874–903</ref> oder sogar nahezu lineare Komplexität<ref>Andrew Novocin, Damien Stehlé, Gilles Villard: An LLL-reduction algorithm with quasi-linear time complexity. STOC 2011 (Symposium on Theory of Computing), S. 403–412</ref> besitzen.

Literatur

{{#invoke:Vorlage:Literatur|f}}
Phong Q. Nguyen, Brigitte Valée (Hrsg.): The LLL algorithm. Survey and applications. Springer 2010, ISBN 978-3-642-02294-4.
Murray R. Bremner: Lattice basis reduction: An introduction to the LLL algorithm and its applications. CRC Press 2011, ISBN 978-1-439-80702-6.

Weblinks

Gitter und Kryptographie (PDF; 1015 KB). Johann Wolfgang Goethe-Universität Frankfurt am Main, 17. Oktober 2011 (Skript für die Vorlesungen von Prof. C. P. Schnorr, Wintersemester 2010)
Phong Q. Nguyen: Lattice reduction algorithms: Theory and practice. eingeladener Powerpoint-Vortrag zur EUROCRYPT'11-Konferenz

Einzelnachweise