Cryptography Reference
In-Depth Information
We build the lattice corresponding to these polynomials (with the usual method of
converting a polynomial into a row vector). This lattice has basis matrix
N
0
0
0
˜
pX
0
0
.
pX X
2
0
0
00
pX
2
X
3
The first row of the output of the LLL algorithm on this matrix is (105
,
−
1200
,
800
,
1000),
which corresponds to the polynomial
x
3
8
x
2
G
(
x
)
=
+
−
120
x
+
105
.
The polynomial has the root
x
=
7 over
Z
. We can check that
p
=
p
+
7
=
2837 is a factor
of
N
.
Exercise 19.4.4
Let
N
=
22461580086470571723189523 and suppose you are given the
approximation
p
=
2736273600000 to
p
, which is correct up to a factor 0
≤
x<X
=
50000. Find the prime factorisation of
N
using Coppersmith's method.
Exercise 19.4.5
Let
>
0. Let
F
(
x
) be a polynomial of degree
d
such that
F
(
x
0
)
≡
2
N
α
2
/d
−
. Generalise the proof of The-
orem
19.4.2
to show that given
F
(
x
) and
N
one can compute
x
0
in time polynomial in
log(
N
),
d
and 1
/
.
N
α
and
1
0(mod
M
)forsome
M
|
N
,
M
=
|
x
0
|≤
Exercise 19.4.6
Coppersmith showed that one can factor
N
in time polynomial in log(
N
)
given
p
such that
<N
1
/
4
. Prove this result.
|
p
−
p
|
Exercise 19.4.7
Use Coppersmith's method to give an integer factorisation algorithm
requiring
O
(
N
1
/
4
) bit operations. (A factoring algorithm with this complexity was also
given in Section
12.5
.)
Exercise 19.4.8
Show that the method of this section also works if given
p
such that
<N
1
/
4
for some integer
k
such that gcd(
k,N
)
|
p
−
kp
|
=
1.
Exercise 19.4.9
Coppersmith also showed that one can factor
N
in time polynomial in
log(
N
)given
p
such that
p
p
(mod
M
) where
M>N
1
/
4
. Prove this result.
≡
Exercise 19.4.10
Let
N
q
. Show that if one knows half the high order bits
of
p
then one also knows approximately half the high order bits of
q
as well.
=
pq
with
p
≈
19.4.3 Factoring
p
r
q
As mentioned in Section
24.1.2
, moduli of the form
p
r
q
, where
p
and
q
are distinct primes
and
r
, can be useful for some applications. When
r
is large then
p
is relatively small
compared with
N
and so a natural attack is to try to factor
N
using the elliptic curve method.
∈ N
