Cryptography Reference
In-Depth Information
If XY <W
2
/
(3
d
)
then there is an algorithm that takes as input F
(
x,y
)
,X,Y, runs in
time (bit operations) bounded by a polynomial in
log(
W
)
and
2
d
and outputs all pairs
(
x
0
,y
0
)
2
such that F
(
x
0
,y
0
)
∈ Z
=
0
,
|
x
0
|≤
X and
|
y
0
|≤
Y.
The condition in Theorem
19.3.1
is somewhat self-referential. If one starts with a
polynomial
F
(
x,y
) and bounds
X
and
Y
on the size of roots, then one can compute
W
and
determine whether or not the algorithm will succeed in solving the problem.
Proof
(Sketch) There are two proofs of this theorem, both of which are rather technical. The
original by Coppersmith can be found in [
131
]. We sketch a simpler proof by Coron [
139
].
As usual, we consider shifts of the polynomial
F
(
x,y
). Choose
k
∈ N
(sufficiently large)
and consider the
k
2
polynomials
x
a
y
b
F
(
x,y
)
s
a,b
(
x,y
)
=
f r
0
≤
a,b<k
k
)
2
monomials
x
i
y
j
with 0
k
. Coron chooses a certain set of
k
2
in the (
d
+
≤
i,j < d
+
monomials (specifically of the form
x
i
0
+
i
y
j
0
+
j
for 0
≤
i,j < k
and fixed 0
≤
i
0
,j
0
≤
d
)
and obtains a
k
2
k
2
matrix
S
with non-zero determinant
M
. (The most technical part of
[
139
] is proving that this can always be done and bounding the size of
M
.)
One can now consider the (
d
×
k
)
2
polynomials
Mx
i
y
j
for 0
+
≤
i,j < d
+
k
. Writing
each polynomial as a row vector of coefficients, we now have a
k
2
k
)
2
k
)
2
+
(
d
+
by (
d
+
matrix. One can order the rows such that the matrix is of the form
∗
MI
k
2
0
0
MI
w
S
=
+
k
)
2
−
k
2
,
∗
represents a
k
2
×
×
where
w
(
d
w
matrix, and
I
w
denotes the
w
w
identity
matrix.
Now, since
M
=
det(
S
) there exists an integer matrix
S
such that
S
S
=
MI
k
2
. Perform
the row operations
I
k
2
00
∗
MI
k
2
0
0
MI
w
S
S
∗
0
T
0
MI
w
=
S
I
k
2
0
00
I
w
−
for some
k
2
×
w
matrix
T
. Further row operations yield a matrix of the form
S
∗
0
T
00
w
integer matrix
T
.
Coron considers a lattice
L
corresponding to
T
(where the entries in a column corre-
sponding to monomial
x
i
y
j
are multiplied by
X
i
Y
j
as in equation (
19.2
)) and computes
for some
w
×
