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
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)) ?
Ciao,
Alex.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
