Cryptography Reference
In-Depth Information
p
2
x
2
M
1
/
2
+
Exercise 19.1.14
Let
M
=
and consider
F
(
x
)
=
+
px
. Show that if
X
=
0(mod
M
)is2
M
,
where 0
<<
1
/
2 then the number of solutions
|
x
|
<X
to
F
(
x
)
≡
Exercise 19.1.15
Let
N
=
pq
be a product of two primes of similar size and let
e
∈ N
be a small integer such that gcd(
e,ϕ
(
N
))
=
1. Let 1
<a,y<N
be such that there is an
x<N
1
/e
satisfying (
a
x
)
e
integer 0
≤
+
≡
y
(mod
N
). Show that, given
N,e,a,y
, one
can compute
x
in polynomial-time.
19.2 Multivariate modular polynomial equations
∈ Z
Suppose one is given
F
(
x,y
)
[
x,y
] and integers
X
,
Y
and
M
and is asked to find
one or more roots (
x
0
,y
0
)to
F
(
x,y
)
<Y
.
One can proceed using similar ideas to the above, hoping to find two polynomials
F
1
(
x,y
)
,F
2
(
x,y
)
≡
0(mod
M
) such that
|
x
0
|
<X
and
|
y
0
|
∈ Z
[
x,y
] such that
F
1
(
x
0
,y
0
)
=
F
2
(
x
0
,y
0
)
=
0 over
Z
, and such that
the resultant
R
x
(
F
1
(
x,y
)
,F
2
(
x,y
))
0 (i.e., that
F
1
(
x,y
) and
F
2
(
x,y
)are
algebraically
independent
). This yields a heuristic method in general, since it is hard to guarantee the
independence of
F
1
(
x,y
) and
F
2
(
x,y
).
=
Theorem 19.2.1
Let F
(
x,y
)
∈ Z
[
x,y
]
be a polynomial of total degree d (i.e., every
monomial x
i
y
j
satisfies i
be such that XY <M
1
/d
−
for some
0
<<
1
/d. Then one can compute (in time polynomial in
log(
M
)
and
1
/ > d) polyno-
mials F
1
(
x,y
)
,F
2
(
x,y
)
+
j
≤
d). Let X,Y,M
∈ N
∈ Z
∈ Z
2
with
|
x
0
|
|
y
0
|
[
x,y
]
such that, for all
(
x
0
,y
0
)
<X,
<Y
≡
=
=
Z
and F
(
x
0
,y
0
)
0(mod
M
)
, one has F
1
(
x
0
,y
0
)
F
2
(
x
0
,y
0
)
0
over
.
Proof
We refer to Jutla [
290
] and Section 6.2 of Nguyen and Stern [
415
]forasketchof
the details.
19.3 Bivariate integer polynomials
2
We now consider
F
(
x,y
)
∈ Z
[
x,y
] and seek a root (
x
0
,y
0
)
∈ Z
such that both
|
x
0
|
and
|
y
0
|
are small. Coppersmith has proved the following important result.
Theorem 19.3.1
Let F
(
x,y
)
∈ Z
[
x,y
]
and let d
∈ N
be such that
deg
x
(
F
(
x,y
))
,
deg
y
(
F
(
x,y
))
≤
d. Write
F
i,j
x
i
y
j
.
F
(
x,y
)
=
0
≤
i,j
≤
d
Fo r X,Y
∈ N
define
X
i
Y
j
.
W
=
0
≤
i,j,
≤
d
|
max
F
i,j
|
