Cryptography Reference
In-Depth Information
10
8
Exercise 19.4.18
Repeat the above example for
W
=
150000001
=
1
.
5
·
+
1 and
W
=
46558000.
If this process fails then one can make adjustments to the value of
P
(for example, by
changing the exponents
e
i
). Analysing the probability of success of this approach is an
open problem.
19.5 Simultaneous Diophantine approximation
Let
α
. It is well-known that the continued fraction algorithm produces a sequence
of rational numbers
p/q
such that
∈ R
<
1
/q
2
. This is the subject of
Diophantine
approximation
; see Section 1.1 of Lovasz [
356
] for background and discussion. We now
define a natural and important generalisation of this problem.
|
α
−
p/q
|
Definition 19.5.1
Let
α
1
,...,α
n
∈ R
−
n
.The
simultaneous Diophantine approximation problem
is to find
q,p
1
,...,p
n
∈ Z
∈ N
≥
and let
>
0. Let
Q
be such that
Q
such
that 0
<q
≤
Q
and
|
α
i
−
p
i
/q
|≤
/q
(19.4)
for all 1
≤
i
≤
n
.
A theorem of Dirichlet mentioned in Section 1.1 of [
356
] and Section 17.3 of [
220
]
shows that there is a solution satisfying the constraints in Definition
19.5.1
.
Exercise 19.5.2
Let
≥
1
/
2. Prove that integers
p
1
,...,p
n
satisfying equation (
19.4
)
exist for any
n
and
q
.
A major application of lattice reduction is to give an algorithm to compute the integers
(
q,p
1
,...,p
n
) in Definition
19.5.1
. In practice, the real numbers
α
1
,...,α
n
are given to
some decimal precision (and so are rational numbers with coefficients of some size). The
size of an instance of the simultaneous Diophantine approximation is the sum of the bit
lengths of the numerator and denominator of the given approximations to the
α
i
, together
with the bit length of the representation of
and
Q
.Let
X
be a bound on the absolute value
of all numerators and denominators of the
α
i
. The computational task is to find a solution
(
q,p
1
,...,p
n
) in time that is polynomial in
n
,log(
X
), log(1
/
) and log(
Q
).
Theorem 19.5.3
Let α
1
,...,α
n
∈ Q
be given as rational numbers with numerator
and denominator bounded in absolute value by X. Let
0
<<
1
. One can com-
pute in polynomial-time integers
(
q,p
1
,...,p
n
)
such that
0
<q<
2
n
(
n
+
1)
/
4
−
(
n
+
1)
and
|
α
i
−
p
i
/q
|≤
/q for all
1
≤
i
≤
n.
