Cryptography Reference
In-Depth Information
µ
k,k
−
1
)
B
k
−
1
. By Lemma
17.4.3
,
Two vectors
b
k
and
b
k
−
1
are swapped when
B
k
<
(
δ
−
the new values for
B
k
−
1
and
B
k
are
B
k
−
1
=
µ
k,k
−
1
B
k
−
1
and
B
k
=
B
k
−
1
B
k
/B
k
−
1
.Let
B
k
+
d
i
be the new values for the
d
i
.Wehave
d
i
=
d
i
when 1
≤
i<k
−
1. By the Lovasz
condition
B
k
−
1
≤
δB
k
−
1
. Hence,
d
k
−
1
≤
δd
k
−
1
. Finally, since
B
k
−
1
B
k
=
B
k
−
1
B
k
we have
d
i
=
n
. Hence, swapping
b
k
and
b
k
−
1
always strictly reduces
D
.
On the other hand, we always have
4
d
i
∈ Z
d
i
for
k
≤
i
≤
and so
D
≥
1. It follows that the number
of swaps in the LLL algorithm is at most
5
log
δ
(
X
(
n
−
1)
n/
2
)
O
(
n
2
log(
X
)). Hence, the
=
algorithm requires
O
(
n
2
log(
X
)) iterations of the main loop.
Algorithm
24
and Theorem
17.5.1
provide a proof that an LLL-reduced basis exists for
every lattice.
2
(
n
−
1)
/
4
(this bound
Exercise 17.5.2
Let
n
∈ N
. Show that Hermite's constant satisfies
γ
n
≤
can be improved to (4
/
3)
(
n
−
1)
/
2
;see[
335
]).
m
then LLL can be implemented using exact
arithmetic, and
hence exact integer arithmetic. But we need to show that the size of the integers does
not explode. The analysis given already for the Gram-Schmidt algorithm (for example,
Lemma
17.3.2
) provides most of the tools we need.
It is clear that if
L
⊂ Z
Q
Z
m
with basis
b
1
,...,
b
n
and let X
∈ Z
≥
2
be such
Theorem 17.5.3
Let L be a lattice in
that
b
i
2
≤
X for
1
≤
i
≤
n. Then the LLL algorithm requires arithmetic operations on
integers of size O
(
n
log(
X
))
.
Proof
(Sketch) The bounds on the sizes of the
b
i
follow the same methods as used in the
proof of Theorem
17.3.4
. Since
b
i
is never increased during the algorithm (indeed, the
vectors are specifically permuted to reduce the
b
i
b
i
≤
X
1
/
2
)wehave
at the end of
each iteration. Since
d
i
−
1
b
i
∈ Z
X
i
−
1
it follows that the entries of
b
i
can be
n
and
|
d
i
−
1
|≤
written as
n
i,j
/d
i
−
1
where
n
i,j
|≤
X
i
.
|
2
at the end of each iteration. These values all start
bounded by
X
. As the algorithm proceeds, the values are either not yet changed (and hence
still bounded by
X
) or have been modified so that the Gram-Schmidt basis is size reduced
(and possibly swapped to an earlier position in the list of vectors). After each size reduction
step (and before swapping) we have
Let us now consider the values
b
i
i
−
1
b
i
+
µ
i,j
b
j
b
i
=
j
=
1
with
−
1
/
2
≤
µ
i,j
≤
1
/
2 and so
i
−
1
2
b
i
2
µ
i,j
b
j
2
b
i
=
+
≤
nX.
(17.2)
j
=
1
4
To apply this argument it is necessary to use the square of the determinant. An integer lattice that does not have full rank does
not necessarily have integer determinant.
5
Recall that 1
/
4
<δ<
1 is considered as a fixed constant.
