Lattice Basis Reduction

The LLL Algorithm 75

Theorem 4.22. For a fi xed value of the parameter α, the number of times

the LLL algorithm passes through the loop in Step (4) is O(n

2

log B), and the

number of arithmetic operations performed by the algorithm is O(n

4

log B).

Proof. The first claim follows immediately from Theorem 4.19. For the second

claim, we observe that

• The initial computation of the Gram-Schmidt orthogonalization in Step (2)

requires O(n

3

) arithmetic op e rations.

• The initial reduction in Step (4)(a) requires O(n) operations, the k−2 reduc-

tions in Step (4)(b)(i) require O(n

2

) operatio ns, and the exchange in Step

(4)(b)(iii) requires O(n) operations. Thus