Cryptography Reference
In-Depth Information
the determinant of this lattice. Lattice basis reduction yields a short vector that corresponds
to a polynomial
G
(
x,y
) with small coefficients such that every root of
F
(
x,y
) is a root
of
G
(
x,y
) modulo
M
.If(
x
0
,y
0
) is a sufficiently small solution to
F
(
x,y
) then, using an
analogue of Theorem
19.1.2
, one infers that
G
(
x
0
,y
0
)
.
A crucial detail is that
G
(
x,y
) has no common factor with
F
(
x,y
). To show this suppose
G
(
x,y
)
=
0 over
Z
F
(
x,y
)
A
(
x,y
) for some polynomial (we assume that
F
(
x,y
) is irreducible, if
not then apply the method to its factors in turn). Then
G
(
x,y
)
=
=
0
≤
i,j<k
A
i,j
x
i
y
j
F
(
x,y
)
and so the vector of coefficients of
G
(
x,y
) is a linear combination of the coefficient vectors
of the
k
2
polynomials
s
a,b
(
x,y
)for0
a,b<k
. But this vector is also a linear combination
of the rows of the matrix (0
T
) in the original lattice. Considering the first
k
2
columns
(namely the columns of
S
) one has a linear dependence of the rows in
S
. Since det(
S
)
≤
=
0
this is a contradiction.
It follows that the resultant
R
x
(
F,G
) is a non-zero polynomial, and so one can find all
solutions by finding the integer roots of
R
x
(
F,G
)(
y
) and then solving for
x
.
To determine the complexity it is necessary to compute the determinant of
T
and
to bound
M
. Coron shows that the method works if
XY <W
2
/
(3
d
)
−
1
/k
2
−
9
d
. To get the
stated running time for
XY <W
2
/
(3
d
)
and perform-
ing exhaustive search on the
O
(
d
) highest-order bits of
x
0
(i.e., running the algorithm a
polynomial in 2
d
times).
Coron proposes setting
k
=
log(
W
)
Example 19.3.2
Consider
F
(
x,y
)
=
axy
+
bx
+
cy
+
d
=
127
xy
−
1207
x
−
1461
y
+
127
4
21 with
X
=
30
,Y
=
20. Let
M
=
(see below).
Consider the 13
×
9 matrix (this is taking
k
=
2 in the above proof and introducing the
powers
X
i
Y
j
from the start)
aX
2
Y
2
bX
2
YcXY
2
dXY
0
0
0
0
0
aX
2
Y
cXY bX
2
0
0
0
dX
00
aXY
2
bXY
0
cY
2
0
0
0
dY
0
0
0
0
aXY
0
0
bX cY d
=
B
.
MX
2
Y
2
0
0
0
0
0
0
0
0
MX
2
Y
0
0
0
0
0
0
0
0
.
.
0
0
0
0
0
0
0
0
M
We take
S
to be the matrix
abcd
0
a
0
c
00
ab
000
a
corresponding to the monomials
x
i
0
+
i
y
j
0
+
j
for 0
≤
i,j <
2 and fixed
i
0
=
j
0
=
1. Note
a
4
127
4
.
that
M
=
det(
S
)
=
=
