Lattice Basis Reduction

Kannan’s Algorithm 189

which gives

|b

1

|

m

≤



2(m−1)



(m−1)/2

det(L) ≤ (2m)

m/2

det(L).

Returning to our upp e r bound for |T | we obtain

|T | ≤

3

m

|b

1

|

m

det(L)

≤ 3

m

(2m)

m/2

= (18m)

m/2

.

Since m ≤ n this completes the proof.

11.3.3 Procedure REDUCEDBASIS

In Kannan [70, 71] this procedure is called SHORTEST. The preceding dis-

cussion provides a theoretical justification of the algorithm; some additional

explanatory comments follow. This procedure is presented in Figure 11.2.

The algorithm beg ins in step (1) by reducing the input basis using the LLL

algorithm. (The reduction par ameter can be given its standar d value α =

3

4

or any value in the range

1

4

< α < 1.) T he imp ...