ECM FACTORING

Since the start of Fermatsearch project, users have been requested to offer CPU cycles to factoring purposes.

We gathered people from all over the world, using different factoring programs as **Fermat.exe**,
**Proth.exe**, **PFGW.exe**, **GMP-Fermat.exe**, **MFAC.exe**
and many more.

All these programs have been written using different developments of the same trial-factoring algorithm:
given a range of N, a range of k and a factor representation **k*2 ^{n}+1**, test all the possible
factors in that range.

It is a deterministic algorithm: we are assured that no more factors can be found once the range has been totally searched. All we can do is deepen the range, choosing higher k ranges, or changing our N.

The bad news: the time to complete a range grows as the range is increased, no matter what heuristics are used to lower the number of potential factors.

The good news: we may use different factoring algorithms for those Fermat numbers that reached high levels of trial-factoring.

What is ecm and how does it work?

ECM is the acronym for Elliptic Curves Method.

The history of what are called elliptic curves goes back well more than a century. Originally developed for clssical analysis, elliptic curves have found their way into abstract and computational number theory. Like the prime numbers themselves, elliptic curves have the wonderful aspect of elegance, complexity and power. Elliptic curves are not only celebrated algebraic constructs; they also provide considerable leverage in regard to prime number nd factorization study.

The method is not deterministic, because you cannot tell if a factor is present after the calculation of a number of "curves". But what is a curve? In ecm, points over an elliptic curve are "mapped" to numbers: calculating a curve is roughly the same as checking for a factor.

It is considered a statistic method, as the algorithm evaluate the probability of finding a factor after the calculation of
a number of curves with definite bounds. As bounds increase, the probability of finding a bigger factor grows.

The bad news: this method requires **huge** amounts of phisical memory.

The good news: for small Fermat numbers (up to F_{20}) we can check for factors up to 60 digits long!

Ecm parameters

To evaluate the chances of a factor, four parameters are needed:

- The exponent to check
- The number of curves
- The lower bound B1
- The upper bound B2

The

The

The

The higher the bounds, the higher the memory request, the higher the time requested for each curve, the higher the factor you may find out.

Digits in factor | 25 | 30 | 35 | 40 | 45 | 50 | 55 | 60 |
---|---|---|---|---|---|---|---|---|

Bound #1 | 50,000 | 250,000 | 1,000,000 | 3,000,000 | 11,000,000 | 44,000,000 | 110,000,000 | 260,000,000 |

Curves to test | 280 | 640 | 1,580 | 4,700 | 9,700 | 17,100 | 46,500 | 112,000 |

Ecm reservation

Of course you don't need to know all the mathematical background that lies under the ecm.

All you need to do to join this search is download a program (prime95,
written by George Woltman, perfectly suits the need), input the parameters and run. Read the ecm_howto file to learn how to start, and download the file lowp.txt: this fie must reside in the same folder where Prime95.exe is.
When you run your curves, send the **results.txt** file to me: and I'll add your results to the project and contact George Woltman.

To correctly choose the parameters, go to this link or look at this excel file, and choose the B1 bounds that fulfil your needs (obviously, curves that are "done" don't need to be "rerun").

As a matter of neatness, I would like to receive ECM curves done grouped by at least 10: it will be easier for me and George Woltman to take care of the ECM ranges if they don't arrive in sparse mode.

On the next table you will find some timings for ecm on F_{14} using GMP-ECM on a 2.4GHz AMD64 with large B2 bounds.

Digits | B1 | B2 | mem | stage 1 ms | stage 2 ms |
---|---|---|---|---|---|

15 | 2,000 | 119,805 | 8 | 2,430 | 2,608 |

20 | 11,000 | 1,359,460 | 15 | 13,530 | 11,881 |

25 | 50,000 | 11,757,135 | 33 | 61,789 | 51,133 |

30 | 250,000 | 116,469,998 | 97 | 310,837 | 249,851 |

35 | 1,000,000 | 839,549,780 | 249 | 1,247,434 | 963,127 |

40 | 3,000,000 | 4,016,636,514 | 544 | 3,756,443 | 2,741,624 |

45 | 11,000,000 | 25,577,181,640 | 679 | 13,831,555 | 11,372,366 |

50 | 43,000,000 | 54,934,226 |

Here are times in seconds for one ECM curve (B2=100*B1) on F

Digits | B1 | stage 1 sec | stage 2 sec |
---|---|---|---|

25 | 50,000 | 11 | 6 |

30 | 250,000 | 54 | 25 |

35 | 1,000,000 | 220 | 93 |

40 | 3,000,000 | 661 | 259 |

45 | 11,000,000 | 2408 | 885 |

50 | 43,000,000 | 9533 | 3329 |

For more accurate timings on curves to do, download this excel file.

Copyright © MoreWare 2003 ...