Lattice Basis Reduction

46 Lattice Basis Reduction

The k-th Gram determinant of this basis is

d

k

= det(G

k

).

For convenience we set d

0

= 1. If x

i

∈ Z

n

for all i then d

k

∈ Z for 0 ≤ k ≤ n.

This fact will be important later in our analysis of the LLL algorithm.

Propositio n 3.8. Let x

1

, . . ., x

n

be a basis of R

n

, and let x

∗

1

, . . ., x

∗

n

be its

Gram-Schmidt orthogonalization. For 1 ≤ k ≤ n the k-th Gram determinant

of the basis is the product of the square-lengths of the GSO vectors:

d

k

=

k

Y

i=1

|x

∗

i

|

2

.

Proof. By Remark 3.2 we can express the Gram-Schmidt orthogonalization

as the matrix equation X = MX

∗

. Let M

k

be the upper left k ×k submatrix

of M, and le t X

∗

k

be the k ×n matrix cons isting ...