Cryptography Reference
In-Depth Information
2
n
(
n
+
1)
/
4
−
n
and consider the lattice
L
n
+
1
Proof
Let
Q
=
⊆ Q
with basis matrix
/Q α
1
α
2
···
α
n
0
−
10
···
0
0
0
−
1
.
(19.5)
.
.
.
.
.
.
··· −
0
0
1
2
−
n
(
n
+
1)
/
4
n
+
1
. Every vector in the
The dimension is
n
+
1 and the determinant is
/Q
=
lattice is of the form (
q/Q,qα
1
−
p
1
,qα
2
−
p
2
,...,qα
n
−
p
n
). The entries of the lattice
X,
2
n
(
n
+
1)
/
4
/
n
+
1
are ratios of integers with absolute value bounded by max
{
}
.
Note that the lattice
L
does not have a basis with entries in
Z
, but rather in
Q
.
By Remark
17.5.5
the LLL algorithm applied to
L
runs in
O
(
n
6
max
n
log(
X
)
,n
2
{
+
3
) bit operations (which is polynomial in the input size) and outputs a non-
zero vector
v
n
log(1
/
)
}
=
(
q/Q,qα
1
−
p
1
,...,qα
n
−
p
n
) such that
2
n/
4
det(
L
)
1
/
(
n
+
1)
2
n/
4
2
−
n/
4
v
≤
=
=
<
1
.
If
q
=
0 then
v
=
(0
,
−
p
1
,...,
−
p
n
) with some
p
i
=
0 and so
v
≥
1, and so
q
=
0.
Without loss of generality
q>
0. Since
v
∞
≤
v
it follows that
q/Q
≤
<
1 and so
2
n
(
n
+
1)
/
4
−
(
n
+
1)
. Similarly,
0
<q<Q/
=
|
qα
i
−
p
i
|
<
for all 1
≤
i
≤
n
.
Exercise 19.5.4
Let
α
1
=
1
.
555111,
α
2
=
0
.
771111 and
α
3
=
0
.
333333. Let
=
0
.
01 and
10
6
. Use the method of this section to find a good simultaneous rational approximation
to these numbers.
Q
=
See Section 17.3 of [
220
] for more details and references.
19.6 Approximate integer greatest common divisors
The basic problem is the following. Suppose positive integers
a
and
b
exist such that
d
=
gcd(
a,b
) is “large”. Suppose that one is not given
a
and
b
, but only approximations
a, b
to them. The problem is to find
d
,
a
and
b
. One issue is that there can be surprisingly
many solutions to the problem (see Example
19.6.4
), so it may not be feasible to compute
all solutions for certain parameters. On the other hand, in the case
b
b
(i.e., one of the
values is known exactly, which often happens in practice) there are relatively few solutions.
Howgrave-Graham [
269
] has considered these problems and has given algorithms that
apply in various situations. We present one of the basic ideas. Let
a
=
b
=
a
+
x
and
b
=
+
y
.
Suppose ˜
a<b
and define
q
a
=
a/d
and
q
b
=
b/d
. Then, since
q
a
/q
b
=
a/b
,wehave
a
b
−
q
a
q
b
=
q
a
y
−
q
b
x
.
(19.6)
bq
b
