Lattice Basis Reduction

80 Lattice Basis Reduction

Proposition 4.6 (with β = 2 since α =

3

4

) gives

1

4



|x

∗

1

|

2

+ |x

∗

2

|

2

+ ··· + |x

∗

n

|

2



≤

1

4



2

n−1

+ 2

n−2

+ ··· + 1



|x

∗

n

|

2

=

1

4



2

n

− 1



|x

∗

n

|

2

< 2

n−2

|x

∗

n

|

2

.

Combining these inequalities gives

|z − y| ≤ 2

n/2−1

|x

∗

n

|. (4.12)

We now consider two cases, corresponding to whether the closest lattice vector

u ∈ L does o r doe s not belong to the translated hyperplane U + w.

Case 1 (u ∈ U +w): In this ca se u−w is the closest vector in the sublattice

L

(n−1)

to the vector z

∗

− w ∈ U. Therefor e the inductive hypothesis gives

|z

∗

− y| = |z

∗

− w − y

(n−1)

|

≤ 2

(n−1)/2

|z

∗

− w − (u − w)|

= 2

(n−1)/2

|z

∗

− u|

≤ 2

(n−1)/2

|z − u|.

Combining this with inequality (4.11) gives ...