Lattice Basis Reduction

184 Lattice Basis Reduction

(1) For 2 ≤ j ≤ n we have a

j

(j) = Λ

1

(L

j

(a

1

, a

2

, . . . , a

n

)). In terms

of the lower triangular r e presentation of a

1

, a

2

, . . . , a

n

as in Lemma

11.6, this means that for j ≥ 2 , the j-th diagonal entry is the length

of the shortest vector in the lattice generated by the rows of the

lower r ight (n−j+1) × (n−j+1) block.

(2) |a

1

|

2

≤

4

3

|a

2

|

2

.

(3) |a

2

(1)|

2

≤

1

4

|a

1

|

2

; recall that a

2

(1) is the component of a

2

par-

allel to a

1

.

It follows from these conditions that

|a

1

|

2

≤ 2n



det(L)

2/n



,

where det(L) is the determinant of the lattice L. If we compare this with the

inequality achieved by the LLL algorithm in polynomial time, namely

|a

1

|

2