Cryptography Reference
In-Depth Information
which, taking
M
2
.
07. (Note that the method worked for a larger
value of
x
0
; this is because the bound used on LLL only applies in the worst case.)
Consider instead the basis matrix that also includes rows corresponding to the polyno-
mials
xF
(
x
) and
x
2
F
(
x
)
=
10001, leads to
X
≈
M
0
0
0
0
0
0
MX
0
0
0
0
MX
2
0
0
0
0
0
B
=
.
5000
X
10
X
2
X
3
−
222
0
0
222
X
5000
X
2
10
X
3
X
4
0
−
0
−
222
X
2
5000
X
3
10
X
4
X
5
0
0
The dimension is 6 and the determinant is
M
3
X
15
. The condition for LLL to output a
sufficiently small vector is
2
5
/
4
M
3
X
15
1
/
6
M
√
6
,
≤
which leads to
X
≈
3
.
11. This indicates that some benefit can be obtained by using
x
-shifts.
Exercise 19.1.8
Let
G
(
x
) be a polynomial of degree
d
. Show that taking
dx
-shifts
G
(
x
)
,xG
(
x
)
,...,x
d
−
1
G
(
x
) gives a method that works for
X
M
1
/
(2
d
−
1)
.
≈
M
1
/
6
to
Exercise
19.1.8
shows that when
d
=
3 we have improved the result from
X
≈
M
1
/
5
. Coppersmith [
131
] exploits both
x
-shifts and powers of
F
(
x
). We now present
the method in full generality.
X
≈
Theorem 19.1.9
(Coppersmith) Let
0
<<
min
. Let F
(
x
)
be a monic poly-
nomial of degree d with one or more small roots x
0
modulo M such that
{
0
.
18
,
1
/d
}
<
2
M
1
/d
−
.
Then x
0
can be found in time, bounded by a polynomial in d,
1
/ and
log(
M
)
.
|
x
0
|
Proof
Let
h>
1 be an integer that depends on
d
and
and will be determined in equation
(
19.3
) below. Consider the lattice
L
corresponding (via the construction of the previous
section) to the polynomials
G
i,j
(
x
)
M
h
−
1
−
j
F
(
x
)
j
x
i
for 0
=
≤
i<d
,0
≤
j<h
.Note
0(mod
M
h
−
1
). The dimension of
L
is
dh
. One can represent
L
byalower
triangular basis matrix with diagonal entries
M
h
−
1
−
j
X
jd
+
i
. Hence, the determinant of
L
is
that
G
i,j
(
x
0
)
≡
M
(
h
−
1)
hd/
2
X
(
dh
−
1)
dh/
2
.
det(
L
)
=
Running LLL on this basis outputs an LLL-reduced basis with first vector
b
1
satisfying
<
2
(
dh
−
1)
/
4
det(
L
)
1
/dh
2
(
dh
−
1)
/
4
M
(
h
−
1)
/
2
X
(
dh
−
1)
/
2
.
b
1
=
This vector corresponds to a poly
no
mial
G
(
x
)ofdegree
dh
−
1 such that
G
(
x
0
)
≡
<M
h
−
1
/
√
dh
then Howgrave-Graham's result applies and we
0(mod
M
h
−
1
). If
b
1
have
G
(
x
0
)
=
0 over
Z
.
