Cryptography Reference
In-Depth Information
the standard way to implement this algorithm is using floating-point
arithmetic. However, problems can arise (especially if the
b
i
decrease quickly in size).
Such issues are beyond the scope of this topic; we refer to Higham [
259
] for details.
If the input vectors lie in
When working in
R
m
then one can perform Algorithm
23
using exact arithmetic
Z
over
. However, the integers can become very large (this is called
coefficient explosion
).
We now analyse the size of the integers and prove the complexity of the exact version of the
Gram-Schmidt algorithm. These results are used later when determining the complexity
of LLL.
Q
m
. Define
B
i
=
b
i
2
(as
Definition 17.3.1
Let
b
1
,...,
b
n
be an ordered set of vectors in
Z
before). For 1
≤
i
≤
n
−
1 define the
i
×
m
matrix
B
(
i
)
whose rows are
b
1
,...,
b
i
. Define
d
0
=
0 and, for 1
≤
i
≤
n
det(
B
(
i
)
B
(
i
)
)
d
i
=
=
det(
b
j
,
b
k
1
≤
j,k
≤
i
)
∈ Z
,
which is the square of the volume of the sublattice generated by
B
(
i
)
.
Lemma 17.3.2
Let the notation be as above.
1. d
i
=
i
j
=
1
B
j
for
1
≤
i
≤
n.
2. B
i
=
d
i
/d
i
−
1
for
1
≤
i
≤
n.
3. d
i
−
1
b
i
∈
n
for
1
L
⊆ Z
≤
i
≤
n, where L is the lattice spanned by
{
b
1
,...,
b
n
}
.
4. d
j
µ
i,j
∈ Z
for
1
≤
j<i
≤
n.
Proof
1. Write
L
(
i
)
for the lattice spanned by the first
i
vectors (i.e.,
L
is given by the matrix
B
(
i
)
). Then
d
i
=
=
i
j
=
1
B
j
by Lemma
16.1.14
.
2. This property follows immediately from the previous one.
3. Write
b
i
=
=
i
j
=
1
det(
L
(
i
)
)
2
b
j
2
b
i
−
i
−
1
. Note that the sum is over vectors
b
j
not
b
j
,sothe
a
i,j
are not the same as the
µ
i,j
. Since
1
a
i,j
b
j
for some
a
i,j
∈ R
j
=
b
l
,
b
i
=
0for1
≤
l<i
we have
i
−
1
b
l
,
b
i
=
a
i,j
b
l
,
b
j
,
j
=
1
which corresponds to the matrix product
(
a
i,
1
,...,a
i,i
−
1
)
B
(
i
−
1)
B
(
i
−
1)
.
(
b
i
,
b
1
,...,
b
i
,
b
i
−
1
)
=
. It follows that
d
i
−
1
b
i
∈
Inverting
B
(
i
−
1)
B
(
i
−
1)
to solve for the
a
i,j
gives
d
i
−
1
a
i,j
∈ Z
n
as required.
4. By the previous results we have
d
j
µ
i,j
=
L
⊂ Z
b
i
,
b
j
b
i
,d
j
−
1
b
j
∈Z
d
j
−
1
B
j
/B
j
=
.
