Verbesserte Analyse des LLL Algorithmus (Bachelor)
CITS » Lehre » Abschlussarbeiten

Man kann zeigen, dass der folgende Algorithmus bei Gittern kleiner Determinante zu einer Verbesserung des Approximationsfaktors beim LLL führt.
Berechne die HNF einer Basis.
Berechne LLL auf einem geeigneten Untergitter der hinteren Vektoren.

Daraus resultieren die folgenden Fragestellungen:
Wird der Approximationsfaktor durch Voranstellen der HNF besser oder nur die Analyse?
Kann die Analyse des LLL so verbessert werden, dass dieser Spezialfall abgedeckt wird?
Führen die Ergebnisse zu verbessertem Preprocessing für Gitterreduktionsalgorithmen?
Wie sind die Auswirkungen auf q-näre Gitter und deren Kryptanalyse?

Grundkenntnisse in Programmierung und Gittern erforderlich.

Ansprechpartner: A. May