Cryptography Reference
In-Depth Information
17.6 Variants of the LLL algorithm
There are many refinements of the LLL algorithm that are beyond the scope of the brief
summary in this topic. We list some of these now.
As mentioned earlier, it is necessary to use floating-point arithmetic to obtain a fast
version of the LLL algorithm. A variant of floating-point LLL whose running time grows
quadratically in log(
X
) (rather than cubicly, as usual) is the L
2
algorithm of Nguyen and
Stehl´e[
407
] (also see Stehl´e[
523
]).
Schnorr-Euchner “deep insertions”. The idea is that, rather than just swapping
b
k
and
b
k
−
1
in the LLL algorithm, one can move
b
k
much earlier in the list of vectors if
B
k
is
sufficiently small. With standard LLL we have shown that swapping
b
k
and
b
k
−
1
changes
B
k
to
B
k
+
µ
k,k
−
1
B
k
−
1
. A similar argument shows that inserting
b
k
between
b
i
−
1
and
b
i
for some 1
<i<k
changes
B
k
to
k
−
1
µ
k,j
B
j
.
B
=
B
k
+
j
=
1
Hence, one can let
i
be the smallest index such that
B<
4
B
i
and insert
b
k
between
b
i
−
1
and
b
i
(i.e., reorder the vectors
b
i
,...,
b
k
as
b
k
,
b
i
,...,
b
k
−
1
). We refer to Schnorr and
Euchner [
473
] and Section 2.6.2 of Cohen [
127
] for more details.
Our presentation of the LLL algorithm was for the Euclidean norm. The algorithm has
been extended to work with any norm by Lovasz and Scarf [
357
] (also see Kaib and
Ritter [
291
]).
In practice, if one wants results for a norm other than the Euclidean norm, one usually
performs ordinary LLL reduction with respect to the Euclidean norm and then uses
the standard relations between norms (Lemma
A.10.2
) to determine the quality of the
resulting vectors.
Another important approach to lattice basis reduction is the block Korkine-Zolotarev
algorithm due to Schnorr [
468
]. We mention this further in Section
18.5
.
