Lattice Basis Reduction

List of Figures

2.1 The Euclidean algorithm Euclid(a, b) for the greatest common

divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 The two-dimensional lattice L generated by x = [2, 0] and y =

[3, 2]. The vectors v = [0, −4] and w = [−1, 2] form another

basis of the same lattice. . . . . . . . . . . . . . . . . . . . . . 26

2.3 The Gauss ian algorithm Gauss(x, y) for a minimal basis of a

lattice in R

2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4 The centered Gaussian algorithm CGauss(x, y) . . . . . . . 32

2.5 The parameterized Gaussian algorithm PGauss[t](x, y) . . . 35

3.1 The Gram-Schmidt algorithm to compute ...