Article: 56165 of sci.crypt Path: news.usyd.edu.au!news1.optus.net.au!optus!news.mpx.com.au!nsw.nnrp.telstra.net!intgwpad.nntp.telstra.net!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.tli.de!newsfeed01.btx.dtag.de!newsfeed00.sul.t-online.de!t-online.de!news-MUC.ecrc.net!news-raspail.gip.net!news.gsl.net!gip.net!grolier!fr.usenet-edu.net!usenet-edu.net!ciril.fr!loria.fr!not-for-mail From: Paul Zimmermann Newsgroups: sci.math.symbolic,sci.math,sci.crypt Subject: New ECM record: up to 60 digits Date: 05 Jan 2000 17:11:27 +0100 Organization: LORIA & INRIA-Lorraine - Nancy - FRANCE Lines: 63 Message-ID: NNTP-Posting-Host: leibniz.loria.fr Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Newsreader: Gnus v5.5/Emacs 20.3 Xref: news.usyd.edu.au sci.math.symbolic:32313 sci.math:353400 sci.crypt:56165 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! [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 -- Paul Zimmermann INRIA Lorraine 615 rue du Jardin Botanique F-54602 Villers-les-Nancy Cedex