Cryptography Reference
In-Depth Information
2
Definition 17.1.1
An ordered basis
b
1
,
b
2
for
R
is
Lagrange-Gauss reduced
if
b
1
≤
b
2
≤
b
2
+
q
b
1
for all
q
∈ Z
.
The following theorem shows that the vectors in a Lagrange-Gauss reduced basis are as
short as possible. This result holds for any norm, though the algorithm presented below is
only for the Euclidean norm.
Theorem 17.1.2
Let λ
1
,λ
2
be the successive minima of L.IfL has an ordered basis
{
b
1
,
b
2
}
that is Lagrange-Gauss reduced then
b
i
=
λ
i
for i
=
1
,
2
.
Proof
By definition we have
b
2
+
q
b
1
≥
b
2
≥
b
1
for all
q
∈ Z
.
Let
v
=
l
1
b
1
+
l
2
b
2
be any non-zero point in
L
.If
l
2
=
0 then
v
≥
b
1
.If
l
2
=
0
then write
l
1
=
ql
2
+
r
with
q,r
∈ Z
such that 0
≤
r<
|
l
2
|
. Then
v
=
r
b
1
+
l
2
(
b
2
+
q
b
1
)
and, by the triangle inequality
b
2
+
q
b
1
−
v
≥|
l
2
|
r
b
1
=
(
|
l
2
|−
r
)
b
2
+
q
b
1
+
r
(
b
2
+
q
b
1
−
b
1
)
≥
b
2
+
q
b
1
≥
b
2
≥
b
1
.
This completes the proof.
n
. We write
2
B
i
=
2
Definition 17.1.3
Let
b
1
,...,
b
n
be a list of vectors in
R
b
i
=
b
i
,
b
i
.
A crucial ingredient for the Lagrange-Gauss algorithm is that
2
µ
2
B
1
b
2
−
µ
b
1
=
B
2
−
2
µ
b
1
,
b
2
+
(17.1)
is minimised at
µ
/B
1
(to see this, note that the graph as a function of
µ
is a
parabola and that the minimum can be found by differentiating with respect to
µ
). Since
we are working in a lattice we therefore replace
b
2
by
b
2
−
=
b
1
,
b
2
is the nearest
integer to
µ
. Hence, lines 3 and 9 of Algorithm
22
reduce the size of
b
2
as much as possible
using
b
1
. In the one-dimensional case, the formula
b
2
−
µ
b
1
where
µ
µ
b
1
is the familiar operation
r
i
+
1
=
r
i
−
1
−
r
i
−
1
/r
i
r
i
from Euclid's algorithm.
Lemma 17.1.4
An ordered basis
{
b
1
,
b
2
}
is Lagrange-Gauss reduced if and only if
b
1
≤
b
2
≤
b
2
±
b
1
.
Proof
The forward implication is trivial. For the converse, suppose
b
2
≤
b
2
±
b
1
.
2
We use the fact that the graph of
F
(
µ
)
=
b
2
+
µ
b
1
is a parabola. It follows that the
miniumum of
F
(
µ
)istakenfor
−
1
<µ<
1. Hence,
b
2
≤
b
2
+
q
b
1
for
q
∈ Z
such
that
|
q
|
>
1.
2
The reader is warned that the notation
B
i
will have a different meaning when we are discussing the LLL algorithm.
