Cryptography Reference
In-Depth Information
Hence, it is sufficient that
√
dh
2
(
dh
−
1)
/
4
M
(
h
−
1)
/
2
X
(
dh
−
1)
/
2
<M
h
−
1
.
Rearranging gives
√
dh
2
(
dh
−
1)
/
4
X
(
dh
−
1)
/
2
<M
(
h
−
1)
/
2
,
which is equivalent to
c
(
d,h
)
X<M
(
h
−
1)
/
(
dh
−
1)
(
√
dh
2
(
dh
−
1)
/
4
)
2
/
(
dh
−
1)
=
√
2(
dh
)
1
/
(
dh
−
1)
.
where
c
(
d,h
)
=
Now
h
−
1
1
d
−
d
−
1
1
=
1)
.
dh
−
d
(
dh
−
Equating (
d
−
1)
/
(
d
(
dh
−
1))
=
gives
h
=
((
d
−
1)
/
(
d
)
+
1)
/d
≈
1
/
(
d
)
.
(19.3)
√
2(1
Note that
dh
=
1
+
(
d
−
1)
/
(
d
) and so
c
(
d,h
)
=
+
(
d
−
1)
/
(
d
))
d/
(
d
−
1)
, which
converges to
√
2as
0. Since
X<
2
M
1
/d
−
we require
1
1
→
2
≤
c
(
d,h
)
. Writing
x
=
√
2, which holds for 0
−
+
1
/x
)
x
≤
≤
≤
d/
(
d
1) this is equivalent to (1
x
0
.
18.
Rounding
h
up to the next integer gives a lattice such that if
<
2
M
1
/d
−
|
x
0
|
then the LLL algorithm and polynomial root finding leads to
x
0
.
Since the dimension of the lattice is
dh
1
/
and the coefficients of the polynomials
G
i,j
are bounded by
M
h
it follows that the running time of LLL depends on
d,
1
/
and
log(
M
).
≈
Exercise 19.1.10
Show that the precise complexity of Coppersmith's method is
O
((1
/
)
9
log(
M
)
3
) bit operations (recall that 1
/ > d
). Note that if one fixes
d
and
and considers the problem as
M
tends to infinity then one has a polynomial-time algorithm
in log(
M
).
We refer to Section 3 of [
132
] for some implementation tricks that improve the algorithm.
For example, one can add basis vectors to the lattice corresponding to polynomials of the
form
M
h
−
1
x
(
x
−
1)
···
(
x
−
i
+
1)
/i
!.
2
30
2
32
Example 19.1.11
Let
p
=
+
3,
q
=
+
15 and
M
=
pq
. Consider the polynomial
a
2
x
2
a
3
x
3
F
(
x
)
=
a
0
+
a
1
x
+
+
=
1942528644709637042
+
1234567890123456789
x
987654321987654321
x
2
x
3
,
+
+
