Thread: ecm thing
View Single Post
Old 2016-12-16, 23:58   #4
VBCurtis's Avatar
Feb 2005
Riverside, CA

5,279 Posts

You should start with "odds this composite *has* a 35-digit factor." Absent any knowledge of the number's special form, that's about 1/n, so 1/35 in this case.

Then, given there is such a factor to find, and *no* previous ECM attempts, you could calculate your odds of finding the factor after a certain number of curves. That's roughly (1-1/e^(z/y)), where z is the number of curves you plan to run and y is the expected number of curves required to discover a factor of that specific size. y-values are freely available for each n divisible by 5; if you wish to run non-standard B1 bounds, invoking gmp-ecm with "-v" flag will print the expected curve counts.

I am not 100% certain about the above formula; I have used it in the past when z is of the same order of magnitude of y (say, 2000 curves when 4400 is the expected number of curves), but I believe it's an approximation when z is a few hundred or more that isn't quite accurate if you're running a very small number of curves.

EDIT: Note that previous ECM failures alter the first probability- it is less likely a factor of the desired size exists when ECM has already been run. Calculating this probability is left as an exercise for the reader.

Last fiddled with by VBCurtis on 2016-12-17 at 00:00
VBCurtis is offline   Reply With Quote