Cryptography Reference
In-Depth Information
2
N
θ−
4
.Since
w
4
N
2
θ−
2
,wehave
1
1
Choose
M
to be an integer no less than
≤
that
w
can be written as
w
=
u
0
+
v
0
·
M
with the unknown integers
u
0
and
v
0
satisfying 0
M
.
Let
b
=
a
−
(
N
+2
−
2
√
2
N
)
mod
N
,and
≤
u
0
,v
0
≤
M
b
1
mod
N.
a
M·v
x
G
(
x
)=
·
−
v
=0
Computing the polynomial
G
(
x
)takestime
O
(
M
)andstoring
G
(
x
)requires
space
O
(
M
). Note that
G
(
a
u
0
)
≡
0mod
q
since
w
=
u
0
+
v
0
·
M
.Evaluate
G
(
x
)mod
N
at
a
u
for all 0
M
. This gives a list of
M
numbers, one of
which has a non-trivial gcd with
N
. Then the factorization of
N
is obtained.
This method requires the evaluation of
G
(
x
)at
M
points. By the Fast Fourier
Transform (FFT), one can evaluate a polynomial of degree
M
at
M
points in time
O
(
M
log
M
) operations (see Chapter 10 in [4]). Since
G
(
x
) is a polynomial of
degree
M
+1, these
M
numbers can be obtained in time
O
(
M
log
M
)operations.
One of these values has a non-trivial gcd with
N
,whichcanbecalculatedintime
O
(
M
log
N
) operations by the Euclidean algorithm. This completes the proof of
Theorem 3.
≤
u
≤
=
N
θ
Now we consider the case
|
ρq
−
p
|
with a known constant
ρ
satisfying
1
<ρ<
2.
Theorem 4.
Let
N
=
pq
be an integer where primes
p
and
q
satisfy
|
ρq
−
p
|
=
4
<θ<
2
.If
ρ
is a known simple fraction between
1
and
2
,then
N
canbefactoredintime
O
(
N
θ−
4
+
ε
)
.
1
N
θ
with
s
Proof.
Since
ρ
is a known simple fraction between 1 and 2, we write
ρ
=
t
with
the known integers
s
and
t
satisfying
s>t>
0andgcd(
s, t
)=1.Wehave
|
=
tN
θ
,and
sq
−
tp
|
2
√
stN
=
tp
)
2
sq
+
tp
+2
√
stN
(
sq
−
sq
+
tp
−
t
2
N
2
θ
4
√
stN
t
4
N
2
θ−
2
.
<
<
(6)
Since
t
(
N
−
p
)
−
s
(
q
−
1) = 0 mod (
q
−
1)
,
we have
tN
+
s
−
(
tp
+
sq
)=0mod(
q
−
1)
.
(7)
By (6), we have that
tp
+
sq
can be written as
tp
+
sq
=
2
√
stN
+
w,
Search WWH ::
Custom Search