Cryptography Reference
In-Depth Information
2
(
i
−
1)
/
2
b
i
5. By part 3 of Lemma
17.2.8
we have
b
1
≤
and so
n
n
2
(
i
−
1)
/
2
b
i
=
2
n
(
n
−
1)
/
4
det(
L
)
.
b
1
≤
i
=
1
b
i
Corollary 17.2.13
If
b
1
≤
for all
1
≤
i
≤
n then
b
1
is a correct solution to SVP.
Exercise 17.2.14
Prove Corollary
17.2.13
.
Z
m
and let
{
b
1
,...,
b
n
}
Exercise 17.2.15
Suppose
L
is a lattice in
be an LLL-reduced
≤
v
1
≤
v
2
≤···≤
v
n
basis. Rename these vectors as
v
1
,...,
v
n
such that 1
. Show
that one does not necessarily have
v
1
=
b
1
. Show that, for 1
≤
i
≤
n
v
i
≤
2
n
(
n
−
1)
/
4
det(
L
)
1
/
(
n
+
1
−
i
)
.
As a final remark, the results in this section have only given upper bounds on the
sizes of
in an LLL-reduced lattice basis. In many practical instances, one finds that
LLL-reduced lattice vectors are much shorter than these bounds might suggest.
b
i
17.3 The Gram-Schmidt algorithm
The LLL algorithm requires computing a Gram-Schmidt basis. For the complexity analysis
of the LLL algorithm it is necessary to give a more careful description and analysis of the
Gram-Schmidt algorithm than was done in Section
A.10.2
. We present pseudocode in
Algorithm
23
(the “downto” in line 4 is not necessary, but we write it that way for future
reference in the LLL algorithm).
Algorithm 23
Gram-Schmidt algorithm
INPUT:
m
{
b
1
,...,
b
n
}
in
R
b
1
,...,
b
n
}
m
OUTPUT:
{
in
R
1:
b
1
=
b
1
2:
for
i
=
2to
n
do
v
=
b
i
3:
for
j
:
=
i
−
1downto1
do
4:
b
i
,
b
j
b
j
,
b
j
µ
i,j
=
/
5:
µ
i,j
b
j
v
=
v
−
6:
end for
7:
b
i
=
v
8:
9:
end for
10:
return
b
1
,...,
b
n
}
{
