Large Factors Found By ECM ^^^^^^^^^^^^^^^^^^^^^^^^^^ This file (champs11.txt) contains information on the "top ten" factors found by the elliptic curve factoring method (ECM) up to the end of 2011. 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 100" list at http://www.loria.fr/~zimmerma/records/top100.html and my list of factors found in 2003, champs03.txt. There are three new entries so far in 2011, a p69 and p68 by Dodson and a p67 by Bos, Kleinjung, Arjen Lenstra and Montgomery. 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://wwwmaths.anu.edu.au/~brent/ftp/champs11.txt or via the link at http://wwwmaths.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 ^^^^^^ ^^^^^^^ ^^^^^^^^ ^^^^ p73 YYYYMMDD ^^^ 1808422353177349564546512035512530001279481259854248860454348989451026887 * 2,1181- J. Bos et al (21) 20100307 1042816042941845750042952206680089794415014668329850393031910483526456487 2,1163- J. Bos et al (15) 20100418 p70 ^^^ 2538207129840687799335203259492870476186248896616401346500027311795983 2,1237- J. Bos et al (19) 20101031 p69 ^^^ 474942339376967475871960321762614254290810243038880418971061342256529 2,1822L B. Dodson (18) 20110221 362466230088787245203725150695608196446507416763500471557553488672973 3,1443L S. Wagstaff (14) 20101125 p68 ^^^ 42593783346150223186979443437882164324892008462850480008134130873603 * 64*10^341-1 yoyo@home/M.Thompson (17) 20091228 12947560801881275212486900476122097688373975262784709656768032387833 2,1139- J. Bos et al (16) 20100905 11770588553073659242102454824858622972163387155333297977804066944331 7,763L B. Dodson (12) 20110612 p67 ^^^ 4444349792156709907895752551798631908946180608768737946280238078881 * 10,381+ B. Dodson (13) 20060824 3043392259206870967482500082233986390424278957322258801584514334307 2,1151+ Bos et al (20) 20110506 [end of current top ten] [following former champions listed for historical interest] p66 ^^^ 709601635082267320966424084955776789770864725643996885415676682297 * 3,466+ B. Dodson (22) 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) Bruce Dodson with GMP-ECM-6.3 on a cluster of 8-core AMD chips, c232 = p68*p165, r = 3.41 (13) Bruce Dodson with GMP-ECM 2006-03-13 [using GMP 4.1] on an Opteron cluster, c214 = p67*p147, r = 3.19. (14) Sam Wastaff with GMP-ECM 6.1.3, c154 = p69.p86, r = 2.23 (15) Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, Peter Montgomery, c318 = p73.p246, r = 4.36, details similar to (21). (16) Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, Peter Montgomery, c313 = p68.p246, r = 4.60 (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, c197 = p69.p128, r = 2.86. (19) Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, Peter Montgomery, c373 = p70.c303, r = 5.33. (20) Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, Peter Montgomery, c302 = p67.c236, r = 4.51. (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) Bruce Dodson with GMP-ECM 6.0 on an Opteron cluster, c180 = p66*p114, r = 2.73. ================================================================================ 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. 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). The larger C, the more "improbable" it is that the group order is so smooth. 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. Factor g2 g1 C sigma ^^^^^^ ^^^^ ^^^^ ^^^ ^^^^^ p73 = 1808... 1923401731 10801302048203 570000 4000027779 p73 = 1042... 431421191 13007798103359 ? 3000085158 p70 = 2538... 2634306799 38790235277 ? 3000086787 p69 = 3624... 254178263 341591895241 ? 1574053484 p69 = 4749... 356236847 31186368729239 ? 1648470872 p68 = 4259... 79037141 723922811009 4500000 1998958586 p68 = 1294... 2353240789 312975725519 ? 3000043837 p68 = 1177... 498184633 70820042681 ? 4251689254 p67 = 4444... 87373729 11805290281 6400000 834412411 p67 = 3043... 577611283 6145032281393 ? 1000021551 p66 = 7096... 13153633 249436823 170000000 1875377824 p59 = 2013... 134939023 7285852169 180000 4114600819 p57 = 1675... 33587233 78756287 1500000 6329517009540700 p55 = 1139... 16576387 8139353693 230000 556090596 p54 = 4840... 8939393 13323719 4400000 599841120 p53 = 5362... 8867563 15880351 2400000 8689346476060549 p49 = 1078... 28393447 2700196643 16000 p48 = 6629... 141667 150814537 29000000 876329474 p47 = 1202... 2459497 903335969 85000 p44 = 2788... 949159 4818400261 49000 p43 = 5688... < 139894 < 14212100 > 2300000 p42 = 1849... < 2000000 < 100000000 > 20000 p40 = 1232... < 1000000 1209269 > 110000 =============================================================================== 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, 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. [see champs10.txt for 2010, champs09.txt for 2009, etc.] Last revised 31 December 2011.