ABSTRACT
In this chapter we study an algorithm for finding not merely one short vector in a lattice, but for enumerating all vectors in a lattice with length less than a given upper bound. In particular, this allows us to determine a shortest nonzero lattice vector. This algorithm was introduced by Fincke and Pohst [43] in 1985; it originated in their earlier work on algebraic number theory [42]. Before the work of Fincke and Pohst, the standard methods for calculating short vectors in a lattice relied on enumerating all vectors in a suitable box. The contribution of Fincke and Pohst was to show that it suffices to consider only those vectors in a suitable ellipsoid of much smaller volume than the box; searching through this ellipsoid is in many cases much more efficient. The two papers of Fincke and Pohst also provide a detailed analysis of the complexity of their algorithm, which will not be discussed in this chapter. Of course, the decision version of the shortest vector problem is known to be NP-complete, and so we should expect that any algorithm to find a shortest vector in a lattice will have exponential time complexity with respect to the dimension.
Suppose that B = (bij) is an n × m matrix (m ≤ n) with real entries, and suppose that B has full rank; that is, rank(B) = m. We regard the m columns b1,b2, . . . ,bm of B as a basis for the lattice L in R
