Gitterbasenreduktion mit Random Sampling und heuristischen Erweiterungen

Lattice Basis Reduction with Random Sampling and Heuristic Extensions

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 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.show moreshow less
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 enThis 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.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • frontdoor_exportcitavi

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Institutes:Mathematik
Author: Heiko Vogel
Advisor:Dr. habil Alfred Wassermann
Granting Institution:Universität Bayreuth,Fakultät für Mathematik, Physik und Informatik
Date of final exam:20.07.2011
Year of Completion:2011
SWD-Keyword:Abzählen; Ganzzahliges Gitter; Gitter <Mathematik>; Heuristik; Zufall
Tag:Ganzzahlig-Lineare Gleichungssysteme; Gitterbasenreduktion; Random Sampling; Siebverfahren
heuristical sieve; integer linear equation systems; lattice; lattice basis reduction; random sampling
Dewey Decimal Classification:510 Mathematik
MSC-Classification:05A99 None of the above, but in this section
06B99 None of the above, but in this section
URN:urn:nbn:de:bvb:703-opus-8963
Document Type:Doctoral Thesis
Language:German
Date of Publication (online):05.08.2011