=========================================================================== Large Factors Found By ECM ^^^^^^^^^^^^^^^^^^^^^^^^^^ This file (champsm.txt) contains information on factors of at least 40 decimal digits found by the elliptic curve factoring method (ECM) up to the end of 1997. Compiled by R. P. Brent with assistance from F. Berger, S. Cavallar, B. Dodson, Y. Kida, H. Kuwakado, S. Larvala, A. Lenstra, P. Leyland, P. Montgomery, A. Mueller, D. Rusin, S. Wagstaff, G. Wambach, M. Wiener and P. Zimmermann. In 1997 there were 29 additions, making 73 entries in all. The 1997 additions are summarized in the following table. p40 p41 p42 p43 p44 p45 p46 p47 p48 total Brent 3 1 - - - 1 - - 1 6 Cavallar 1 - - - - - - - - 1 Dodson 1 - - - - - - - - 1 Leyland - 1 - - - - - - - 1 Montgomery 4 1 2 3 - - - - - 10 Wiener - - - 1 - - - - - 1 Zimmermann 1 4 2 2 - - - - - 9 Totals 10 7 4 6 - 1 - - 1 29 In addition, someone using the pseudonym "Marin Mersenne" reported the following new factorizations without indicating the method used: 7,193+ p40.p99 6,226+ p41.p108 10,206+ p41.p110 85!+1 p42.p65 86!+1 p43.p62 11,341L p43.p77 3,356+ p45.p109 3,413- p47.p48 5,254+ p50.p71 Some or all of these factorizations could have been obtained by ECM/SNFS/MPQS or some other method. If they were all obtained by ECM we would have an additional row in the table: p40 p41 p42 p43 p44 p45 p46 p47 p48 p49 p50 total Mersenne 1 2 1 2 - 1 - 1 - - 1 9 This file is available by ftp from nimbus.anu.edu.au:/pub/Brent/champs.txt Please send corrections/updates to Richard.Brent@anu.edu.au Last revised 6 January 1998 (980106). =============================================================================== Summary ^^^^^^^ Factor Divides Found by Date p48 ^^^^^^ ^^^^^^^ ^^^^^^^^ ^^^^ ^^^ 662926550178509475639682769961460088456141816377 24,121+ R. P. Brent(15) 971009 p47 ^^^ 28207978317787299519881883345010831781124600233 30,109-P. Montgomery(10) 960225 12025702000065183805751513732616276516181800961 5,256+ P. Montgomery(10) 951127 p46 ^^^ 7341439622297499430728231447393744853967297899 L769 P. Montgomery(10) 960506 p45 ^^^ 122213491239590733375594767461662771175707001 91,100+ R. P. Brent (15) 971024 p44 ^^^ 27885873044042449777540626664487051863162949 p(19069) Berger-Mueller(3) 950621 p43 ^^^ 8968496972740368420580830979099439448387289 6,678+ P. Montgomery(10) 970328 8717585253517894966154284413195420314854559 5,283- P. Montgomery(10) 970322 7497754071286769174173123707569003284024777 491,37- R. P. Brent (7) 960914 5688864305048653702791752405107044435136231 p(19997) Berger-Mueller(3) 930320 5606313649481545357328860836968083293930859 Note(22) P. Zimmermann(19) 970522 4578376497845545742407987348754758713076681 2,1310M H. Kuwakado (8) 950925 4343963399878302334317690940709972284426861 60,73- R. P. Brent (13) 960407 3475700719926956233659563848134955052440801 10,200+ M. Wiener (24) 970930 2444038758180970932054301427659584157488373 2,1306L P. Montgomery(10) 971117 2108763496647978603692913892519856162800073 p(14957) Berger-Mueller(3) 960305 1106456110228900043398648244535079439933081 Note(20) P. Zimmermann(19) 970324 p42 ^^^ 648168721774409511378116151410898673195879 2,603- S. S. Wagstaff(6) 940502 227831060593285510425519277644775297708801 3,600+ B. A. Dodson (4) 961104 212108166036775590312324935519541762631363 Note(23) P. Zimmermann(19) 971017 210113748844700144917711383538967015427673 12,543M P. Zimmermann(19) 970903 209286094074580318288344692937218868614221 2,1830L P. Montgomery(10) 970202 184976479633092931103313037835504355363361 10,201- D. Rusin (2) 920405 152254207931524870640907264181257222395351 7,275- P. Montgomery(10) 971229 125761471192249852273062537506530518867571 55,95+ R. P. Brent (13) 961204 p41 ^^^ 84394719860368846600630163154101993088491 p(15647) Berger-Mueller(3) 931122 48361480625294992935267296663140221806509 p(26959) P. Zimmermann(19) 970825 46340806006056354017115743518899032786839 89,123- R. P. Brent (15) 960803 42173111702521341940416989340041084225191 5,309- R. P. Brent (15) 970915 29329409239671376771086497588445454404721 71,120+ P. Montgomery(10) 960305 26917859611055656728302165725740157055483 6,269+ P. Zimmermann(19) 971201 25828091831330874777071588408699791972187 Cullen(449) P. Leyland(25) 971221 25797525576710361109978532913802482717701 211,50+ G. Wambach (16) 961011 25233450176615986500234063824208915571213 55,126+ R. P. Brent (7) 950716 23994584868649296901330386181079088910237 p(13327) Dodson-Fante (4) 930717 23002427674538423724440222579773363877497 47,76+ R. P. Brent (15) 960921 17833653493084084667826559287841287911473 p(25943) P. Zimmermann(19) 970915 17247806607650556918057245637345946590803 p(16057) Berger-Mueller(3) 950402 15164972751718165538717288739219937057169 2,548+ S. S. Wagstaff(6) 940820 14115544468985642263240160261309025447469 211,69+ G. Wambach (14) 960907 11312395373674587455280184557176229738187 2,909+ H. Kuwakado (8) 960507 11241422727712129053244656991156530202847 p(27017) P. Zimmermann(19) 970728 10200602444075618255654001255237011614621 6,642+ P. Montgomery(10) 970324 p40 ^^^ 9409853205696664168149671432955079744397 Note(11) R. P. Brent (12) 951217 8500591978242473249929589155637812362821 2,1690L S. Cavallar (21) 971201 8403554954641929910039991953994224831757 Note(18) P. Zimmermann(19) 961210 7870274800351815110009026018449339439561 96,117- R. P. Brent (13) 970131 6698673804353059562951740785616684633441 467,48+ R. P. Brent (7) 961209 5735013127104523546495917836490637235369 p(14561) P. Zimmermann(19) 970304 5383539446793990416488818114381662511041 10,202+ R. P. Brent (15) 970905 4789533577787722153663685529580118155897 3,1089L P. Montgomery(10) 971124 4659775785220018543264560743076778192897 2,1024+ R. P. Brent (9) 951020 4195369622107561728725528588657828897923 6,279- P. Montgomery(10) 971011 4177156944967188156130003670858609781761 5,232+ S. S. Wagstaff(6) 950125 3838349180533062410406956899485822213133 109,78+ G. Wambach (14) 960502 3546851167184977186234046951293491020491 293,37- G. Wambach (14) 961104 3150916688576664143611069445209929619169 2,917- P. Montgomery(10) 961216 2953667228251580029339756726838729574091 7,209+ Y. Kida (17) 961016 2756692276893174429957731525074455099863 p(26267) B. A. Dodson (4) 971201 2537189980641402843885010229600805270041 p(18917) Berger-Mueller(3) 960222 2394594520709878135254356190088519028761 2,833- P. Montgomery(10) 961015 2268381355068847973282641640849813559817 p(17401) B. A. Dodson (4) 960108 2222565653301339313658936859608420497867 p(15329) Berger-Mueller(3) 940630 1822603397490636085779714533101530614797 6,702M B. A. Dodson (4) 961123 1591612831542489243529439351018973064207 L808 P. Montgomery(10) 960508 1549314255062038569719906776599544873717 26,126+ P. Montgomery (5) 940321 1530577370570695515843056744341672838593 11,228+ P. Montgomery(10) 970201 1345967414522954303164296915490846371433 2,783- P. Montgomery(10) 970322 1339128944366397132859034282532402735701 277,50+ G. Wambach (14) 960927 1315211409858295604581107271920860265251 19,145+ R. P. Brent (15) 971006 1232079689567662686148201863995544247703 p(11279) Lenstra-Dixon(1) 911028 1217879561317617415835577123128586000961 p(13619) B. A. Dodson (4) 960119 1162795072109807846655696105569042240239 22,141+ R. P. Brent (13) 960331 Notes ^^^^^ Most 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). Dates are in YYYY or YYMMDD format. (1) Arjen K. Lenstra and Brandon Dixon on a MasPar (the first p40 by ECM). (2) David Rusin using P. Montgomery's program. (3) Franz-Dieter Berger and Andreas M\"uller on a network of workstations. (4) Bruce Dodson and (sometimes) Matt Fante with Peter Montgomery's program. (5) Peter L. Montgomery on a Cray C98. (6) Samuel S. Wagstaff, Jr., with MasPar program of A. Lenstra and B. Dixon. (7) Richard P. Brent on a Fujitsu AP1000 (128 x 25 Mhz Sparc processors). (8) Hidenori Kuwakado on an IBM PC (Pentium). (9) Richard P. Brent on a 60 Mhz SuperSparc. 2,1024+ = F10 is a Fermat number. (10) Peter L. Montgomery on an SGI workstation. (11) p40 is a factor of p252-1, where p252 is the largest prime factor of F10. (12) Richard P. Brent on a Fujitsu VP2200/10. (13) Richard P. Brent on a 90 Mhz SGI R8000 or R10000. (14) Georg Wambach on a network of Suns using freelip 1.0 by Arjen K. Lenstra. (15) Richard P. Brent on a Fujitsu VPP300. (16) Georg Wambach on a Parsytec-GCel, using freelip 1.0 by Arjen K. Lenstra. (17) Yuji Kida on a 233 MHz PentiumPro using ECMX with UBASIC. (18) p40 is a factor of index 390 of the aliquot sequence starting from 966. (19) Paul Zimmermann on an SGI Power Challenge with Montgomery's program. (20) p43 is a factor of index 768 of the aliquot sequence starting from 552. (21) Stefania Cavallar on an SGI workstation with Peter Montgomery's program. (22) p43 is a factor of index 437 of the aliquot sequence starting from 966. (23) p42 is a factor of index 564 of the aliquot sequence starting from 2936. (24) Michael Wiener on a 200 MHz Pentium Pro. (25) Paul Leyland with Montgomery's program. Cullen(449) = 449*2^449+1. =============================================================================== 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 the information given in the "Details" section below 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. The entry p49 = 7455602825647884208337395736200454918783366342657 is for the p49 factor of F9 = 2,512+ which was "rediscovered" by R. P. Brent on 970429 using a 250 Mhz DEC alpha. This factor is not included in the list above, since it had previously been found by Lenstra et al using SNFS. It is included in the list below because the group order may be of interest. Factor g2 g1 C sigma ^^^^^^ ^^^^ ^^^^ ^^^ ^^^^^ p49 = 7455... 9859051 44275577 210000 862263446 p48 = 6629... 141667 150814537 29000000 876329474 p47 = 2820... 1127603 209558929 370000 p47 = 1202... 2459497 903335969 85000 p46 = 7341... 2675249 548483497 80000 p45 = 1222... 325001 1032299 4400000 877655087 p44 = 2788... 949159 4818400261 49000 p43 = 8968... 169283 195147269 910000 p43 = 8717... 1819397 20740417 81000 p43 = 7497... 170927 16992133 1700000 842640248 p43 = 5688... < 139894 < 14212100 > 2300000 p43 = 5606... 2223499 129634621 33000 p43 = 4578... 5091883 456387241 11000 p43 = 4343... 463453 89776321 210000 6035637 p43 = 3475... < 522432 < 33958015 > 220000 p43 = 2444... 653797 3379074389 49000 p43 = 2108... 3564181 9997644497 6700 p43 = 1106... < 3000000 < 10000000000 > 6800 p42 = 6481... < 800000 < 8000000 > 150000 p42 = 2278... < 1400000 < 100000000 > 29000 p42 = 2121... 841793 35916649 66000 p42 = 2101... 637339 1282547419 36000 p42 = 2092... 2960297 65553193 17000 p42 = 1849... < 2000000 < 100000000 > 20000 p42 = 1522... 2586791 1442325569 8000 p42 = 1257... 811501 2043841 220000 849664676 p41 = 8439... 207061 12371741 440000 p41 = 4836... 461441 671138953 45000 p41 = 4634... 239383 10925743 320000 839005192 p41 = 4217... 348241 134583641 91000 875120139 p41 = 2932... 951997 1438979053 15000 p41 = 2691... 1133459 86584777 24000 p41 = 2582... < 300000 < 30000000 > 150000 p41 = 2579... < 2097152 < 20971520 > 22000 p41 = 2523... 149827 345551 2800000 805816989 p41 = 2399... < 2000000 < 136000000 > 12000 p41 = 2300... 676861 4026193 120000 843230723 p41 = 1783... 389797 1805746381 35000 p41 = 1724... 112199 11425784561 130000 p41 = 1516... < 800000 < 8000000 > 66000 p41 = 1411... < 1048576 < 10485760 > 45000 p41 = 1131... 3713263 166683703 6200 p41 = 1124... 2335117 46964303 13000 p41 = 1020... 740939 207840037 24000 p40 = 9409... 57163 309335137 860000 48998398 p40 = 8500... 990503 17351597 36000 p40 = 8403... < 3000000 < 10000000000 > 2800 p40 = 7870... 859913 125833693 22000 854658786 p40 = 6698... 103951 3952733 960000 850071363 p40 = 5735... 329941 4043946241 28000 p40 = 5383... 139663 533249 1500000 873368186 p40 = 4789... 996173 158665009 16000 p40 = 4659... 314263 4677853 170000 14152267 p40 = 4195... 1020529 82119953 19000 p40 = 4177... < 800000 < 8000000 > 50000 p40 = 3838... < 1048576 < 10485760 > 35000 p40 = 3546... < 2097152 < 20971520 > 15000 p40 = 3150... 794011 641870213 14000 p40 = 2953... 1000000 50000000 > 20000 p40 = 2756... < 1000000 < 1000000 > 170000 p40 = 2537... 522569 804235547 19000 p40 = 2394... 1680361 107205019 9800 p40 = 2268... < 1400000 < 100000000 > 11000 p40 = 2222... 371669 2625541 150000 p40 = 1822... < 1400000 < 100000000 > 11000 p40 = 1591... 21347 138921457 4900000 p40 = 1549... 154303 4035751 350000 p40 = 1530... 2508101 5698736347 2600 p40 = 1345... 701819 29831381 28000 p40 = 1339... < 1048576 < 10485760 > 28000 p40 = 1315... 616463 873319 190000 876131849 p40 = 1232... < 1000000 1209269 > 110000 p40 = 1217... < 1400000 < 100000000 > 10000 p40 = 1162... 184777 87353389 100000 30093425 =============================================================================== [see champs2.txt and champs3.txt for continuation, champs96.txt for 1996] 1048576 < 10485760 > 28000 p40 = 1315... 616463 873319 190000 876131849 p40 = 1232... < 1000000 1209269 > 110000 p40 = 1217... < 1400000 < 100000000 > 10000 p40 = 1162... 184777 87353389 100000 30093425 =============================================================================== [see champs1.txt and champs2.txt for continuation, champs96.txt for 1996]