Lattice Basis Reduction

The Hermite Normal Form 241

the bottom rig ht corner), and in fact the reduce and exchange steps pe rformed

by the LLL algorithm also settle down to the s ame sequence of operatio ns .

Our next task is to identify this limiting sequence of operations, and per fo rm

them not on the matrix C

γ

but instead on the matrix



I

m

V



. In this way,

we will achieve the same result but without the complications introduced by

multiplying the input vector V by an arbitrarily large integer γ.

Recall tha t we are g iven an input vector

V =



v

1

v

2

··· v

m



t

.

We define the (m−1)-dimensional lattice Λ ⊂ Z

m

as follows:

Λ = {X ∈ Z

m

| V

t

X = 0 }.

For each positive integer γ, we define the m-dimensio nal lattice L

γ

⊂ Z

m+1

to

be the lattice spa nned by the (transp oses of the) rows of the