> I've read on the list some time ago that ECM takes, like
> Pollard-Rho or
> P-1, O(sqrt(f)) operations mod N to find a factor f. But
> looking at the
> factors found so far I find that hard to believe; according to that
And quite right too. It's just plain wrong. ECM runs in sub-exponential
time.
> formula, finding a 50-digit factor should be 10^15 times harder than
> finding a 20-digit factor. Even if a 20-digit could be found in 1 sec.
> average, the 50-digit would take some 30 million years - I
> dont believe
> this much time has been spent on ECM worldwide already.
> Is ECM better than O(sqrt(f)) ? Are there any more accurate lower
> bounds, or even a \Theta(g(f)) ?
The expected number of arithmetic operations taken to find a prime factor p
is asymptotic to exp(sqrt(log p log log p)) and so is, in some handwaving
manner, halfway between polynomial and exponential.
Of course, as N gets larger the cost of each operation gets larger, but at a
strictly polynomial rate for any sane implementation of multiple precision
arithmetic.
Paul
p.s. I found a 50-digit factor by ECM recently 8-)
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
