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