Cryptography Reference
In-Depth Information
The problem is therefore to deal with polynomials
F
(
x
) having a small solution but
whose coefficients are not small. Coppersmith's idea (in the formulation of Howgrave-
Graham [
268
]) is to build from
F
(
x
) a polynomial
G
(
x
) that still has the same solution
x
0
,
but which has coefficients small enough that the above logic does apply.
=
·
=
Example 19.1.1
Let
M
17
19
323 and let
x
2
F
(
x
)
=
+
33
x
+
215
.
We want to find the small solution to
F
(
x
)
≡
0(mod
M
) (in this case,
x
0
=
3 is a solution,
but note that
F
(3)
).
We seek a related polynomial with small coefficients. For this example
=
0 over
Z
9
x
2
=
−
+
=
−
−
G
(
x
)
9
F
(
x
)
M
(
x
6)
26
x
3
satisfies
G
(3)
=
0. This root can be found using Newton's method over
R
(or even the
quadratic formula).
We introduce some notation for the rest of this section. Let
M,X
∈ N
and let
F
(
x
)
=
i
=
0
a
i
x
i
∈ Z
[
x
]. Suppose
x
0
∈ Z
is a solution to
F
(
x
)
≡
0(mod
M
) such that
|
x
0
|
<X
.
We associate with the polynomial
F
(
x
) the row vector
(
a
0
,a
1
X,a
2
X
2
,
,a
d
X
d
)
.
b
F
=
···
(19.1)
Vice versa, any such row vector corresponds to a polynomial. Throughout this section we
will interpret polynomials as row vectors, and row vectors as polynomials, in this way.
Theorem 19.1.2
(Howgrave-Graham [
268
]) Let F
(
x
)
,X,M,b
F
be as above
(i.e.,
there
is some x
0
such that
<M/
√
d
|
x
0
|≤
X and F
(
x
0
)
≡
0(mod
M
)
). If
b
F
+
1
then
F
(
x
0
)
0
.
Proof
Recall the Cauchy-Schwarz inequality (
i
=
1
x
i
y
i
)
2
=
(
i
=
1
x
i
)(
i
=
1
y
i
)for
≤
x
i
,y
i
∈ R
. Taking
x
i
≥
0 and
y
i
=
1for1
≤
i
≤
n
one has
n
n
n
x
i
.
x
i
≤
i
=
1
i
=
1
Now
≤
d
d
d
i
=
0
|
i
=
0
|
a
i
x
i
0
i
X
i
|
F
(
x
0
)
|=
a
i
||
x
0
|
≤
a
i
|
i
=
0
√
d
<
√
d
1
M/
√
d
≤
+
1
b
F
+
+
1
=
M
where the third inequality is Cauchy-Schwarz, so
−
M<F
(
x
0
)
<M
.But
F
(
x
0
)
≡
0(mod
M
) and so
F
(
x
0
)
=
0.
=
i
=
0
a
i
x
i
be a monic polynomial. We assume that
F
(
x
) has at least one
solution
x
0
modulo
M
such that
Let
F
(
x
)
|
x
0
|
<X
for some specified integer
X
.If
F
(
x
)isnot
