Gitterbasenreduktion mit Random Sampling und heuristischen Erweiterungen

Titelangaben

Vogel, Heiko:
Gitterbasenreduktion mit Random Sampling und heuristischen Erweiterungen.
Bayreuth , 2011
( Dissertation, 2011 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

Diese Dissertation beschäftigt sich mit dem mathematischen Teilgebiet der Gitterbasenreduktion. Aufbauend aus den Erkenntnissen der Diplomarbeit "Gitterbasenreduktion mit Random Sampling" werden verschiedene Modifikationen am ursprünglichen LLL- bzw. BKZ-Verfahren vorgenommen: Es wird der von C. Schnorr entwickelte Ansatz, den LLL-Austauschschritt um Tiefeneinfügungen zu erweitern, aufgegriffen und eine alternative Methode zum Basisaustausch für das BKZ-Verfahren vorgestellt. Ferner werden zwei unterschiedliche Verfahren von A. Wassermann und P. Nguyen zum Abschneiden von Enumerationsbäumen beschrieben. Die Random Sampling Strategie von Schnorr wurde überarbeitet, um ein schlechtes GSA-Verhalten des Gitters zu berücksichtigen und eine neuartige Strategie von Buchmann und Ludwig wurde implementiert, bei der das GSA-Verhalten vollkommen irrelevant ist. Schließlich wird ein grundlegendes, heuristisches Bewertungskonzept für Gittervektoren entwickelt, das im Rahmen eines von T. Vidick und P. Nguyen beschriebenen Siebverfahrens, Anwendung findet. Mit Hinblick auf die Qualität der erreichten Gitter-Reduktion für schwierige Market-Split-Probleme in Dimensionen ≈ 120, liefern diese neuen Methoden hervorragende Ergebnisse in äußerst kurzer Zeit (ca. 5 Stunden auf einem 3 GHz Rechner). Auch für Problemdimensionen > 500 sind die Resultate durchaus noch zufriedenstellend - allerdings ist hierbei der Rechenaufwand (> 7 Tage) nicht mehr zu vernachlässigen. Im Vergleich mit dem kommerziellen Programm CPLEX, das einen völlig anderen Ansatz zur Lösung von ganzzahlig-linearen Gleichungssystemen verfolgt, konnten sogar sehr gute Ergebnisse erzielt werden.

Abstract in weiterer Sprache

This dissertation describes the mathematical subject concerned with lattice basis reduction and analyzes several algorithms which are involved in solving lattice based problems. Stacked on the scientific findings of the diploma thesis "Gitterbasenreduktion mit Random Sampling" several modifications of the famous LLL-algorithm and the generalized BKZ-reduction are introduced: C. Schnorr’s method for extending the Lovasz step with deep insertions and a modified basis replacement routine for the enumeration step, which was first described by H. Hörner. Further, two different cutting techniques are explained, which allow to decrease the size of the enumeration tree. These techniques originate from A. Wassermann and P. Nguyen. Schnorr’s Random Sampling strategy is modified in order to deal with lattices, which have a bad GSA behaviour and an approach from Buchmann and Ludwig is implemented where the GSA behaviour gets totally irrelevant. Finally a heuristical evaluation concept for lattice vectors is developed and implemented in form of a modified sieve algorithm, which originates from Ajtaj, Kumar, Sivakumar (AKS) and has been extensively examined by T. Vidick and P. Nguyen afterwards. Regarding the quality of the achieved lattice reductions for hard market split problems in dimensions ≈ 120 these new methods produce excellent results in short time (about 5 hours on a machine with 3 GHz). Even for problem dimensions > 500 the findings are still quite satisfying, though the computation amount (> 7 days) is not negligible anymore. In comparison with the commercial program CPLEX, which uses completely different methods for solving integer linear programs, the results are remarkably very good and motivate further investigations in the field of lattice reduction.