View Single Post
Old 2009-03-19, 20:36   #21
Feb 2004

25810 Posts

Originally Posted by 10metreh View Post
What about 2/7*N? That's what I use.
I'm still not really satisfied. For a c120 I'd then do ecm to a 34.3-digit factor level. That's about 1.25 cpu-hours work, whereas the ggnfs job takes ~20-25 cpu-hours. ECMing for just 1/16th of the sieve time seems a little frugal. Ben mentioned a few posts above a tentative recommendation of ~1/3 the sieve time, and I noticed in another thread fivemack said he does about 1/4 (

Any simple fraction*N factor-digits ecm rule probably matches reality pretty badly for one size or another, assuming a constant ratio of ecm_time to sieve_time is correct, which I'm not even sure it is. Ultimately we want to find a factor as quickly as possible. Running gnfs guarantees we'll find it after a certain period of time, while doing ecm gives us a chance to maybe find it sooner. Doing ecm yields progressively worse returns though. About all I can say is that we probably should spend more than zero time ecming, but less than the full sieve time.

I still hope someone can step up with some solid math and explain the reasoning behind it and/or point to a good chunk of empirical data. Maybe something taking into consideration the probability of our composite having a factor of a certain size and the probability per time unit of finding such a factor with ecm. The gmp-ecm readme file gives at least a part of the solution in the quote "After performing the expected number of curves from Table 1, the probability that a factor of D digits was missed is exp(-1), i.e., about 37%." Anyway, surely there are wizards lurking around here for whom such tricks is a trifling matter.

In the meantime I'll be releasing a new version soon that is a lot faster for small numbers (using experimentally determined better ecm limits and letting yafu work its pollard rho magic), and hopefully a little better for bigger numbers. Without knowing what the optimal targets even are for bigger numbers though, it's hard to say. Anyway, you're of course all welcome to alter the config/source and use whatever limits you prefer.
mklasson is offline   Reply With Quote