Lattice Basis Reduction

The Hermite Normal Form 231

Applying the LLL algorithm (α = 3/4) to the rows of V gives the following

matrix U

2

containing a reduced bas is for N(A):

U

2

=





3 1 −6 3 −3 −6

7 −2 −1 −6 2 −6

5 −4 0 8 5 5





We write U

1

for the matrix formed by the first three rows of U :

U

1

=





0 0 −111 317 −28 72

0 0 32 −92 8 −21

0 0 −4 12 −1 3





We stack U

2

on top of U

2

to obtain the matrix F :

F =



U

2

U

1



=

















3 1 −6 3 −3 −6

7 −2 −1 −6 2 −6

5 −4 0 8 5 5

0 0 −111 317 −28 72

0 0 32 −9 2 8 −21

0 0 −4 12 −1 3

















We compute the Gram-Schmidt ortho gonalization of the rows of F . We use

procedure reduce from the LLL algorithm to size-reduce the bottom three

rows of F using the top three ...