What's ECM?

[alpertron]

Originally Posted by R.D. Silverman

You really need to learn how to discuss mathematics. You especially need to learn how to use quantifiers.
I discussed TYPICAL B2 values. I did not discuss anywhere whether these B2 values were OPTIMAL. (your apparent
interpretation of what I said.)

Learn to read. Learn how NOT to misquote others. Learn how NOT to put words in other peoples mouths. Learn how
[i]not[/b] to change their choice of quantifiers in your subsequent discussions.

Over a very wide range of factor sizes being sought , ECM behaves very much like an O(p^1/5) algorithm. Read the
"Practical Analysis" paper.

The choice of OPTIMAL B2 also depends on what optimization is being performed. If maximizing the probability of
success per unit time spent the analysis also assumes that one is going to perform a COMPLETE computation
for the parameter choices. Very few people perform a complete set of curves when looking for a p60 factor
among composites currently under consideration. OTOH, if one is going to spend a FIXED (or a priori bounded) amount
of time, the optimal B2 (and B1) will be different. If one performs a full (say) t60 search, finds nothing, then performs
a second t60 search it then means (post computation) that one has made sub-optimal B1, B2 choices.

Furthermore, the choice of OPTIMAL parameters very much depends not only on the underlying mathematical
theory but also upon practical matters: How much memory is there? What is its latency? How much L1, L2, L3
cache is available? If running on a multi-core processor, how many cores are running simultaneously? How much
cache contention is there? If running on multiple cores is there enough memory to allow the algorithm to
perform optimally? There certainly won't be enough cache.

My entire discussion throughout this thread has been to discuss typical choices. You have chosen to put
different words in my mouth. STOP.

Yes, I read several books and papers about ECM, and I also implemented the algorithm in Java (see http://www.alpertron.com.ar/ECM.HTM with Firefox or IE, not Chrome). The problem with Java is that you do not have control of what goes to the cache. For example, in my SIQS implementation in the same applet, I used smaller factor bases than expected in most papers, so it could fit on caches L1 and L2 for Core 2 processors.

The typical choices you mention are for current numbers being factored on Cunnigham Project. Here in this thread I was responding to LaurV who talked about running ECM on a Mersenne number with known p19 factor using extremely small values of B1 and B2 (with his selection, almost no step 2 was being done). So the running time for this will not be typical.

[R.D. Silverman]

Originally Posted by alpertron

The typical choices you mention are for current numbers being factored on Cunnigham Project.

Very few people are still trying ECM on Cunningham numbers. (Sam, Bruce, anyone else?)

Here in this thread I was responding to LaurV who talked about running ECM on a Mersenne number with known p19 factor using extremely small values of B1 and B2 (with his selection, almost no step 2 was being done). So the running time for this will not be typical.

"almost no step 2 was being done" says a lot about the choice of B1........ (think about it!)

Furthermore, Richard Guy's strong law of small numbers applies here. The numbers involved are too small to expect
that any kind of 'optimal' selection process is correct simply because Dickman's function is not very accurate for
numbers this small.

If one measures 'typical' by how much work is currently being done (whether measured by CPU time or number of curves or other
measure), one will find by far that the typical use of ECM these days involves using it to split cofactors during NFS runs.
For this application the choice of B1, B2 will be TINY.

[LaurV]

Would you two stop, at least until I finish to read what you both wrote?
I am sorry I may have said some stupid thing that started all this discussion. We all recognize that you both know what you are talking about, now give us few moments to catch up.

[aurashift]

Originally Posted by LaurV

I am sorry I may have said some stupid thing that started all this discussion. We all recognize that you both know what you are talking about, now give us few moments to catch up.

+1