=============================================================================== Large Factors Found By ECM ^^^^^^^^^^^^^^^^^^^^^^^^^^ This file (champs.txt) contains information on large factors found by the elliptic curve factoring method (ECM) up to the end of 2003. Factors are included if 1) they were at any time the largest factor found so far by ECM and at least 40 decimal digits ("champions"); or 2) they are one of the largest ten factors found so far (the "top ten"), but see the comments re "?" and "??" factors below. New entries will be accepted if they are in the current "top ten". At present this means they will have to be at least 52 decimal digits. The largest factor not labelled "??" or "?", found by Bruce Dodson, has 57 decimal digits. The largest factor so far, found by Robert Backstrom, has 58 decimal digits but is labelled "??" for reasons explained below. In 2003 nine new entries were submitted: 1) A p52 factor of 83^76+76^83 by Jonathan Zylstra. 2) A p52 factor of the Mersenne number 2,773- by Patrik Johansson. 3) A p57 factor of the Mersenne number 2,997- by Bruce Dodson. It became the new "champ" (beating Izumi Miyamoto's p55 that had been the "champ" since October 2001). 4) A p52 factor of 10,313+ by Torbjorn Granlund. 5) A p58 "??" factor of 8*10^141-17 by Robert Backstrom. This should probably not be regarded as the new "champ" since the cofactor has only 52 decimal digits! p58 is a factor of c110 = (8*10^141-17)/9/p32, where p32 = 49832154030989267740867384231123. In fact c110 = p52.p58, where p52 = 5551433702907422298841863964693267244613910158966569 and p58 = 3213162276640339413566047915418064969550383692549981333701. ECM found the p58 factor, with sigma = 2735675386 and a very smooth group order (see below). Of course, as far as factoring c110 goes, finding p58 is no better than finding p52, and the c110 is small enough that it could have been factored in a few days by GNFS. 6) A p54 "??" factor found by Chris Casey from a c100 = p54*p46. 7) A p52 "??" factor found by Jonathan Zylstra from a c100 = p52*p49. 8) A p55 "??" factor found by David Broadhurst from a c107 = p55*p53. 9) A p56 factor found by K. Aoki from a c249 = p56*p193. Factors such as Backstrom's p58, Casey's p54 and Zylstra's p52 are listed with a "??" to indicate that they are larger than the cofactor. Such factors could certainly be found more easily by a method such as MPQS or GNFS unless ECM is extremely lucky in finding a smooth group order much faster than expected. A single "?" indicates a factor that is smaller than the cofactor, but even so could (probably) have been found more easily by another method such as GNFS or SNFS. Typically this is the case if r < 2.5, where r is the ratio of lengths of the input (composite) and the factor. To give some benefit of the doubt to ECM, we only assign a "?" if r < 2.2. The reader can decide whether or not to count factors with a "?" or "??" or to disregard them. Since they are factors found by ECM, it seems appropriate to list them here. "?" and "??" factors are not counted in the limit of ten, so they do not displace other factors. The overall list is given below. Factors which at one time were the current "champions" (without any "?" marks) are indicated by an asterisk. NB: From 1 January 2004 I am not going to include new "?" or "??" factors in this list. If you are interested in them, see Paul Zimmermann's "top 100" list at http://www.loria.fr/~zimmerma/records/top100.html . This file is available from ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/champs.txt or via the link at http://www.comlab.ox.ac.uk/oucl/work/richard.brent/factors.html Please send corrections/updates to champs@rpbrent.co.uk R. P. Brent http://www.comlab.ox.ac.uk =============================================================================== Summary ^^^^^^^ Factor Divides Found by Date p58 ^^^^^^ ^^^^^^^ ^^^^^^^^ ^^^^ ^^^ YYYYMMDD 3213162276640339413566047915418064969550383692549981333701 ?? 8*10^141-17 R. Backstrom (18) 20031031 p57 ^^^ 167560816514084819488737767976263150405095191554732902607 * 2,997- B. Dodson (16) 20030621 p56 ^^^ 69787377067722881486602094502761253930262932578924438539 2,827+ K. Aoki (21) 20031226 p55 ^^^ 7230880127526821693925059508972082952702133004552346281 ? 629,59- I. Miyamoto (14) 20011006 5214992488521222360623470091045256749679250526710700189 ?? V(54,1,73) D. Broadhurst (19) 20031210 1139151258261034615880135106860446479526482959089061629 * 93^56+56^93 P. Gaudry (15) 20021213 p54 ^^^ 484061254276878368125726870789180231995964870094916937 * (6^43-1)^42+1 Note (8) 19991226 133936702795612545033253138872863276649299468089582417 ?? Choose_341,141+ C. Casey (17) 20020319 113944651856655107794996103150041939333993926230123191 ? (3^64-1)^63+1 Note (10) 20000321 p53 ^^^ 81477382431617858607629654669086224895030590860856949 HP49(84) A. Kruppa (9) 20020525 53625112691923843508117942311516428173021903300344567 * 2,677- C. Curry (7) 19980914 p52 ^^^ 9550932766611135096816626304308249655491758024828481 858,140+ D. Broadhurst (13) 20021010 7517596214490051335825344881028792801065608068512131 102!-1 S. Irvine (11) 20011101 6124304827429735546123425103102892562385732953863411 ?? XY(105,55) J. Zylstra (20) 20031101 3942061217624131929520541160207424212724650028976527 10,313+ T. Granlund (12) 20030715 3102804258869848876949115800490112967822146918598407 2,773- P. Johansson (22) 20030617 [end of current top ten, apart from "?" and "??" entries] [following former champions listed for historical interest] 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{+-LM}) or partition numbers (p(n) is the n-th partition number) or Lucas numbers (Ln is the n-th Lucas number) or other numbers described in the notes. Dates are in YYYYMMDD format (after conversion to GMT). The notations "*", "?", "??" are described above. (1) Arjen Lenstra and Brandon Dixon on a MasPar (the first p40 by ECM). c89 = p40*p50 (r = 2.22; borderline "?" as easier by MPQS than ECM on most machines, but it was not regarded as a "?" when it was found, and MPQS might not have been implemented on the MasPar, so we have adopted a cutoff of r = 2.20 < 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; borderline "?") 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, borderline "?". (9) Alexander Kruppa with GMP-ECM 4c. c167 = p53*p114, r = 3.15. See http://www.worldofnumbers.com/topic1.htm for the definition of HP49(n). (10) Nik Lygeros and Michel Mizony with GMP-ECM. c118 = p54*p65, r = 2.18 so "?" (easier by GNFS than ECM). (11) Sean Irvine with GMP-ECM. The p52 is a factor of 102! - 1 (c148). c148 = p52*p96, r = 2.85. (12) Torbjorn Granlund with GMP-ECM. 10,313+ c282= p52*c230, r = 5.42. (13) David Broadhurst with GMP-ECM. c197 = p52*p145, r = 3.79. (14) Izumi Miyamoto with GMP-ECM 4c on 800 Mhz Pentium III under Linux. c112 = p55*p57, r = 2.03 so "?" (easier by MPQS or GNFS than by ECM). (15) Pierrick Gaudry with GMP-ECM. c121 = p55*p67 so r = 2.2, which is precisely our cutoff for "?". (16) Bruce Dodson using George Woltman's Prime95. c301 = p57*p244, r = 5.28. (17) Chris Casey with GMP-ECM. c100 = Choose_341,141+ = p54*p46 so "??". Found 20020319 but not reported until 20031201. (18) Robert Backstrom with GMP-ECM. c110 = p58*p52 so "??". (19) David Broadhurst with GMP-ECM. c107 = p55*p53 so "??". (20) Jonathan Zylstra with GMP-ECM. c100 = p52*p49 so "??". c100 is a factor of 105^55+55^105. (21) K. Aoki with GMP-ECM, c249 = p56*p193. (22) Patrik Johansson with Woltman's Prime95 for step 1 and GMP-ECM for step 2. c186 = p52*c135, c135 = p45*p91. (The p45 was already known.) ================================================================================ 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 ^^^^^^ ^^^^ ^^^^ ^^^ ^^^^^ p58 = 3213... 1615843 33631583 135000000 2735675386 p57 = 1675... 33587233 78756287 1500000 6329517009540700 p56 = 6978... 27554129 750546089 ?????? 4029008539 p55 = 7230... 25268183 41286269351 150000 267937500 p55 = 5214... 26678501 45807419443 130000 3836151505 p55 = 1139... 16576387 8139353693 232000 556090596 p54 = 4840... 8939393 13323719 4400000 599841120 p54 = 1339... 479147 1943983339 33000000 1335265706 p54 = 1139... 3015007 101673721 3500000 718797804 p53 = 8147... 8193599 322677167 690000 219538831 p53 = 5362... 8867563 15880351 2400000 8689346476060549 p52 = 9550... 9917191 58860449 710000 1991445260 p52 = 7517... 7044757 118052531 700000 1689607121 p52 = 6124... 2521223 584786623 ?????? 3530648309 p52 = 3942... 1385303 183419881 4200000 1461716703 p52 = 3102... 2378263 1701537137 ??? 8170945836124664 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, D. Broadhurst, A. Brown, J. Card, C. Casey, S. Cavallar, T. Charron, C. Clavier, C. Curry, B. Dodson, D. Doligez, M. Fleuren, P. Gaudry, T. Granlund, S. Irvine, P. Johansson, Y. Kida, T. Kobayashi, Y. Koide, A. Kruppa, H. Kuwakado, A. Lenstra, P. Leyland, N. Lygeros, A. MacLeod, J-C. Meyrignac, D. Miller, I. Miyamoto, M. Mizony, P. Montgomery, A. Mueller, T. Nokleby, E. Prestemon, M. Quercia, D. Rusin, R. Silverman, A. Steel, I. Tetsuya, M. Ukai, S. Wagstaff, G. Wambach, M. Wiener, G. Woltman, A. Yamasaki, P. Zimmermann and J. Zylstra. [see champs1.txt for factors of at least 40 decimal digits found to 31 December 1998, champs2.txt for more details, champs02.txt for 2002, etc.] For a "top 100" list, see http://www.loria.fr/~zimmerma/records/top100.html Last revised 17 January 2004.