From Paul.Zimmermann@loria.fr Thu Jul 2 11:22:05 1998
Date: Wed, 24 Jun 1998 14:32:47 -0400
From: Paul Zimmermann
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: 1078825191548640568143407841173742460493739682993
1078825191548640568143407841173742460493739682993
June 24, 1998, Nancy, France. According to Richard Brent's "champs.ecm" file
[1], the above number of 49 digits is the largest new prime factor found so
far with the Elliptic Curve Method (ECM). It is a factor of 2^1071+1, and it
was known before that
2^1071+1 = (2^357+1) * 3 * 19 * 6427 * 17137 * 119953 * 123931 * 1340000929
* 26159806891 * 77158673929 * 27439122228481 * 49697164752429114523
* c132
where c132 stands for a composite number of 132 digits. The previous record
was a factor of 48 digits of 24^121+1 found by Richard Brent on Oct 9, 1997.
The new record was found June 19, 1998, on a R10K processor from the Silicon
Graphics Power Challenge Array from the Centre Charles Hermite [3], a center
for high-performance computations in Nancy.
The Elliptic Curve Method. Invented by H. W. Lenstra Jr in the mid 80's [4],
this algorithm is currently the best-known method to find reasonably small
factors (up to 40 digits) in large composite numbers (140 digits or more).
Indeed, unlike other methods (the Quadratic Sieve or the Number Field Sieve),
the complexity of ECM mainly depends on the size of the smallest prime factor
of the input number, and not on the input number size. Several improvements
to the original method were proposed, among them the FFT extension from Peter
Montgomery [2]. Richard Brent used this method to complete the factorizations
of the Fermat numbers F10 and F11 [5].
Technical details. The above p49 factor was found using Peter Montgomery's
ecmfft program [2], with first limit B1=50,000,000. This binary was specially
designed to find factors in the 50-digit range. It has an equivalent 2nd
phase limit of about B2=1.7*10^11. Such a binary will find a factor whenever
the corresponding elliptic curve group order has its largest factor less than
B2 (in fact, as ecmfft uses the birthday paradox continuation, it may find
factors larger than B2, whence the word "equivalent" above), and its second
largest factor less than B1. The lucky curve was of the form
b*y^2*z = x^3 + A*x^2*z + x*z^2
with A=264516088570649034570750958281483585100784947400, and has group order
g=2^6*29*68737*210631*348989*746153*2010977*28393447*2700196643. One such
curve takes about 2.7 hours on a R10K processor, and the average number of
curves to find a 49-digit factor is about 5700, assuming such a factor exists.
This record factorization was obtained during an attempt to factor the about
75 remaining composite numbers from 120 to 135 digits from the Cunningham
table, maintained by Sam Wagstaff. About 55 curves were tried on the c132
cofactor of 2^1071+1, which decomposes as c132 = p49 * p84, where p84 denotes
a prime number of 84 digits.
This record may not hold very long, as several very efficient implementations
of ECM are available today, for example the Windows implementation of George
Woltman (the fundator of the GIMPS project) for Mersenne numbers, one other
implementation from Richard Crandall for Fermat numbers, or the GMP-ECM
implementation used by the ECMNET project. All those implementations are
available from the ECMNET home page [6].
Paul Zimmermann
Polka project
INRIA Lorraine and LORIA, Nancy
[1] ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/champs.ecm
[2] An FFT extension of the Elliptic Curve Method of Factorization, by Peter
Montgomery, PhD dissertation, 1992. Available from
ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz
[3] http://www.loria.fr/CCH
[4] Factoring integers with elliptic curves, by H. W. Lenstra Jr, Annals of
Mathematics 126 (1987), n. 3, 649-673, 2nd series.
[5] Factorization of the tenth and eleventh Fermat numbers, by Richard Brent,
ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb161tr.dv
i.gz,
to appear in Mathematics of Computation.
[6] http://www.loria.fr/~zimmerma/records/ecmnet.html