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