Short vectors of planar lattices via continued fractions

We show that a shortest vector of a 2-dimensional integral lattice with res pect to the l(oc)-norm can be computed with a constant number of extended-g cd computations, one common-convergent computation and a constant number of arithmetic operations. It follows that in two dimensions, a fast basis-red uction algorithm can be solely based on Schonhage's classical algorithm on the fast computation of continued fractions and the reduction algorithm of Gauss. (C) 2001 Elsevier Science B.V. All rights reserved.