de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Short vectors of planar lattices via continued fractions

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44373

Eisenbrand,  Friedrich
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

eisen.ps
(beliebiger Volltext), 118KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Eisenbrand, F.(2000). Short vectors of planar lattices via continued fractions (MPI-I-2000-2-001). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-6567-4
Zusammenfassung
We describe how a shortest vector of a 2-dimensional integral lattice corresponds to a best approximation of a unique rational number defined by the lattice. This rational number and its best approximations can be computed with the euclidean algorithm and its speedup by Schoenhage (1971) from any basis of the lattice. The described correspondence allows, on the one hand, to reduce a basis of a 2-dimensional integral lattice with the euclidean algorithm, up to a single normalization step. On the other hand, one can use the classical result of Schoenhage (1971) to obtain a shortest vector of a 2-dimensional integral lattice with respect to the $\ell_\infty$-norm. It follows that in two dimensions, a fast basis-reduction algorithm can be solely based on Schönhage's algorithm and the reduction algorithm of Gauss (1801).