ABSTRACT
In this chapter we introduce the simplest case of lattice basis reduction: a lattice in the plane generated by two linearly independent vectors. The algorithm we discuss goes back to Legendre and Gauss in the 19th century. (Scharlau and Opolka [122] provide a very useful history of developments in this area.) This algorithm has a striking resemblance to the classical Euclidean algorithm for computing the greatest common divisor (GCD) of two integers.
