Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-2000-2-001

Short vectors of planar lattices via continued fractions

Eisenbrand, Fritz

MPI-I-2000-2-001. May 2000, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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).
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
eisen.ps118 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2000-2-001
Hide details for BibTeXBibTeX
@TECHREPORT{EisenbrandMPI-I-2000-2-001,
  AUTHOR = {Eisenbrand, Fritz},
  TITLE = {Short vectors of planar lattices via continued fractions},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2000-2-001},
  MONTH = {May},
  YEAR = {2000},
  ISSN = {0946-011X},
}