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