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