Cryptography Reference
In-Depth Information
Exercise 17.4.7
Prove Lemma
17.4.6
. Indeed, the fact that the Lovasz conditions are
satisfied is immediate. Prove the bounds on the
µ
i,j
using the three following steps. Let
1
j<k
and let
b
k
=
≤
b
k
−
µ
k,j
b
j
.
b
j
,b
j
=
b
j
,b
j
b
j
,b
i
=
1. Prove that
and
0if
j<i
.
2. Hence, writing
µ
k,j
=
b
k
,b
j
b
j
,b
j
µ
k,j
|≤
/
, prove that
|
1
/
2for1
≤
j<k
.
3. For
j<i<k
denote
µ
k,i
=
b
k
,b
i
b
i
,b
i
. Prove that
µ
k,i
=
/
µ
k,i
.
In the next section we show that the LLL algorithm does terminate. Before then we give
an example and some further discussion.
Example 17.4.8
Let
L
be the lattice with basis matrix
10 0
42 5
00 3
.
B
=
We will perform the LLL algorithm to reduce this lattice basis.
We start with
k
=
2 and compute
µ
2
,
1
=
4
/
1
=
4. So
q
1
=
4 and we define
b
2
=
b
2
−
4
b
1
=
(4
,
2
,
15)
−
(4
,
0
,
0)
=
(0
,
2
,
15)
.
We now want to check the second LLL condition. To do this we need
b
2
. We compute
µ
2
,
1
=
0 and hence
b
2
=
b
2
,
b
2
=
b
2
. Then
B
1
=
1 and
B
2
=
229. Clearly,
B
2
>
(3
/
4
−
µ
2
,
1
)
B
1
and so we set
k
=
3. Now consider
b
3
. We compute
µ
3
,
2
=
45
/
229
≈
0
.
19 and,
since
q
2
=
0 there is no reduction to be performed on
b
3
. We compute
µ
3
,
1
=
0, so again
no size reduction is required. We now compute
b
3
=
229
b
2
=
45
b
3
−
(0
,
−
90
/
229
,
12
/
229)
.
b
3
,
b
3
=
We have
B
2
=
229 and
B
3
=
8244
/
52441
≈
0
.
157. From this, one can check
µ
3
,
2
)
B
2
≈
that
B
3
<
(3
/
4
−
166
.
1. Hence, we swap
b
2
and
b
3
and set
k
=
2.
At this point we have the vectors
b
1
=
(1
,
0
,
0) and
b
2
=
(0
,
0
,
3)
and
b
1
=
b
1
,
b
2
=
b
2
. First, check that
µ
2
,
1
=
0 and so no size reduction on
b
2
is required.
µ
2
,
1
)
B
1
=
Second,
B
1
=
1 and
B
2
=
9 and one checks that
B
2
>
(3
/
4
−
0
.
75. Hence, we
set
k
=
3. Now
b
3
=
(0
,
2
,
15)
and we compute
µ
3
,
2
=
45
/
9
=
5. Hence, we reduce
b
3
=
b
3
−
5
b
2
=
(0
,
2
,
0)
.
Now compute
µ
3
,
1
=
0, so no reduction is required.
One computes
µ
3
,
2
=
0,
b
3
=
µ
3
,
2
)
B
2
=
b
3
and
B
3
=
4. Hence,
B
3
<
(3
/
4
−
27
/
4
=
6
.
75 and so we should swap
b
2
and
b
3
and set
k
=
2. One can check that the
k
=
2 phase runs
