Cryptography Reference
In-Depth Information
can be broken most of the time: Hildebrand and Tenenbaum showed that, for any
>
0,
equation (
15.5
) holds when
X
exp(log(
X
)
5
/
6
+
) and
Y
exp(log(
X
)
1
/
6
)
≥
Y
≥
≤
Z
≤
X
for all but at most
M/
exp(log(
M
)
1
/
6
−
) integers 1
≤
X
≤
M
. As a
s
pecial case, this result
−
√
p,p
+
√
p
] contains a
Y
-smooth
shows that, for almost all primes
p
, the interval [
p
exp(log(
X
)
5
/
6
+
) (i.e., subexponential smoothness).
Using Conjecture
15.3.1
one obtains the following complexity for the elliptic curve
method (we stress that the complexity is in terms of the smallest prime factor
p
of
N
, rather
than
N
itself).
integer where
Y
=
Theorem 15.3.2
(Conjecture 2.10 of [
339
]) Ass
um
e Conjecture
15.3.1
. One can find
the smallest factor p of an integer N in L
p
(1
/
2
,
√
2
+
o
(1))
M
(log(
N
))
bit operations as
p
→∞
.
L
p
(1
/
2
,
1
/
√
2) (since the size of
p
is not known
one actually runs the algorithm repeatedly for slowly increasing valu
e
s of
B
). Then each
run of Algorithm
11
requires
O
(
B
log(
B
)
M
(log(
N
)))
Proof
Guess the size of
p
and choose
B
=
L
p
(1
/
2
,
1
/
√
2
=
+
o
(1))
M
(
log(
N
))
bit operations. By Conjecture
15.3.1
one needs to repeat the process
L
p
(1
/
2
,
1
/
√
2
+
o
(1))
times. The result follows.
and
p<
√
N<
2
p
.
Exercise
1
5.3.3
Let
N
=
pq
where
p
is
prime
Show
that
L
p
(1
/
2
,
√
2
+
=
+
o
(1)). Hence, in the worst case, the complexity of
ECM is the same as the complexity of the quadratic sieve.
o
(1))
L
N
(1
/
2
,
1
For further details on the elliptic curve method we refer to Section 7.4 of [
150
]. We
remark that Lenstra, Pila and Pomerance [
342
] have considered a variant of the elliptic
curve method using divisor class groups of hyperelliptic curves of genus 2. The Hasse-Weil
interval for such curves contains an interval of the form (
X,X
X
3
/
4
) and Theorem 1.3
of [
342
] proves that such intervals contain
L
X
(2
/
3
,c
1
)-smooth integers (for some constant
c
1
) with probability 1
/L
X
(1
/
3
,
1). It follows that there is a rigorous factoring algorithm
with complexity
L
p
(2
/
3
,c
) bit operations for some constant
c
2
. This algorithm is not used
in practice, as the elliptic curve method works fine already.
+
Exercise 15.3.4
Suppose a sequence of values 1
<x<N
are chosen uniformly at ran-
dom. Show that one can find such a value that is
L
N
(2
/
3
,c
)-smooth, together with its
factorisation, in expected
L
N
(1
/
3
,c
+
o
(1)) bit operations for some constant
c
.
Remark 15.3.5
It is tempting to conjecture that the Hasse interval contains a polynomially
smooth integer (indeed, this has been done by Maurer and Wolf [
367
]; see equation (
21.9
)).
This is not relevant for the elliptic curve factoring method, since such integers would be very
rare. Suppose the probability that an integer of size
X
is
Y
-smooth is exactly 1
/u
u
, where
u
log(
X
)
/
log(
Y
) (by Theorem
15.1.2
, thi
s i
s reasona
ble
as long as
Y
1
−
=
≥
log(
X
)).Itis
2
√
X,X
2
√
X
] is likely to contain a
Y
-smooth
natural to sup
po
se that the interval [
X
−
+
integer if 4
√
X>u
u
.Let
Y
log(
X
)
c
. Taking logs of both sides of the inequality gives
=