English | Italian | Russian |

 

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ⁿ+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.

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₂₀) we can check for factors up to 60 digits long!

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 first parameter is the exponent of our Fermat number to test. Different implementations of ecm software require to input the number as a power of 2 or as a (very long) integer.
The second parameter represents the number of curves to run. For Fermat numbers you can just take a look at the table below.
The third and fourth parameters represent the bounds applied to the curve: usually B2 = 100*B1.
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

 

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₁₄ 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₁₄ using Prime95 24.6 on a 2.66GHz P4:
 

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.