Cryptography Reference
In-Depth Information
2
14
. Set
X
2
14
. Note that
X
M
1
/
4
.
4
.
which has a root
x
0
modulo
M
such that
|
x
0
|≤
=
≈
One can verify that the basic method in Section
19.1.1
does not find the small root.
Consider the basis matrix (this is of smaller dimension than the lattice in the proof of
Theorem
19.1.9
in the case
d
=
3 and
h
=
3)
M
2
0
0
0
0
0
0
M
2
X
0
0
0
0
0
0
M
2
X
2
0
0
0
0
0
0
Ma
0
Ma
1
X a
2
X
2
MX
3
.
0
0
0
0
Ma
0
X a
1
X
2
Ma
2
X
3
MX
4
0
0
0
0
Ma
0
X
2
Ma
1
X
3
Ma
2
X
4
MX
5
0
a
0
2
a
0
a
1
X
(
a
1
+
2
a
0
a
2
)
X
2
2
a
1
a
2
)
X
3
(
a
2
+
2
a
1
)
X
4
2
a
2
X
5
X
6
(2
a
0
+
The dimension is 7 and the determinant is
M
9
X
21
. The first vector of the LLL-reduced
basis is
(
−
369928294330603367352173305173409792
,
1451057442025994832259962670402797568
,...
)
.
This corresponds to the polynomial
−
369928294330603367352173305173409792
+
3439987357258441728608570659
x
2
88565517701781911148679362207202
x
−
446358057645551896819258
x
3
4564259979987386926
x
4
+
+
1728007960413053
x
5
21177681998
x
6
,
−
−
which has
x
0
=
=
2
14
16384
as a real root.
(2
20
7)(2
21
x
3
(2
25
2883584)
x
2
Exercise 19.1.12
Let
M
=
+
+
17) and
F
(
x
)
=
+
−
+
<
2
9
46976195
x
+
227. Use Coppersmith's algorithm to find an integer
x
0
such that
|
x
0
|
and
F
(
x
0
)
≡
0(mod
M
).
Remark 19.1.13
It is natural to wonder whether one can find roots right up to the limit
X
M
1
/d
. Indeed, the
term can be eliminated by performing an exhaustive search over
the top few bits of the root
x
0
. An alternative way to proceed is to set
=
−
=
1
/
log
2
(
M
), break
|
x
0
|
<M
1
/d
of size 2
M
1
/d
into
M
2
=
4 intervals of size 2
M
1
/d
−
2
=
M
1
/d
−
the range
and perform Coppersmith's algorithm for each subproblem in turn.
M
1
/d
. A first obser-
vation is that for
X>M
1
/d
one does not necessarily expect a constant number of solutions;
see Exercise
19.1.14
. Coppersmith [
132
] gives further arguments why
M
1
/d
is the best one
can hope for.
Another question is whether one can go beyond the boundary
X
=
