Cryptography Reference
In-Depth Information
without making any changes. We have
B
1
=
1 and
B
2
=
4. Consider now
k
=
3again.We
µ
3
,
2
)
B
2
=
have
µ
3
,
2
=
µ
3
,
1
=
0 and so
b
3
remains unchanged. Finally,
B
3
=
9
>
(3
/
4
−
3
and so we set
k
=
4 and halt.
Exercise 17.4.9
Perform the LLL algorithm by hand on the basis
{
(
−
1
,
5
,
0)
,
(2
,
5
,
0)
,
(8
,
6
,
16)
}
.
Exercise 17.4.10
Perform the LLL algorithm by hand on the basis
{
}
(0
,
3
,
4)
,
(
−
1
,
3
,
3)
,
(5
,
4
,
−
7)
.
2
(
n
−
1)
/
2
λ
1
. In other
words, the LLL algorithm solves SVP up to an exponential factor, but is not guaranteed to
output a shortest vector in the lattice. Hence, LLL does not officially solve SVP.
In practice, at least for relatively small dimensions, the vector
b
1
output by the LLL
algorithm is often much closer to the shortest vector than this bound would suggest, and in
many cases will be a shortest vector in the lattice. In Example
17.4.8
, the theoretical bound
gives
Remark 17.4.11
Part 1 of Theorem
17.2.12
shows we have
b
1
≤
b
1
≤
2, so (0
,
2
,
0) would have been a possible value for
b
1
.
17.5 Complexity of LLL
We now show that the LLL algorithm terminates and runs in polynomial-time. The original
paper of Lenstra, Lenstra and Lovasz [
335
] proves polynomial termination for any lattice
in
m
but only gives a precise complexity for lattices in
m
.
R
Z
m
with basis
b
1
,...,
b
n
and let X
Theorem 17.5.1
Let L be a lattice in
Z
∈ Z
≥
2
be such
2
that
n. Let
1
/
4
<δ<
1
. Then the LLL algorithm with factor δ
terminates and performs O
(
n
2
log(
X
))
iterations.
b
i
≤
X for
1
≤
i
≤
Proof
We need to bound the number of “backtracks” in Algorithm
24
. This number is
at most
n
plus the number of swaps. So it suffices to bound the number of swaps by
O
(
n
2
log(
X
)).
For 1
≤
i
≤
n
−
1 define the
i
×
m
matrix
B
(
i
)
formed by the first
i
basis vectors for the
det(
B
(
i
)
B
(
i
)
)
lattice. Define
d
i
=
∈ Z
, which is the square of the volume of the sublattice
generated by the rows of
B
(
i
)
. Hence
i
i
i
j
=
1
j
=
1
b
i
2
2
X
i
.
d
i
=
B
j
=
≤
b
i
≤
j
=
1
Define
n
−
1
n
−
1
B
n
−
i
i
D
=
d
i
=
.
i
=
1
i
=
1
X
(
n
−
1)
n/
2
.
It follows that
D
≤
