New ECM record with 54 digits

N. Lygeros




The above 54-digit factor of (6^43-1)^42+1 is the new record for the largest factor found by ECM on December 26, 1999. The previous record was a 53 digit factor of 2^677 - 1 found by Conrad Curry on September 14, 1998 and the previous record was a 49 digit factor of 2^1071+1 found by Paul Zimmermann on June 19, 1998.

History. Richard Brent has predicted in 1985 in a paper entitled Some Integer Factorization Algorithms using Elliptic Curves that factors up to 50 digits could be found by the Elliptic Curve Method (ECM). Indeed, Peter Montgomery found in November 1995 a factor of 47 digits of 5^256+1, and Richard Brent set in October 1997 a new genuine record with a factor of 48 digits of 24^121+1.

The original purpose of the ECMNET project was to make Richard's prediction true, i.e. to find a factor of 50 digits or more by ECM. This goal was attained on September 14, 1998, when Conrad Curry found a 53-digit factor of 2^677-1 c150 using George Woltman's mprime program. The new goal of ECMNET is now to find other large factors by ecm, mainly by contributing to the Cunningham project, most likely the longest, ongoing computational project in history according to Bob Silverman. The Cunningham project is described in the following excerpt from a sci.math posting by Bob Silverman, who has contributed many of the factorizations. In 1925 Lt.-Col. Alan J.C. Cunningham and H.J. Woodall gathered together all that was known about the primality and factorization of such numbers and published a small book of tables. These tables collected from scattered sources the known prime factors for the bases 2 and 10 and also presented the authors' results of thirty years' work with these and the other bases.

Since 1925 many people have worked on filling in these tables. It is likely that this project is the longest, ongoing computational project in history. D.H. Lehmer, a well known mathematician who passed away in 1991 was for many years a leader of these efforts. Professor Lehmer was a mathematician who was at the forefront of computing as modern electronic computers became a reality. He was also known as the inventor of some ingenious pre-electronic computing devices specifically designed for factoring numbers. These devices are currently in storage at the Computer Museum in Boston.

Result. Input number is
1016306709671193366455664959650795243281414526493491827044789465193046042487698662851664697620567076330351101340248184365348097 (127 digits)
Using B1=15000000, B2=5188485120, polynomial x^60, sigma=599841120
Step 1 took 453516ms for 196039890 muls, 3 gcdexts
********** Factor found in step 1: 484061254276878368125726870789180231995964870094916937
Found probable prime factor of 54 digits: 484061254276878368125726870789180231995964870094916937
Probable prime cofactor 2099541536720217916793625797492307860357351911231978329066474541503922681 has 73 digits

References. ECMNET, Top100, p53, Champions Primes.







free counters


Opus