Cryptography Reference
In-Depth Information
19
Coppersmith's method and related applications
An important application of lattice basis reduction is finding small solutions to polynomial
equations
F
(
x
)
0(mod
M
)ofdegree
d>
1. The main purpose of this chapter is to
present some results of Coppersmith [
131
] on this problem. We also discuss finding small
roots of bivariate integer polynomials and some other applications of these ideas.
In general, finding solutions to modular equations is easy if we know the factorisation of
the modulus, see Section
2.12
. However, if the factorisation of the modulus
M
is not known
then finding solutions can be hard. For example, if we can find a solution to
x
2
≡
≡
1(mod
M
)
that is not
x
1 then we can split
M
. Hence, we do not expect efficient algorithms for
finding all solutions to modular equations in general.
Suppose then that the polynomial equation has a “small” solution. It is not so clear that
finding the roots is necessarily a hard problem. The example
x
2
=±
≡
1(mod
M
) no longer
gives any intuition since the two non-trivial roots both have absolute value at least
√
M
.
As we will explain in this chapter, if
F
(
x
)
≡
0(mod
M
)ofdegree
d
has a solution
x
0
such
<M
1
/d
−
for small
>
0 then it can be found in polynomial-time. This result has
a number of important consequences.
General references for the contents of this chapter are Coppersmith [
131
,
132
], May [
370
,
371
], Nguyen and Stern [
415
] and Nguyen [
409
].
that
|
x
0
|
19.1 Coppersmith's method for modular univariate polynomials
19.1.1 First steps to Coppersmith's method
We sketch the basic idea of the method, which goes back to Hastad. Let
F
(
x
)
=
x
d
+
a
d
−
1
x
d
−
1
a
0
be a monic polynomial of degree
d
with integer coefficients.
Suppose we know that there exist one or more integers
x
0
such that
F
(
x
0
)
+···+
a
1
x
+
≡
0(mod
M
)
<M
1
/d
. The problem is to find all such roots.
and that
|
x
0
|
x
i
0
|
Since
|
<M
for all 0
≤
i
≤
d
then, if the coefficients of
F
(
x
) are small enough, one
might have
F
(
x
0
)
. The problem of finding integer roots of integer polynomials
is easy: we can find roots over
=
0 over
Z
using numerical analysis (e.g., Newton's method) and
then round the approximations of the roots to the nearest integer and check whether they
are solutions of
F
(
x
).
R
