ECM factoring ?

2004-02-25, 07:53

I tried ECM factoring on 21xxxyyy exponent
All I see is messages like "At prime 797. Time thusfar 1234.345 sec."

Does anybody know what does that mean?

Or how long will I wait till there is a result?

And something more - there are Boundary 1 & 2 in ECM factoring dialog,
but there is nothing about how they should be chosen in help.

Is ECM faster than P-1 & Trail Factoring?

ET_ · 2004-02-25, 08:22

You can start looking at

http://www.mersenne.org/ecm.htm

then, if you like that kind of work, there are many distributed projects that use that system.

ECM is a sort of "statistical factoring" that can find bigger factors than P-1 or trial factoring, but to use it efficiently one should be part of a coordinate project.

Try searching the forum with "ECM" and happy hunting!

Luigi

R.D. Silverman · 2004-02-25, 16:46

Allow me to offer some advice and to suggest a (perhaps) more fruitful
use of CPU time.

If a large Mersenne number has been shown to have no factors under (say)
2^60, then trying to find a factor with ECM will require a very large
expenditure of CPU time with little chance of success. I won't discuss
the math behind this except to suggest that interested parties read
my joint paper with Sam Wagstaff Jr:

A Practical Analysis of the Elliptic Curve Factoring Algorithm
Mathematics of Computation (1993)

To find a factor in the (say) 25-30 digit range will require 100 to 200
curves with first ECM limit of around 100,000.

A prior post stated that taking ECM up to about 800 in step 1 required
1200 seconds for exponent near 20M. Step 1 time is linear in the bound,
so taking one curve to limit 100K will take ~42 hours. Step 2 will roughly
double this, so one curve will take "about" 3.5 days. 100 curves will take
1 year. This will give (roughly) a chance of about (1-1/e) of finding a
25 digit factor IF IT EXISTS.

May I suggest (and ask) that if you want to try ECM, then you help out
with trying to find factors from the Cunningham project. (i.e. exponent less
than 1200). It would be useful to those who are working on the Cunningham
project if all 2^n-1 (and 2^n+1) were tested with ECM up to 50 digit
factors before we run NFS on them. Please. We really could use help
on this.

For a list of what has been done, see http://www.mersenne.org/ecm.htm.

Indeed, perhaps we might even find a 60 digit factor of one of these
numbers; something that has not been done before.

Good hunting.

markhl · 2004-02-25, 19:32

Quote:

Originally Posted by Bob Silverman

I won't discuss the math behind this except to suggest that interested parties read my joint paper with Sam Wagstaff Jr:

A Practical Analysis of the Elliptic Curve Factoring Algorithm
Mathematics of Computation (1993)

Not everyone on this forum has science library access. If the publisher allows it, can you post a link to an HTML or PDF version of the article?

R.D. Silverman · 2004-02-25, 19:52

Quote:

Originally Posted by markhl

Not everyone on this forum has science library access. If the publisher allows it, can you post a link to an HTML or PDF version of the article?

You can get access to Math. Comp. at the Amer. Math. Soc. ams.org

The paper was written in Tex. The source is no longer available to me.
When I was laid off by my last employer I (and everyone else) was
basically hustled out of my office under guard; I had to leave a lot of stuff
behind on my office PC.

2004-02-25, 07:53	#1
Peet 2262₁₆ Posts	ECM factoring ? I tried ECM factoring on 21xxxyyy exponent All I see is messages like "At prime 797. Time thusfar 1234.345 sec." Does anybody know what does that mean? Or how long will I wait till there is a result? And something more - there are Boundary 1 & 2 in ECM factoring dialog, but there is nothing about how they should be chosen in help. Is ECM faster than P-1 & Trail Factoring?

2004-02-25, 08:22	#2
ET_ Banned "Luigi" Aug 2002 Team Italia 61×79 Posts	You can start looking at http://www.mersenne.org/ecm.htm then, if you like that kind of work, there are many distributed projects that use that system. ECM is a sort of "statistical factoring" that can find bigger factors than P-1 or trial factoring, but to use it efficiently one should be part of a coordinate project. Try searching the forum with "ECM" and happy hunting! Luigi Last fiddled with by ET_ on 2004-02-25 at 08:23

2004-02-25, 16:46	#3
R.D. Silverman Nov 2003 2²×5×373 Posts	ECM on Mersenne numbers Allow me to offer some advice and to suggest a (perhaps) more fruitful use of CPU time. If a large Mersenne number has been shown to have no factors under (say) 2^60, then trying to find a factor with ECM will require a very large expenditure of CPU time with little chance of success. I won't discuss the math behind this except to suggest that interested parties read my joint paper with Sam Wagstaff Jr: A Practical Analysis of the Elliptic Curve Factoring Algorithm Mathematics of Computation (1993) To find a factor in the (say) 25-30 digit range will require 100 to 200 curves with first ECM limit of around 100,000. A prior post stated that taking ECM up to about 800 in step 1 required 1200 seconds for exponent near 20M. Step 1 time is linear in the bound, so taking one curve to limit 100K will take ~42 hours. Step 2 will roughly double this, so one curve will take "about" 3.5 days. 100 curves will take 1 year. This will give (roughly) a chance of about (1-1/e) of finding a 25 digit factor IF IT EXISTS. May I suggest (and ask) that if you want to try ECM, then you help out with trying to find factors from the Cunningham project. (i.e. exponent less than 1200). It would be useful to those who are working on the Cunningham project if all 2^n-1 (and 2^n+1) were tested with ECM up to 50 digit factors before we run NFS on them. Please. We really could use help on this. For a list of what has been done, see http://www.mersenne.org/ecm.htm. Indeed, perhaps we might even find a 60 digit factor of one of these numbers; something that has not been done before. Good hunting.