Cryptography Reference
In-Depth Information
b
1
2
<
2
/
3 unless we are in the last two iterations of the algorithm.
We show that
b
1
b
1
2
2
/
3. Then
To do this, suppose that
≥
b
1
b
1
,
b
2
| = |
b
1
,
b
1
| = |
2
1
2
3
b
1
2
.
|
|
b
1
≤
2
b
1
≤
2
It follows that, in the next iteration of the algorithm, we will be taking
m
=
µ
∈{−
1
,
0
,
1
}
and so the next iteration would, at most, replace
b
1
with
b
2
±
b
1
=
b
1
±
(
b
2
−
m
b
1
). But,
if this were smaller than
b
1
then we would have already computed
b
1
differently in the
current iteration. Hence, the next step is the final iteration.
2
such that
2
Theorem 17.1.10
Let X
∈ Z
≥
2
and let
b
1
,
b
2
be vectors in
Z
b
i
≤
X. Then
the Lagrange-Gauss algorithm performs O
(log(
X
)
3
)
bit operations.
Proof
Lemma
17.1.9
shows that there are
O
(log(
X
)) iterations in the Lagrange-Gauss
algorithm. Since the squared Euclidean lengths of all vectors in
th
e algorithm are bounded
by
X
, it follows that entries of vectors are integers bounded by
√
X
. Similarly, the numerator
and denominator of
µ
∈ Q
require
O
(log(
X
)) bits. The result follows.
A much more precise analysis of the Lagrange-Gauss reduction algorithm is given by
Va l l ee [
551
]. Indeed, the algorithm has complexity
O
(log(
X
)
2
) bit operations; see Nguyen
and Stehl´e[
408
].
The above discussion is for the Euclidean norm, but the Lagrange-Gauss reduction
algorithm can be performed for any norm (the only change is how one computes
µ
). We
refer to Kaib and Schnorr [
292
] for analysis and details.
Finally, we remark that there is a natural analogue of Definition
17.1.1
for any dimension.
Hence, it is natural to try to generalise the Lagrange-Gauss algorithm to higher dimensions.
Generalisations to dimension three have been given by Vallee [
550
] and Semaev [
485
].
There are a number of problems when generalising to higher dimensions. For example,
choosing the right linear combination to size reduce
b
n
using
b
1
,...,
b
n
−
1
is solving the
CVP in a sublattice (which is a hard problem). Furthermore, there is no guarantee that the
resulting basis actually has good properties in high dimension. We refer to Nguyen and
Stehl´e[
413
] for a full discussion of these issues and an algorithm that works in dimensions
3 and 4.
17.1.1 Connection between Lagrange-Gauss reduction and Euclid's algorithm
The Lagrange-Gauss algorithm is closely related to Euclid's algorithm. We briefly discuss
some similarities and differences. Recall that if
a,b
then Euclid's algorithm (using
signed remainders) produces a sequence of integers
r
i
,s
i
,t
i
such that
∈ Z
as
i
+
bt
i
=
r
i
where
|
r
i
t
i
|
<
|
a
|
and
|
r
i
s
i
|
<
|
b
|
. The precise formulae are
r
i
+
1
=
r
i
−
1
−
qr
i
and
s
i
+
1
=
s
i
−
1
−
qs
i
where
q
=
r
i
−
1
/r
i
. The sequence
|
r
i
|
is strictly decreasing. The initial values
are
r
−
1
=
a,r
0
=
b,s
−
1
=
1
,s
0
=
0
,t
−
1
=
0
,t
0
=
1. In other words, the lattice with basis
