The ECMNET Project [Lehigh page]

[quick start]   [client/server setup]   [top 50]   [Cunningham project]   [champions for ECM, P-1, P+1]   [NFSNET]
News:
  • [** 2 January 2005: this page extracted and trimmed (without permission) from an actual ECMNET page; for the current version see [ECMNET] **]
  • 31 October 2003: a new ecm record: a 58-digit factor from 8*10141-17 was found by R. Backstrom using gmp-ecm.
  • 31 October 2003: a new P-1 record: a 57-digit factor from 6396+1 was found by P. Zimmermann using gmp-ecm. This was (for a few hours only) a new overall record for ecm and P-1.
  • [** 21 June 2003: the previous ecm record: a 57-digit factor from 2997-1, found by B. Dodson using prime95 (cf. mprime, below). The above list of ecm records restricted to numbers hard to factor, ECM, still lists this factor in first place. See also [p57post]. **]
    • GMP-ECM Top Ten for 2004

    GMP-ECM Top Ten for 2004

    digits factor from B1 sigma date who
    55 7523020307427066273763456609903850552762967576510974081 10260+1 43e6 3933468262 24 Jun 2004 B. Dodson
    55 1268413494411135671239686038243358243539607519968737801 31557+1 43e6 1073421943 18 Nov 2004 K. Aoki
    54 477350833522476258826705274670317082147893737193497151 3577-1 43e6 1939606094 10 May 2004 K. Aoki
    53 54093886887062230599082516017052647105427126977713417 3508+1 43e6 1988971643 06 Jun 2004 B. Dodson
    53 42156379589779912226383108151000450094080783333678881 2845+1 43e6 2242386807 20 May 2004 B. Dodson
    53 33961207341909494975722524207839732407744380168756907 3*2653-1 860500 879193285 07 Oct 2004 R. Backstrom
    53 18489093999230985031269595355473053970276854216314509 7286+1 43e6 1937590108 27 Jul 2004 B. Dodson
    53 11984437123431823969432655822865428382472038412325377 11473+1 43e6 3782281521 15 Jul 2004 K. Aoki
    51 738313998235889565301599572531640626810525425999201 2984+1 11e6 1073040516 26 May 2004 R. Keiser
    51 197093734279293731287445626494587381600438850930731 5665-1 43e6 2891223763 08 Nov 2004 B. Dodson

    Lehigh's Beowulf. Dodson's factors above, five of the top ten for the year, were found using a beowulf cluster at Lehigh. During November 1, 2003 to December 31, 2004 there were 122 Cunningham factors found by ECMNET, of which 42 were found by Dodson using the cluster. Dodson intends a more narrowly focused effort on factors of 50 digits or more in 2005. An analysis of the ECM efforts for the year 1998, when the first factor of more than 49 digits was found, is given in Champs. The count of 40 - 49 digit factors was Dodson 22; Zimmermann 18; Montgomery 12, but the only factor that counted was Curry's 53 digit factor. (These earlier factors of Dodson were found using binaries of Montgomery's ECM/FFT program, below.) See also the all-times all-ecm-programs top-50 table, and the gmp-ecm top ten from 1998, 1999, 2000, 2001, 2002, 2003.

    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 by 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.

    Goal. 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. A new record was set by Nik Lygeros and Michel Mizony, who found in December 1999 a prime factor of 54 digits using GMP-ECM.

    Free implementations of ECM.

  • giantint from Richard Crandall, Perfectly Scientific, Inc., with special code for Fermat numbers.
  • mprime from George Woltman, is restricted to divisors of 2^n-1, but is very fast because it uses DFT with O(n log n) multiplication.
  • gmp-ecm from Paul Zimmermann, based on the GMP multiprecision library. Other binaries are available through T. Granlund's ftp site and a new CygWin binary.

    Bibliography. To know how ECM works and the history of the factorization of Fermat numbers by ECM and other methods, look at the paper Factorization of the tenth Fermat number by Richard Brent. Looking at the old paper Some Integer Factorization Algorithms using Elliptic Curves you'll see that very few improvements were made to ECM since 1985. One of these improvements is the FFT continutation invented by Peter Montgomery, and detailed in his dissertation entitled An FFT extension of ECM. You might also look at the paper A Practical Analysis of the Elliptic Curve Factoring Algorithm, by Bob Silverman and Sam Wagstaff, Mathematics of Computation vol. 61, July 1993. People reading german may look at Franz-Dieter Berger's Diplomarbeit entitled ``ECM Faktorisieren mit elliptischen Kurven''. Finally, have a look at the FactorWorld page from Scott Contini.