Implementierung der Gitterbasenreduktion in Segmenten

  • Die Gitterbasenreduktion hat in der algorithmischen Zahlentheorie und der Kryptologie bedeutende und praktisch relevante Anwendungen [Joux und Stern, 1998; Nguyen und Stern, 2000; Nguyen, 2001]. Ein wesentlicher Beitrag auf dem Gebiet der Gitter-Reduktionsalgorithmen ist der LLL-Algorithmus [Lenstra, Lenstra und Lov´asz, 1982] und auch die Beta-Reduktion (BKZ-Reduktion) von Gitterbasen [Schnorr, 1987, 1988, 1994] ist von großer Bedeutung. Bei Implementierungen dieser Algorithmen auf modernen Rechnerarchitekturen erfolgen viele Berechnungen aus Gründen der schnelleren Verarbeitungsgeschwindigkeit in Gleitpunktzahlen-Arithmetik. Aufgrund inhärenter Rundungsfehler kommt es dabei zu numerischen Instabilitäten. Vor [Koy und Schnorr, 2001b] gab es keine erfolgreichen Ansätze die bei der Gitterbasenreduktion auftretenden Rundungsfehler so zu kontrollieren, dass auch Gitterbasen in der Dimension >= 400 reduziert werden können. Diese Diplomarbeit beschäftigt sich mit den praktischen Aspekten der Gitterbasenreduktion in Segmenten. Dabei handelt es sich um die erstmalige Implementierung und experimentelle Evaluierung der folgenden beiden Verfahren: ....

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Bartol Filipović
URN:urn:nbn:de:hebis:30-13528
URL:http://www.mi.informatik.uni-frankfurt.de/research/mastertheses.html
Advisor:Claus Peter Schnorr
Document Type:diplomthesis
Language:German
Year of Completion:2002
Year of first Publication:2002
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Granting Institution:Johann Wolfgang Goethe-Universität
Date of final exam:2002/03/04
Release Date:2005/08/05
Last Page:148
HeBIS-PPN:185391818
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht