Large Factors Found By ECM
^^^^^^^^^^^^^^^^^^^^^^^^^^
This file (champs.txt) contains information on the "top ten"
factors found by the elliptic curve factoring method (ECM).
Factors are included if they satisfy conditions 1 and 2.
1. They are one of the largest ten factors found so far by ECM
and satisfying condition 2.
2. Let r = length(composite)/length(prime), where
length is measured in decimal digits.
Also, let r' = ln(composite)/ln(prime).
Factors with max(r,r') < 2.2 are excluded as they could probably have
been found more easily by another method such as MPQS, GNFS or SNFS.
For historical interest, we also list factors of at least 40 decimal digits
that satisfy condition 2 and were at any time the largest factor found so
far by ECM ("champions"), even if they are no longer in the "top ten".
Factors which at one time were the current "champions" are indicated by an
asterisk.
I imposed condition 2 from 1 Jan 2004 (r' term added 18 Sept 2005). For large
factors that do not necessarily satisfy condition 2, see Paul Zimmermann's
"top 50" list at http://www.loria.fr/~zimmerma/records/top50.html.
There are no new entries in 2018 or (so far) in 2019. However, a p76 by
Ryan Propper that was found in 2013 has been added to the current list.
I reserve the right to exclude factorizations that were possibly obtained
by "artificial" means. See for example Research Problem 7.27 of the book
"Prime Numbers: a Computational Perspective" by Crandall and Pomerance.
David Broadhurst has shown that this enables us to concoct examples where
ECM finds factors of over 30,000 decimal digits!
This file is available from
http://maths-people.anu.edu.au/~brent/ftp/champs.txt
or via the link at http://maths-people.anu.edu.au/~brent/factors.html
See also Paul Zimmermann's list at
http://www.loria.fr/~zimmerma/records/ecmnet.html
Please send corrections/updates to champs@rpbrent.com
R. P. Brent
http://www.rpbrent.com
===============================================================================
Summary
^^^^^^^
Factor Divides Found by Date
^^^^^^ ^^^^^^^ ^^^^^^^^ ^^^^
p83 YYYYMMDD
^^^
16559819925107279963180573885975861071762981898238616724384425798932514688349020287 *
7,337+ R. Propper (13) 20130908
p79
^^^
6083324092478900951288520916966416595449236017004455695358667500798143293692091
see (25) R. Propper (25) 20170715
2302872188505279576573535015926441913945044975483579529517513795897664211127797 *
11,306+ S. Wagstaff (22) 20120812
p77
^^^
18974159366624817405627752670504479132613571595050983959444958694223874973021
B_188 S. Wagstaff (19) 20130616
p76
^^^
5191873720703506118777751448022113902214321958414685694699686672326450173651
see (15) R. Propper (15) 20130527
p75
^^^
336842026814486816413712532665671525518487238461533945786937785048474675329 *
11,304+ S. Wagstaff (16) 20120803
227432689108589532754984915075774848386671439568260420754414940780761245893
EM47 R. Propper (20) 20120912
131458002966362191339005108102367227220674315637373735378805031970614273439
3541,101- R. Propper (14) 20160420
p74
^^^
26721194531973848954767772351114152203083577206813943149484875628623309473
12,284+ B. Dodson (18) 20141010
p73
^^^
3045900993960286149497147268705305258031860639784227614140251982523294187
11,311- R. Propper (12) 20160207
[end of current top ten]
[following former champions listed for historical interest]
p73
^^^
1808422353177349564546512035512530001279481259854248860454348989451026887 *
2,1181- J. Bos et al (21) 20100307
p68
^^^
42593783346150223186979443437882164324892008462850480008134130873603 *
64*10^341-1 yoyo@home/M.Thompson (17) 20091228
p67
^^^
4444349792156709907895752551798631908946180608768737946280238078881 *
10,381+ B. Dodson (24) 20060824
p66
^^^
709601635082267320966424084955776789770864725643996885415676682297 *
3,466+ B. Dodson (23) 20050406
p59
^^^
20131492120828919814484857298874674155298711142397769181347 *
10,233- B. Dodson (11) 20050220
p57
^^^
167560816514084819488737767976263150405095191554732902607 *
2,997- B. Dodson (10) 20030621
p55
^^^
1139151258261034615880135106860446479526482959089061629 *
93^56+56^93 P. Gaudry (9) 20021213
p54
^^^
484061254276878368125726870789180231995964870094916937 *
(6^43-1)^42+1 Note (8) 19991226
p53
^^^^
53625112691923843508117942311516428173021903300344567 *
2,677- C. Curry (7) 19980914
p49
^^^
1078825191548640568143407841173742460493739682993 *
2,1071+ P. Zimmermann (6) 19980619
p48
^^^
662926550178509475639682769961460088456141816377 *
24,121+ R. P. Brent (5) 19971009
p47
^^^
12025702000065183805751513732616276516181800961 *
5,256+ P. Montgomery (4) 19951127
p44
^^^
27885873044042449777540626664487051863162949 *
p(19069) Berger-Mueller (3) 19950621
p43
^^^
5688864305048653702791752405107044435136231 *
p(19997) Berger-Mueller (3) 19930320
p42
^^^
184976479633092931103313037835504355363361 *
10,201- D. Rusin (2) 19920405
p40
^^^
1232079689567662686148201863995544247703 *
p(11279) Lenstra-Dixon (1) 19911028
Notes
^^^^^
Factors divide numbers of the form a^n +- 1 (abbreviated a,n{+-})
or partition numbers (p(n) is the n-th partition number)
or other numbers described in the notes.
Dates are in YYYYMMDD format.
(1) Arjen Lenstra and Brandon Dixon on a MasPar (the first p40 by ECM).
c89 = p40*p50, r = 2.22.
(2) David Rusin using Peter Montgomery's program. c111 = p42*p70, r = 2.64.
(3) Franz-Dieter Berger and Andreas M\"uller on a network of workstations.
c99 = p44*p55, r = 2.25 and c139 = p43*p96, r = 2.85.
(4) Peter Montgomery on an SGI workstation. c134 = p47*p88, r = 2.85.
(5) Richard Brent on a Fujitsu VPP300. c130 = p48*p82, r = 2.71.
(6) Paul Zimmermann on an SGI Power Challenge with Montgomery's program.
c132 = p49*p84, r = 2.69.
(7) Conrad Curry with George Woltman's mprime program using 16 Pentiums.
c150 = p53*p98, r = 2.83.
(8) Nik Lygeros and Michel Mizony with GMP-ECM. The input composite was
c127 = (b^6+1)/(b^2+1)/13/733/7177, b = 6^43-1.
c127 = p54*p73, r = 2.37.
(9) Pierrick Gaudry with GMP-ECM. c121 = p55*p67, r = 2.2.
(10) Bruce Dodson using George Woltman's Prime95. c301 = p57*p244, r = 5.28.
(11) Bruce Dodson with GMP-ECM, c162 = p59*c103, r = 2.75.
(12) Ryan Propper with GMP-ECM, c323 = p73*c251, r = 4.42.
(13) Ryan Propper with GMP-ECM 6.4.3, B1=7600000000, B2=324909696561468,
c237 = p83.p155, r = 2.86. 7^337+1 was a Cunningham "first hole".
(14) Ryan Propper with GMP-ECM 6.4.4, c355 = p75.c281, r = 4.73.
(15) Ryan Propper, p76 is a factor of 175^175+176^176. This factor was found
in 2013 but accidentally omitted from our lists until 2019. We have not
retrospectively updated the entries for 2013-2018.
(16) Sam Wagstaff with GMP-ECM 6.4, c181 = p75*p107, r = 2.41.
(17) yoyo@home/M.Thompson with GMP-ECM, c296 = p68*p229, r = 4.35.
c296 is a factor of 64*10^341-1,
see http://hpcgi2.nifty.com/m_kamada/f/c.cgi?q=71111_341
(18) Bruce Dodson/ECMNET, c252 = p74.c179, r = 3.41.
(19) Sam Wagstaff with GMP-ECM 6.4, c193 = p77.p117, r = 2.51.
B_188 is the numerator of the Bernoulli number B188.
(20) Ryan Propper with GMP-ECM 6.4.2, c256 = p75.p181, r = 3.41.
EM47 is related to the Euclid-Mullin sequence.
(21) Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, Peter Montgomery,
c291 = p73.p218, r = 3.99.
"Some details of this computation:
We used GMP-ECM with some modifications so we can run stage 1 on
a cluster of PlayStation 3 game consoles (PS3) and stage 2 on a
cluster of regular processors."
(22) Sam Wagstaff with GMP-ECM 6.4, c191 = p79*p113, r = 2.42
About 600 curves with B1 = 800000000.
(23) Bruce Dodson with GMP-ECM 6.0 on an Opteron cluster,
c180 = p66*p114, r = 2.73.
(24) Bruce Dodson with GMP-ECM 2006-03-13 [using GMP 4.1] on an Opteron
cluster, c214 = p67*p147, r = 3.19.
(25) Ryan Propper with GMP-ECM 6.4.4, factor of c199 Aliquot 276, index 2063,
c199 = p79.p120, r = 2.52. B1=7600000000, B2=324909696561468.
================================================================================
Information on Curves and Group Orders
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
If g is the order of the group used to find the factor, the following table
gives the second-largest prime factor (g2) and the largest prime factor (g1)
of g, where known.
In some cases the exact values are not known, but bounds can be given from
knowledge of the phase 1 and phase 2 limits. This is indicated by the "<"
and ">" symbols.
The values of g2 and g1 have been deduced from information supplied by
various (generally reliable) people, and have not been verified
independently in all cases.
C = C(g1,g2) = 1/mu, where mu is an estimate of the probability that a
random integer close to p/12 has largest prime factor at most g1 and
second-largest prime factor at most g2. Thus, C is an estimate of the
expected number of curves to find the factor with phase 1 limit g2 and
phase 2 limit g1. This assumes that the curves are chosen so that the group
order is divisible by 12, which was not always the case for the computation
which found the factor. It also assumes that group orders behave like
random integers (apart from being a multiple of 12). Finally, C is computed
by an approximation that is accurate in the limit as the group order tends
to infinity, but may be inaccurate for integers as "small" as factors found
by ECM. The larger C, the more "improbable" it is that the group order is
so smooth.
The C values were recomputed on 18 Oct 2019 using an improved program
[available on request] that implements equation (3.3) in my paper "Some
integer factorization algorithms using elliptic curves", Australian Computer
Science Communications 8 (1986), 149-163.
If the elliptic curve is known to be of the form b*y^2 = x^3 + a*x^2 + x
with initial point (x1, y1), where x1 = u^3, u = (sigma^2 - 5)/(4*sigma),
a + 2 = (1/u - 1)^3 * (3*u + 1)/4, then the parameter sigma is given. In
this case the group order is divisible by 12, as discovered by Hiromi Suyama
in Oct 1985.
Factor g2 g1 C sigma
^^^^^^ ^^^^ ^^^^ ^^^ ^^^^^
p83 = 1655... 1143896321 7843501130401 3.43e7 3882127693
p79 = 6083... 6462056569 57699467337301 1.27e6 3761504459
p79 = 2302... 138483313 764489238641 1.84e8 3648110021
p77 = 1897... 677443181 10607352143 3.17e7 366329389
p76 = 5191... 87582379 390238339 9.99e8 896958136
p75 = 3368... 173109949 1584686398147 2.43e7 3885593015
p75 = 2274... 662505049 240668952133 6.86e6 2224648366
p75 = 1314... 11587440367 29544147825133 2.06e5 2143831236
p74 = 2672... 544496971 147157381081 6.66e6 2396540755
p73 = 3045... 708795697 307344999641 3.06e6 1915331402
p73 = 1808... 1923401731 10801302048203 5.70e5 4000027779
p68 = 4259... 79037141 723922811009 4.54e6 1998958586
p67 = 4444... 87373729 11805290281 6.43e6 834412411
p66 = 7096... 13153633 249436823 1.68e8 1875377824
p59 = 2013... 134939023 7285852169 1.83e5 4114600819
p57 = 1675... 33587233 78756287 1.47e6 6329517009540700
p55 = 1139... 16576387 8139353693 2.32e5 556090596
p54 = 4840... 8939393 13323719 4.44e6 599841120
p53 = 5362... 8867563 15880351 2.43e6 8689346476060549
p49 = 1078... 28393447 2700196643 1.65e4
p48 = 6629... 141667 150814537 2.88e7 876329474
p47 = 1202... 2459497 903335969 8.54e4
p44 = 2788... 949159 4818400261 4.94e4
p43 = 5688... <139894 <14212100 >2.34e6
p42 = 1849... <2000000 <100000000 >2.02e4
p40 = 1232... <1000000 1209269 >1.11e5
===============================================================================
Compiled by R.P.Brent with assistance from K.Aoki, R.Backstrom, F.Berger,
A.Bhargava, J.Bos, D.Broadhurst, A.Brown, J.Card, C.Casey, S.Cavallar,
T.Charron, S.Chong, C.Clavier, C.Curry, B.Dodson, D.Doligez, W.Ekkelkamp,
M.Fleuren, P.Gaudry, T.Granlund, R.Hooft, S.Irvine, P.Johansson, M.Kamada,
B.Kelly, Y.Kida, T.Kleinjung, T.Kobayashi, Y.Koide, A.Kruppa, H.Kuwakado,
A.Lenstra, P.Leyland, W.Lipp, N.Lygeros, A.MacLeod, J-C. Meyrignac,
D.Miller, I.Miyamoto, M.Mizony, P.Montgomery, A.Mueller, T.Nokleby,
S.Pelissier, E.Prestemon, R.Propper, M.Quercia, G.Reynolds, D.Rusin,
W.Sakai, T.Shimoyama, R.Silverman, A.Steel, I.Tetsuya, M.Ukai, S.Wagstaff,
G.Wambach, M.Wiener, G.Woltman, A.Yamasaki, P.Zimmermann and J.Zylstra.
Last revised 21 Oct 2019