Basic Question about ECM factoring?
 

If there were no practical time limits when trying to factor a number using ECM and you pick a B1 such as 11,000,000 or 44,000,000 so that you could run as many curves as desired is it guaranteed that you will eventually find the factor? Also if you just kept raising B1 to much larger numbers, would that guarantee success, again assuming no practical time limit?

For example, the C140 of C(566) Cullen number in Mr. Leyland's tables. From my understanding of what I have read you could run ECM curves forever and never find the factor if there are not small factors of p-1 less than B1 or one of the factors of p-1 between B1 and B2 and the rest less than B1, but I am not sure my understanding is correct.

Since in reality we do have time limits, I am assuming the better approach to attempting to factor this number is to learn how gnfs works. What sort of practical timeframe would be required when trying to factor this C140 using gnfs not counting any practice or learning time?

Thankyou

ECM finds the factor [I]p[/I] if the group order of the elliptic curve (mod [I]p[/I]) has only small prime factors. By Hasse's theorem, the order is in the interval [[I]p[/I]-2sqrt([I]p[/I])+1, [I]p[/I]+2sqrt([I]p[/I])+1]. If [I]p[/I] is large and your B1,B2 very small, it is quite possible that no smooth enough number exists in that interval. Another problem for this analysis is that Montgomery parameterisation does not allow as many distinct curves to be selected as, say, Weierstraß form does, so the lucky smooth integer(s) in the Hasse interval may not be accessible. A far greater problem is that most ECM implementations choose the sigma value for the curve parameters from a fairly small set of integers ([7, 2^32] in the case of GMP-ECM), so only a tiny fraction of distinct group order from the Hasse interval is accessible. So there are several reasons that for very large [I]p[/I] and given B1,B2, it may actually be impossible for ECM to find [I]p[/I]. However, [I]p[/I] would have to be quite large.
Keep in mind, though, that choosing B1,B2 way off has a severe impact on performance of ECM. Especially when choosing them way too low, the expected time to find [I]p[/I] grows faster than [I]p[/I], making ECM worse than trial factoring!

Alex