MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2017

2. Number - only D2

MPI-I-2000-2-001

Short vectors of planar lattices via continued fractions

Eisenbrand, Fritz

May 2000, 10 pages.

.
Status: available - back from printing

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).

  • eisen.ps
  • Attachement: eisen.ps (118 KBytes)

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},
}