Lattice basis reduction - Mathematics of Public Key Cryptography - page 360

Lemma 17.4.3 If b k and b k − 1 are swapped then the Gram-Schmidt vectors b i for 1 ≤ i ≤ n

are changed as follows:

1 and k<i<n, b i is unchanged.
2. The new value for b k − 1 is b k +

1. For 1 ≤ i<k −

µ k,k − 1 b k − 1 and the new value for B k − 1 is B k = B k +

µ k,k − 1 B k − 1 .
3. The new value for b k is ( B k /B k − 1 ) b k − 1 − ( µ k,k − 1 B k − 1 /B k − 1 ) b k and the new value for

B k is B k − 1 B k /B k − 1 .
Proof Denote by b i the new basis (i.e., b k − 1 = b k − 1 ), b i ∗ and µ i,j the new

Gram-Schmidt values and B i the squares of the lengths of the b i ∗ . Clearly, b i ∗ =

b k and b k =

b i for

1 and µ i,j = 1 ≤ i<k − µ i,j for 1 ≤ j<i<k − 1. Now

k − 2

µ k − 1 ,j b j ∗

b k − 1 = b k − 1 −

j = 1

k − 2

µ k,j b j = b k −

j = 1

b k + µ k,k − 1 b k − 1 .

=

Hence, B k − 1 = µ k,k − 1 B k − 1 . B k +

Similarly

k − 1

b k ∗ = µ k,j b j ∗ b k −

j = 1

k − 2

−

/B k − 1 b k − 1 µ k − 1 ,j b j b k − 1 , b k − 1

=

b k − 1 −

j = 1

b k − 1 − /B k − 1 ( b k +

b k − 1 , b k + µ k,k − 1 b k − 1 µ k,k − 1 b k − 1 ) =

b k − 1 − µ k,k − 1 B k − 1 /B k − 1 ( b k + µ k,k − 1 b k − 1 )

=

µ k,k − 1 B k − 1 /B k − 1 b k − 1 − µ k,k − 1 B k − 1 /B k − 1 b k .
The result for b k ∗ follows since 1

= 1 −

µ k,k − 1 B k − 1 /B k − 1 = B k /B k − 1 . Finally −

/B k − 1 2 /B k − 1 2 B k = ( B k b k − 1 , b k − 1 µ k,k − 1 B k − 1 b k , b k B k − 1 B k /B k − 1 .

+ =

Exercise 17.4.4 Give explicit formulae for updating the other Gram-Schmidt values in
lines 7 and 13 of Algorithm 24 .

Exercise 17.4.5 Show that the condition in line 9 of Algorithm 24 can be checked imme-
diately after µ k,k − 1 has been computed. Hence, show that the cases 1

≤ j<k − 1inthe

loop in lines 5 to 8 of Algorithm 24 can be postponed to line 10.

Lemma 17.4.6 If the LLL algorithm terminates then the output basis is LLL-reduced.