Next: Lattice Basis Reduction Algorithms
Up: Introduction
Previous: Point Lattices
Reduced Lattice Bases
Any lattice L may be described by many different lattice bases. Let
be distinct sets of vectors, all of which form bases
of lattice L. We can imagine that there exists some ordering or
ranking of the bases B_{i}, and thus one or more of the B_{i} might be
considered ``good'' lattice bases of L. Lattice reduction
theory deals with identifying ``good'' lattice bases for a particular
lattice. If we are given a basis B which describes L, we would like
to reduce B to basis B', also describing L, where B' is
a ``good'' lattice basis in the sense of some reduction theory.
There are two classical lattice reduction theories, one due to Korkin
and Zolotarev [23,24] and one due to Minkowski [29].
A basis
of lattice L is
said to be Minkowskireduced if
 1.

is the shortest nonzero vector in L.
 2.
 For
,
is the shortest vector in L
such that
may be extended to a
basis of L.
Minkowskireduced lattice bases always contain the shortest nonzero
vector in the lattice. Subsequent basis vectors
are selected
by choosing the shortest lattice vector in L which is not a linear
combination of the already selected basis vectors
.
If
,
then it would be impossible to extend
(
)
to be a basis of L.
The definition of KorkinZolotarev reduction is similar to that
of Minkowski. We say a basis
is
KorkinZolotarev reduced if it satisfies the following three conditions:
 1.

is the shortest nonzero vector in L.
 2.
 For
,
let S_{i} be the (i1)dimension
subspace spanned by the basis
.
Let
be the
orthogonal complement of S_{i} in
.
Finally, let P_{i}(L)
denote the orthogonal projection of L onto .
Then
choose
such that
is the shortest
nonzero vector in P_{i}(L).
 3.
 Size reduction condition. For
,
where
.
In the definition of Minkowski reduction, successive basis vectors
are added to the lattice basis only if
is the
shortest vector in the lattice which will allow the basis to be
extended. In KorkinZolotarev reduction, though, successive basis
vectors
are chosen based on their length in the orthogonal
complement of the space spanned by the previous basis vectors
.
Depending on the specific problem, we may find either, both, or neither
of the above definitions of ``good'' lattice bases is sufficient.
Certainly if the goal is to find the shortest nonzero vector in the
lattice, as is the case with subset sum problems (see
Chapter 3), we could use either Minkowski reduction or
KorkinZolotarev reduction as a measure of how ``good'' a particular
lattice basis is. If the item of interest involves multiple vectors in
the lattice, one definition may be preferred over the other for that
particular application.
Next: Lattice Basis Reduction Algorithms
Up: Introduction
Previous: Point Lattices
Brian A. LaMacchia
19991030