# 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): |

| 118 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

**BibTeX**
`@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},`

`}`