In this chapter we present the algorithm of Kannan [70, 71] which finds a lattice basis which is reduced in the strong sense of Definition 11.9 below; in particular, the first vector in the basis is a shortest (nonzero) lattice vector.
We recall the Gram-Schmidt orthogonalization process , and introduce some further notation. Suppose that the vectors b1,b2, . . . ,bn ∈ Rn form a basis of the lattice L. The orthogonal vectors b∗1,b