Cryptography Reference
In-Depth Information
If the right hand side of equation (
19.6
) is small then performing Euclid's algorithm on
a/b
gives a sequence of possible values for
q
a
/q
b
. For each such value, one can compute
b/q
b
=
(
dq
b
−
y
)
/q
b
=
d
+−
y/q
b
.
b
<
2
q
b
then one has computed
d
exactly and can solve
a
If
0(mod
d
).
Note that one must use the basic extended Euclidean algorithm, rather than the improved
method using negative remainders as in Algorithm
1
.
|
y
|
+
x
≡
+
y
≡
Exercise 19.6.1
Show that if
a<b<b
,
b
2
/
3
<d<
2
b
2
/
3
<
4
b
1
/
3
and
|
x
|
,
|
y
|
then the
above method finds
d
,
a
and
b
.
b
α
. Explain
why it is natural to assume
α>β
. Show that the above method succeeds if (ignoring
constant factors)
β<
< b
β
and
d
Exercise 19.6.2
Let the notation be as above. Suppose
|
x
|
,
|
y
|
=
−
1
+
2
α
and
β<
1
−
α
×
Exercise 19.6.3
Re-formulate this method in terms of finding a short vector in a 2
2
matrix. Derive the same conditions on
α
and
β
as in Exercise
19.6.2
.
b
630864082. The first few convergents
q
a
/q
b
to
a/b
are 1
,
45
/
46
,
91
/
93
,
409
/
418
,
500
/
511
,
1409
/
1440 and 1909
/
1951. Computing
approximations to
a/q
a
and
Example 19.6.4
Let
a
=
617283157 and
=
b/q
b
for these values (except the first) gives the following
table.
a/q
a
13717403
.
5
6783331
.
4
1509249
.
8
1234566
.
3
438100
.
2
323354
.
2
.
b/q
b
13714436
.
6
6783484
.
8
1509244
.
2
1234567
.
7
438100
.
1
323354
.
2
Any values around these numbers can be used as a guess for
d
. For example, taking
b
d
=
13717403 one finds
a
−
22
≡
+
136456
≡
0(mod
d
), which is a not particularly
good solution.
The four values
d
1
=
1234566,
d
2
=
1234567,
d
3
=
438100 and
d
4
=
323354 lead
b
b
to the solutions
a
−
157
≡
−
856
≡
0(mod
d
1
),
a
+
343
≡
−
345
≡
0(mod
d
2
),
a
−
b
b
257
≡
−
82
≡
0(mod
d
3
) and
a
−
371
≡
−
428
≡
0(mod
d
4
).
Howgrave-Graham gives a more general method for solving the problem that does not
require such a strict condition on the size of
y
. The result relies on heuristic assumptions
about Coppersmith's method for bivariate integer polynomials. We state this result as
Conjecture
19.6.5
.
Conjecture
19.6.5
(Algor
ithm 14 and Section 4 of [
269
]) Let
0
<α<
2
/
3
and β<
1
1
α
2
/
2
. There is a polynomial-time algorithm that takes as input
˜
a<b
and outputs all integers d>b
α
such that there exist integers x,y with
−
α/
2
−
−
α
−
< b
β
and
|
x
|
,
|
y
|
(
b
d
|
(
a
+
x
)
and d
|
+
y
)
.
Exercise 19.6.6
Let
a, b,X,Y
be given with
X<
˜
a<b
. Give a brute force algorithm
to output all
d>Y
such that there exist
x,y
∈ N
x, b
∈ Z
with
|
x
|
,
|
y
|≤
X
and
d
=
gcd(
a
+
+
y
). Show that the complexity of this algorithm is
O
(
X
2
log(
b
)
2
) bit operations.
