Cryptography Reference
In-Depth Information
b
i
−
i
−
1
k
=
j
µ
i,k
b
k
in line 6 of Algorithm
23
during
=
Exercise 17.3.3
Consider the vector
v
iteration
j
. Show that
i
−
1
2
2
µ
i,k
b
k
2
.
v
=
b
i
−
k
=
j
m
throughout the loop in line 4 of the algorithm.
Deduce that
v
≤
b
i
and that
d
i
−
1
v
∈ Z
m
. Let X
2
Theorem 17.3.4
Let
b
1
,...,
b
n
be vectors in
Z
∈ Z
≥
2
be such that
b
i
≤
X for
n. Then the Gram-Schmidt algorithm performs O
(
n
4
m
log(
X
)
2
)
bit operations.
The output size is O
(
n
2
m
log(
X
))
.
1
≤
i
≤
arithmetic for the vectors
b
i
. Lemma
17.3.2
Q
Proof
One runs Algorithm
23
using exact
shows that the denominators in
b
i
are all factors of
d
i
−
1
, which has size
i
−
1
j
=
1
B
j
≤
i
−
1
j
=
1
X
, so the numerators are bounded by
X
i
.The
size of each vector
b
i
and, by Exercise
17.3.3
, the intermediate steps
v
in the computation
are therefore
O
(
mi
log(
X
)) bits, which gives the output size of the algorithm. The compu-
tation
2
X
i
−
1
.Also,
b
i
≤
b
j
≤
b
i
≤
b
i
,
b
j
requires
O
(
mn
log(
X
)
2
) bit operations and the computation
b
j
,
b
j
requires
O
(
mn
2
log(
X
)
2
) bit operations. As there are
O
(
n
2
) vector operations to perform, one gets
the stated running time.
m
Corollary 17.3.5
Let the notation be as in Theorem
17.3.4
and let L be the lattice in
Z
. Then one can compute
det(
L
)
2
in O
(
n
4
m
log(
X
)
2
)
bit operations.
3
with basis
{
b
1
,...,
b
n
}
=
i
=
1
b
i
2
. One computes
b
i
using exact (naive)
Proof
Lemma
16.1.14
implies det(
L
)
2
b
i
in
O
(
n
4
m
log(
X
)
2
) bit operations. One computes each
2
arithmetic over
Q
∈ Q
in
b
i
b
i
b
i
O
(
mn
2
log(
X
)
2
) bit operations. Since
2
≤
X
and
d
i
−
1
2
∈ Z
2
it follows that
b
i
is a ratio of integers bounded by
X
n
. One computes the product of the
2
in
O
(
n
3
log(
X
)
2
)
bit operations (since the integers in the product are bounded by
X
n
2
). Finally, one can reduce
the fraction using Euclid's algorithm and division in
O
(
n
4
log(
X
)
2
) bit operations.
17.4 The LLL algorithm
The Lenstra-Lenstra-Lovasz (LLL) algorithm is an iterative algorithm that transforms
a given lattice basis into an LLL-reduced one. Since the definition of LLL-reduced uses
Gram-Schmidt vectors, the algorithm performs the Gram-Schmidt method as a subroutine.
The first condition of Definition
17.2.4
is easily met by taking suitable integer linear
combinations. If the second condition is not met then
b
i
is not significantly longer than
b
i
−
1
.
In this case, we swap
b
i
and
b
i
−
1
and backtrack. The swapping of vectors is familiar from
the Lagrange-Gauss two-dimensional lattice basis reduction algorithm and also Euclid's
algorithm. We give the precise details in Algorithm
24
.
3
Since det(
L
)
2
∈ Z
while det(
L
) may not be rational if
n<m
, we prefer to work with det(
L
)
2
.
