Cryptography Reference
In-Depth Information
2
. Note that the
Algorithm 22 gives the Lagrange-Gauss algorithm for lattices in
Z
computation of
µ
is as an exact value in
Q
. All other arithmetic is exact integer arithmetic.
Lemma 17.1.5
Algorithm
22
terminates and outputs a Lagrange-Gauss reduced basis for
the lattice L.
Exercise 17.1.6
Prove Lemma
17.1.5
.
Example 17.1.7
We run the Lagrange-Gauss algorithm on
b
1
=
(1
,
5) and
b
2
=
(6
,
21).
In the first step,
µ
=
111
/
26
≈
4
.
27 and so we update
b
2
=
b
2
−
4
b
1
=
(2
,
1). We then
swap
b
1
and
b
2
so that the values in the loop are now
b
1
=
(2
,
1) and
b
2
=
(1
,
5). This time,
µ
=
7
/
5
=
1
.
4 and so we set
b
2
=
b
2
−
b
1
=
(
−
1
,
4). Since
b
2
>
b
1
the algorithm
halts and outputs
{
(2
,
1)
,
(
−
1
,
4)
}
.
Algorithm 22
Lagrange-Gauss lattice basis reduction
INPUT: Basis
b
1
,
b
2
∈ Z
2
for a lattice
L
OUTPUT: Basis (
b
1
,
b
2
)for
L
such that
b
i
=
λ
i
2
1:
B
1
=
b
1
2:
µ
=
b
1
,
b
2
/B
1
3:
b
2
=
b
2
−
µ
b
1
4:
B
2
=
2
5:
while
B
2
<B
1
do
6:
b
2
Swap
b
1
and
b
2
B
1
=
B
2
7:
µ
=
b
1
,
b
2
/B
1
8:
b
2
=
b
2
−
µ
b
1
9:
2
B
2
=
b
2
10:
11:
end while
12:
return
(
b
1
,
b
2
)
Exercise 17.1.8
Run the Lagrange-Gauss reduction algorithm on the basis
{
(3
,
8)
,
(5
,
14)
}
.
Lemma 17.1.9
Let
b
1
,
b
2
be the initial vectors in an iteration of the Lagrange-Gauss
algorithm and suppose
b
1
=
m
b
1
and
b
2
=
b
2
−
b
1
are the vectors that will be considered
b
1
2
<
2
/
3
, except perhaps for the last two
in the next step of the algorithm. Then
b
1
iterations.
Proof
Note that
m
=
µ
=
b
1
,
b
2
/
b
1
,
b
1
=
b
1
,
b
2
/
b
1
,
b
1
+
where
|
|≤
1
/
2.
Hence
b
1
,
b
2
−
b
1
=−
b
1
,
b
1
=
2
.
b
1
,
b
2
/
b
1
,
b
1
+
b
1
,
b
1
=−
b
1
