Nancy, December 16, 1999
Dear ecm friends,
after a long break (the last newsletter is from April), here are some news
from the 'ecm front'. First please tell me if you want to be removed from
my mailing list. Anyway, I promise it will be the last newsletter from this
year, since I go into vacation today...
a. New large ecm factorizations
1999 was a great year for ecm. The 53-digit record established by Conrad
Curry in 1998 was not beaten, however 5 from the 10 largest factors ever
found by ecm were found this year [1]. To enter that top-ten, a factor of
at least 48 digits is now needed!
As for gmp-ecm, it contributes to 4 of the 10 "champions", with one factor
of 50 digits eventually found in October. The gmp-ecm 1999 top-ten goes
from 46 to 50 digits, and the all-times top-100 starts from 41 digits! [2]
b. The client/server EcmNet project
It factored several Cunningham, Cullen or Woodall numbers in 1999. See
[3] for more details. The largest factor ever found by gmp-ecm (a p50 from
3^1179+1) was precisely found by the client program written by Tim Charron,
and connected to the master server maintained by Paul Leyland.
c. New version of gmp-ecm
A new version (4c) of gmp-ecm is now available. The main difference with
the last version (4b) is an improvement of about 33% in step 2, and an
overall improvement of 12% to 21% depending on the machines. This release
comes (thanks to Torbjo"rn Granlund) with a binary for 64-bit HP machines
(most wanted by some of you) and a binary for Windows NT (thanks to Paul
Leyland) should be soon available (one for version 4b is already there).
This new version performs in less than one minute on a 500Mhz Alpha 21264
(aka Compaq XP1000) a curve with first limit one million and 2nd stage
limit greater than 200 million on a c120:
GMP-ECM 4c, by P. Zimmermann (Inria), 16 Dec 1999, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac,
A. Yamasaki, and the invaluable help from P.L. Montgomery.
Input number is 265535466579688604805851295242389350646124229512840469920696404242681668380354424870495084413250865968329058772250534133 (120 digits)
Using B1=1000000, B2=234709020, polynomial x^12, sigma=191056488
Step 1 took 29202ms for 12982265 muls, 3 gcdexts
Step 2 took 17673ms for 5626744 muls, 17038 gcdexts
d. Other news.
Conrad Curry re-created the NFSNET project [9], whose goal is to factor
Cunningham numbers using the Number Field Sieve. NFSNET factored quite
a few numbers in 1999, nicely completing the EcmNet work.
Of course you all know about the new Mersenne prime 2^6972593-1 discovered
by GIMPS in June [5], the 512-bit RSA key broken in August [6], and the
ECC2-97 Certicom challenge broken in September [7]. You perhaps don't know
that Perfectly Scientific Inc. (PSI) offers prizes for new factors of Fermat
numbers [4]. Also, Robert Harley's team strikes again by attacking the
ECC2K-108 Certicom challenge [8]; they are at about 3% of the expected number
of points (1.3M). If you have some free cpu cycles, please donate them
either to EcmNet, to NFSNET or to ECC2K-108!
[1] ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/champs.txt
[2] http://www.loria.fr/~zimmerma/records/ecmnet.html
[3] http://www.interlog.com/~tcharron/factors.html
[4] http://www.perfsci.com/prizes.html
[5] http://www.mersenne.org
[6] http://www.cwi.nl/~kik/persb-UK.html
[7] http://www.certicom.com/sixth.htm
[8] http://cristal.inria.fr/~harley/ecdl7/
[9] http://orca.st.usm.edu/~cwcurry/nfs/nfs.html