New ECM record: up to 60 digits =============================== On December 26, 1999, Nik Lygeros and Michel Mizony, two math researchers from Lyon (France), found a prime factor of 54 digits of a 127-digit composite number with GMP-ECM, a free implementation of the Elliptic Curve Method (ECM). According to the table maintained by Richard Brent [1] this is the largest prime factor ever found by ECM. The previous record was hold by Conrad Curry with a 53-digit prime found in September 1998. The number Lygeros and Mizony factored was a cofactor from (6^43-1)^42+1, more precisely n = b^4-b^2+1 where b = 6^43-1. It was known that n = 13 * 733 * 7177 * c127 where c127 is a 127-digit composite number. Lygeros and Mizony discovered that this number factors into c127 = p54 * p73 where p54 = 484061254276878368125726870789180231995964870094916937 is the factor found. This search was done in a huge factoring project Lygeros and Mizony started a year ago about generalized Sloane's sequences [2]. Those generalize sequences A003504, A005166 and A005167 from The Encyclopedia of Integer Sequences [3]. The Elliptic Curve Method was discovered by H. W. Lenstra in 1985. The lucky curve was of the form b*y^2*z = x^3 + A*x^2*z + x*z^2 with A = 422521645651821797908421565743985252929519231684249666 mod p, and group order 2^3*3^2*13*53*283*337*29077*837283*1164803*3978523*7613819*8939393*13323719. Very surprisingly, the 54-digit prime was found in step 1 of ECM! The first limit used was B1=15,000,000. The probability of finding a 54-digit prime in step 1 with such parameters is about one over three million. Lygeros and Mizony just did 1300 curves. The lucky curve took 454 seconds to compute on a 500Mhz Dec Alpha EV6 (21264) from the CDCSP (Center for the Development of Parallel Scientific Computation). The program used was version 4a of GMP-ECM [4], a free implementation of the Elliptic Curve Method based on T. Granlund's GMP multiprecision library [5]. According to [1], GMP-ECM now holds four from the ten largest factors ever found by ECM. Other main projects using GMP-ECM are the Cunningham project [6] and the ECMNET client/server [7]. In a recent paper [8], Richard Brent extrapolates the ECM record to be of D digits at year about 9.3*sqrt(D)+1932.3. This would give a record of D=60 digits at year Y=2004. We strongly believe 60 digits will be reached before, perhaps already in 2002 or even this year! Paul Zimmermann [1] ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/champs.txt [2] http://www.desargues.univ-lyon1.fr/home/mizony/premiers.html [3] http://www.research.att.com/~njas/sequences [4] http://www.loria.fr/~zimmerma/records/ecmnet.html [5] http://www.swox.com/gmp/ [6] http://www.cerias.purdue.edu/homes/ssw/cun/index.html [7] http://www.interlog.com/~tcharron/ecm.html [8] Some Parallel Algorithms for Integer Factorisation, Euro-Par 99, cf ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb193.dvi.gz