Lattice Basis Reduction

Gram-Schmidt Orthogonalization 51

“unhatted” vectors:

b

x

∗

j+1

=

|x

∗

j+1

|

2

|x

∗

j+1

|

2

+ µ

2

j+1,j

|x

∗

j

|

2

x

∗

j

− µ

j+1,j

|x

∗

j

|

2

|x

∗

j+1

|

2

+ µ

2

j+1,j

|x

∗

j

|

2

x

∗

j+1

.

The next result connects Gram-Schmidt orthogonalization with short vec tors

in lattices: it gives a lower bound for the length of a nonzero lattice vector in

terms of the Gram-Schmidt orthogonalizatio n of the lattice basis.

Propositio n 3.14. Let x

1

, x

2

, . . . , x

n

be a basis of R

n

, and let x

∗

1

, x

∗

2

, . . . ,

x

∗

n

be its Gram-Schmidt orthogonalization. Let L be the lattice generated by

x

1

, x

2

, . . . , x

n

. For any nonzero y ∈ L we have

|y| ≥ min



|x

∗

1

|, |x

∗

2

|, . . . , |x

∗

n

|



.

That is, any nonzero lattice vector is at