Cryptography Reference
In-Depth Information
Algorithm 24
LLL algorithm with Euclidean norm (typically, choose
δ
=
3
/
4)
m
.
OUTPUT: LLL reduced basis
b
1
,...,
b
n
1:
Compute the Gram-Schmidt basis
b
1
,...,
b
n
and coefficients
µ
i,j
for 1
INPUT:
b
1
,...,
b
n
∈ Z
≤
j<i
≤
n
b
i
,
b
i
=
b
i
2
2:
Compute
B
i
=
for 1
≤
i
≤
n
3:
k
2
4:
while
k
=
≤
n
do
for
j
=
(
k
−
1) downto 1
do
Perform size reduction
5:
Let
q
j
=
µ
k,j
and set
b
k
=
b
k
−
q
j
b
j
6:
Update the values
µ
k,j
for 1
≤
j<k
7:
end for
8:
if
B
k
≥
−
µ
k,k
−
1
)
B
k
−
1
then
Check Lovasz condition
(
δ
9:
k
=
k
+
1
10:
else
11:
Swap
b
k
with
b
k
−
1
12:
Update the values
b
k
,
b
k
−
1
,
B
k
,
B
k
−
1
,
µ
k
−
1
,j
and
µ
k,j
for 1
≤
j<k
, and
13:
µ
i,k
,µ
i,k
−
1
for
k<i
≤
n
k
=
max
{
2
,k
−
1
}
14:
15:
end if
16:
end while
Lemma 17.4.1
Throughout the LLL algorithm the values
b
i
and B
i
for
1
≤
i
≤
n and µ
i,j
for
1
≤
j<i
≤
n are all correct Gram-Schmidt values.
Exercise 17.4.2
Prove Lemma
17.4.1
. In other words, show that line 6 of the LLL algorithm
does not change
b
i
or
B
i
for 1
n
. Similarly, line 12 of the algorithm does not change
any values except those mentioned in line 13.
≤
i
≤
It is illuminating to compare the LLL algorithm with the Lagrange-Gauss reduction
algorithm. The basic concept of size reduction followed by a swap is the same; there are,
however, two crucial differences.
1. The size reduction operation in the Lagrange-Gauss algorithm gives the minimal value
for
. In LLL, the coefficient
µ
k,j
is chosen to depend on
b
k
and
b
j
so it does not necessarily minimise
b
2
+
q
b
1
over
q
∈ Z
can grow during the algorithm.
Of course, in the two-dimensional case of LLL then
µ
2
,
1
is the same as the value used
in the Lagrange-Gauss algorithm and so the size reduction step is the same.
2. The size check in LLL (the Lovasz condition) is on the lengths of the Gram-Schmidt
vectors, unlike the size check in the Lagrange-Gauss algorithm, which is on the length
of the basis vectors themselves.
b
k
. Indeed,
b
k
These features of LLL may seem counterintuitive, but they are essential to the proof that
the algorithm runs in polynomial-time.
