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
=
 
Search WWH ::




Custom Search