Basic Question about ECM factoring?

drake2 · 2006-01-12, 03:55

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

akruppa · 2006-01-12, 07:40

ECM finds the factor p if the group order of the elliptic curve (mod p) has only small prime factors. By Hasse's theorem, the order is in the interval [p-2sqrt(p)+1, p+2sqrt(p)+1]. If p 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 p and given B1,B2, it may actually be impossible for ECM to find p. However, p 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 p grows faster than p, making ECM worse than trial factoring!

Alex

2006-01-12, 03:55	#1
drake2 Aug 2005 2⁴ Posts	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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Question regarding basic routines being used in Yafu.	storflyt32	YAFU	2	2015-06-29 23:25
basic question for assignment	wong8888	Information & Answers	5	2015-03-22 12:15
A basic math question	iconized	Prime Sierpinski Project	2	2012-02-03 00:01
Yet another basic-factoring-questions thread	davar55	Factoring	24	2011-01-23 23:57
Basic optimisation question	fivemack	Puzzles	6	2008-04-08 13:50

2006-01-12, 07:40	#2
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	ECM finds the factor p if the group order of the elliptic curve (mod p) has only small prime factors. By Hasse's theorem, the order is in the interval [p-2sqrt(p)+1, p+2sqrt(p)+1]. If p 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 p and given B1,B2, it may actually be impossible for ECM to find p. However, p 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 p grows faster than p, making ECM worse than trial factoring! Alex