Friday, March 13, 1998 I'm happy to announce the factorization of the 2^599-1, the current smallest unfactored Mersenne number according to the table [1] maintained by Will Edgington. It was also the 2nd hole in the 2^n-1 Cunningham table, the 1st hole still being 2^589-1: 2^599-1 = 16659379034607403556537 * 148296291984475077955727317447564721950969097 * prp114 The first factor of 23 digits was already known, leaving a composite number of 159 digits. The second factor of 45 digits was found using GMP-ECM, a GMP-based implementation of the Elliptic Curve Method from H. W. Lenstra Jr, freely available from the ECMNET page [2]. The Elliptic Curve Method (ECM for short) is currently the best known algorithm to find not-too-large factors of composite numbers, i.e. up to about 50 digits. Indeed, the complexity of ECM depends primarily on the size of the smallest prime factor of the input composite number, rather than on the total size of the input number, as it is the case for the Quadratic Sieve and the Number Field Sieve. The idea of the Elliptic Curve Method is to choose a random elliptic curve b*y^2 = x^3 + a*x^2 + x over Z/nZ where n is the number to factor. Pick a random starting point P on that curve. Using the group addition formula on the curve, compute Q=m*P where m is the product of all primes up to a limit B1, called "1st limit". Then one computes q*Q for each prime q between B1 and a limit B2, called "2nd limit". If the group order of the elliptic curve (considered now modulo a factor p of n) is smooth, i.e. all its prime factors are less than B1, except perhaps one which is less than B2, then one of these q*Q will give the group identity element, and a gcd will reveal the factor p of n. There exist several variants of ECM, among them Brent's birthday paradox variant and Montgomery's fft variant [5]. We used here B1=3,000,000 and B2=100*B1=300,000,000. The elliptic curve chosen at random used sigma=1604840403 with Montgomery's parameterization [4], which corresponds to a=20199020443226336765465577085303774026731166 for the elliptic curve modulo p. The corresponding group order is: g = 2^7*3^2*373*3673*40927*96097*661883*1179109*1260317*24289207 which has all its prime factors less than B1, except 24289207 which is less than B2. The lucky curve was the 33th with B1=3,000,000, after 1295 unsucessful curves with B1=1,000,000. The lucky machine was a Silicon Graphics R10k processor from the Power Challenge Array of the Centre Charles Hermite in Nancy. GMP-ECM on such a machine does one curve with B1=3,000,000 for a 159-digit number in about 870 seconds. The above p45 (prime factor of 45 digits) is the 5th largest factor found by ECM so far, according to Richard Brent's "champions" table [3], after a p48 of 24^121+1 found by Brent, two p47's of 30^109-1 and 5^256+1 found by Peter Montgomery, and a p46 of Lucas(769) found by Montgomery too. It is also the 11th champion (prime factor of 40 digits or more) found in 1998. I'd like to thank Richard Brent for his very nice paper [4] which helped a lot to implement GMP-ECM, Peter Montgomery for many useful discussions, for checking the above group order, and for his challenging ecmfft implementation, and Torbjorn Granlund for making GMP freely available. Paul Zimmermann Loria, Nancy, France [1] Will Edgington, Table of factors of Mersenne numbers, http://www.garlic.com/~wedgingt/lowM.txt [2] Paul Zimmermann, The ECMNET Project, http://www.loria.fr/~zimmerma/records/ecmnet.html [3] R. P. Brent, Large Factors Found by ECM, ftp://nimbus.anu.edu.au/pub/Brent/champs.ecm [4] R. P. Brent, Factorization of the tenth and eleventh Fermat numbers, ftp://nimbus.anu.edu.au/pub/Brent/rpb161tr.dvi.gz [5] P. L. Montgomery, An FFT Extension of the Elliptic Curve Method of Factorization, Dissertation, University of California, Los Angeles, 1992 ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz ############################################################################## GMP-ECM version 2e, by P. Zimmermann (Inria), February 1998, with many contributions from T. Granlund and P. Leyland. Input number is 124539923134619429718018353168641490719788526741873602224103589351798060075728544650990190016536810151633233676972068237330360238752628542584228856301923448951 recognized factor of 2^599-1 Using special base-2 division (1.75 faster) Using B1=3000000 and sigma=1604840403 A=14273382889677782864358427947782367577676627285399805669575226028138204402452782036390616768585639889571687705092859653119956739992820606195640641408295255627 starting point: x=69122016432760864897602418722313720232115500827308287516676877397290645535965082577932331909600860327643476893741831576033308040859153071786405914140205685309 Step 1 took 602117ms for 45778516 muls, 2 gcds, 2 gcdexts start step 2 with B1=3000000, B2=300000000, D=12248 x=60932563121890305952835424485915380271254051757114228906519112568628421539117945474874590632114552637392833688526233229958291545064784022471206551680465896382 initialization of Step 2 took 5487ms ********** Factor found in step 2: 148296291984475077955727317447564721950969097