Cryptography Reference
In-Depth Information
polynomial method, but we present a simpler version following work of Howgrave-Graham,
Boneh, Durfee and others.
The polynomial
F
(
x
)
p
) has a small solution modulo
p
. The problem is that we
do not know
p
, but we do know a multiple of
p
(namely,
N
). The idea is to form a lattice
corresponding to polynomials that have a small root modulo
p
and to apply Coppersmith's
method.
=
(
x
+
Theorem 19.4.2
Let N
=
pq with p<q<
2
p. Let
0
<<
1
/
4
, and suppose p
∈ N
is
2
√
2
N
1
/
4
−
. Then given N and p one can factor N in time polynomial
1
such that
|
p
−
p
|≤
in
log(
N
)
and
1
/.
√
N
.Let
X
p
) and note that
√
N/
2
1
=
+
≤
≤
=
2
√
2
N
1
/
4
−
Proof
Write
F
(
x
)
(
x
p
.
We describe the lattice to be used. Let
h
≥
4 be an integer to be determined later and let
k
=
2
h
. Consider the
k
+
1 polynomials
N
h
,N
h
−
1
F
(
x
)
,N
h
−
2
F
(
x
)
2
,...,NF
(
x
)
h
−
1
,F
(
x
)
h
,xF
(
x
)
h
,...,x
k
−
h
F
(
x
)
h
.
0(mod
p
h
).
Consider the lattice corresponding to the above polynomials. More precisely, a basis
for the lattice is obtained by taking each polynomial
G
(
x
) above and writing the vector of
coefficients of the polynomial
G
(
x
) as in equation (
19.1
). The lattice has dimension
k
Note that if
p
=
p
+
x
0
and if
G
(
x
) is one of these polynomials then
G
(
x
0
)
≡
+
1
and determinant
N
h
(
h
+
1)
/
2
X
k
(
k
+
1)
/
2
.
Applying LLL gives a shor
t vec
tor and, to apply Howgrave-Graham's result, we
ne
ed 2
k/
4
det(
L
)
1
/
(
k
+
1)
<p
h
/
√
k
+
1. Hence, since
p>
(
N/
2)
1
/
2
, it is sufficient that
√
k
+
12
k/
4
N
h
(
h
+
1)
/
(2(
k
+
1))
X
k/
2
<
(
N/
2)
h/
2
. Rearranging gives
X<N
h/k
−
h
(
h
+
1)
/
(
k
(
k
+
1))
2
−
h/k
2
−
1
/
2
/
(
k
1)
1
/k
.
+
1
/
√
2.
1)
1
/k
2
log
2
(
k
+
1)
/k
2
1
/
2
1)
1
/k
Since
k
≥
7wehave(
k
+
=
≤
and so 1
/
(
k
+
≥
Now, since
k
=
2
h
we find that the result holds if
1
2
√
2
X<N
1
/
2(1
−
(
h
+
1)
/
(2
h
+
1))
.
Since
1
/
2(1
−
(
h
+
1)
/
(2
h
+
1))
=
1
/
4
−
1
/
(4(2
h
+
1))
the
result
will
follow
if
1
/
(4(2
h
+
1))
<
. Taking
h
≥
max
{
4
,
1
/
(4
)
}
is sufficient.
N
α
and
N
β
One can obtain a more general version of Theorem
19.4.2
.If
p
=
|
x
|≤
where 0
<α,β<
1 then, ignoring constants, the required condition in the proof is
h
(
h
+
1)
βk
(
k
+
1)
+
<αh
(
k
+
1)
.
2
2
=
√
βk
and simplifying gives
β<α
2
. The case we have shown is
α
Taking
h
=
1
/
2 and
β<
1
/
4. For details see Exercise 19.4.5 or Theorem 6 and 7 of [370].
Example 19.4.3
Let
N
=
16803551,
p
=
2830 and
X
=
10.
(
x
2
Let
F
(
x
)
=
(
x
+
p
) and consider the polynomials
N,F
(
x
)
,xF
(
x
)
=
+
px
) and
x
2
F
(
x
), which all have the same small solution
x
0
modulo
p
.
