|
[quote=unconnected;173322]Another huge P-1 factor (48-digit), also composite[/quote]
They're not rare. They're only really of note if they're prime factors of roughly that size or if the composite splits into two or more primes, with the largest being roughly that size. |
[quote=10metreh;173054]<snip>[/quote]
And here's another one, this time with an even lower B1 :toot:: [code]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P+1] Input number is 79149865325080986335416791942619887582415026902421882452494444078602449155427 (77 digits) Using B1=[B]110000[/B], B2=341719732, polynomial x^1, x0=1894730186 Step 1 took 265ms Step 2 took 1000ms ********** Factor found in step 2: 319676108967979949394023 Found probable prime factor of 24 digits: 319676108967979949394023 Composite cofactor 247593933686827239948049773281183640493342430521802149 has 54 digits[/code] P+1 = 2^3 * 3 * 23 * 43 * 349 * 4049 * 81457 * 117004087 so B1 and B2 could have been a bit lower, but not too much. BTW the c54 split as p16*p38. |
Here's a nice step-1 P-1 hit (t25 had been run on the number beforehand):
[code]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P-1] Input number is 2281458724945241010011684203274605578730567442172340740328915205297156412287322823077511 (88 digits) Using B1=5000000, B2=117870494688, polynomial x^1, x0=2249205394 Step 1 took 9172ms ********** Factor found in step 1: 1726484420192013540770228983 Found probable prime factor of 28 digits: 1726484420192013540770228983 Probable prime cofactor 1321447618213377896509571620080873219725931433694034411365617 has 61 digits[/code] P-1 = 2 * 3^2 * 41 * 1025099 * 1215629 * 1301701 * 1442209 (4-brilliant in there, and all the first digits are the same!), so the factor could have been found in step 1 with a B1 of only 1.5M. And look how oversized that B2 was! :toot: |
New page, new factor
fibonacci(1039) =
[code] (previously known) 8457461 * 132846541 * 20616815802035244343789 * 869789684576116767247597 * 6360937938832846575060048519967228289050132574873739773148777303473 * 47965167002505772608654009141360523399394137005095861480131877331276771055839497806590229 [/code] 14e, 29-bit large primes, small primes 30M both sides, sieved 15M-32M both sides. 1777 thread-hours (much done on an i7), 32 hours on i7 for the 4854784 x 4855032 matrix. 5x^6 - 18x^5 + 30x^4 - 20x^3 + 15x^2 + 1 on algebraic side; fib(174)*x-fib(173) on rational side. There are several Fibonacci numbers of this sort of complexity left: I've done seven in 1000..1100 over the last two years and there are four of those left. fib(1223) is a nice S257 with size in digits = SNFS difficulty, fib(1091) is S228 with the same property and much more readily accessible. |
Here's a double nice-split by [B]Bob Backstrom[/B]:
(56·10[SUP]169[/SUP]+61)/9 has a cofactor c161. c161 = p39.p39.p42.p42 = [FONT=Arial Narrow]424274908169666727454295410341629377361. 744256981543256710605164151127424339141. 142246468831973644407334999953831883982951. 241631107074584670119388266251172464439467 [/FONT] |
[QUOTE=Batalov;176432]Here's a double nice-split by [B]Bob Backstrom[/B]:
(56·10[SUP]169[/SUP]+61)/9 has a cofactor c161. c161 = p39.p39.p42.p42 = [FONT=Arial Narrow]424274908169666727454295410341629377361. 744256981543256710605164151127424339141. 142246468831973644407334999953831883982951. 241631107074584670119388266251172464439467 [/FONT][/QUOTE] :smile: WOW Luigi |
[quote=Batalov;176432]Here's a double nice-split by [B]Bob Backstrom[/B]:
(56·10[sup]169[/sup]+61)/9 has a cofactor c161. c161 = p39.p39.p42.p42 = [FONT=Arial Narrow]424274908169666727454295410341629377361. 744256981543256710605164151127424339141. 142246468831973644407334999953831883982951. 241631107074584670119388266251172464439467 [/FONT][/quote] what ecm was done? |
[quote=henryzz;176514]what ecm was done?[/quote]
SNFS-170, so the 2/9 rule suggests just under 40 digits. I suspect only t35 was run, although with a full t40 there is still a chance (about 15%?) that none of the factors will appear. |
I just got an ecm 59 digit factor that was a fluke really. As some of you know, I'm helping the MPIR project (GMP fork) and was using gmp-ecm to do some testing and benchmarking, and I had picked a C130 as input so I would get long enough test runs.
Well look at what popped out after about 104 runs of tests I have been doing on and off for the past months: [CODE]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM] Input number is 3561374769003472006611194942083317805928391841857811709042682130841367523415658737688338172847927090359833780290773316642214955689 (130 digits) Using B1=300000000, B2=3178599824416, polynomial Dickson(30), sigma=2032225695 Step 1 took 1336400ms Step 2 took 361499ms ********** Factor found in step 2: 21206963047213924100449174648127600105136716298220374685897 Found probable prime factor of 59 digits: 21206963047213924100449174648127600105136716298220374685897 Probable prime cofactor 167934218637276754526453081924651271560178324552025159937204856612557537 has 72 digits [/CODE] That is good for second place for the 2009 ECM top 10 list, and in the 20s for the all-time list. I e-mailed Paul Zimmerman but haven't heard back from him yet. I guess I picked the magic input number and happened to get an unintentional factor after an insanely small amount of runs. This was supposed to just be for testing, I wasn't actually expecting a factor to pop out. Jeff. |
Interestingly, B1=3e8 is a huge excess.
In fact, it is reproduced with B1=3e7, under two minutes running time. Add to benchmark (and it mustn't fail in one run, ever): [FONT=Arial Narrow]ecm -sigma 2032225695 272e5 < this_number[/FONT] :rolleyes: |
Nice split of the c118 cofactor of aliquot172554.1027:
Fri Jun 12 14:28:41 2009 prp59 factor: 40583848776241605766792619601451111162510370395518373639037 Fri Jun 12 14:28:41 2009 prp59 factor: 68438511819428768802985403034884771297957829825131869081517 |
Lucky punch from aliquot 172554:
[code][Jun 20 2009, 11:17:09] Cofactor 19223719229397103735869895564468606263251785680561653388554202432164204897138631706690937388406707574740021324772129 (116 digits) [Jun 20 2009, 15:04:42] c116: running 904 ecm curves at B1=1e6... Using [B]B1=1000000[/B], B2=1045563762, polynomial Dickson(6), sigma=3018506502 Step 1 took 18578ms Step 2 took 9156ms ********** Factor found in step 2: 172394252736826980988454074578109934129027 [Jun 20 2009, 16:53:08] *** prp[B]42[/B] = 172394252736826980988454074578109934129027[/code] |
Today user eteo has found 55-digit factor from M6211 - [FONT=Courier New][SIZE=2]1110196860540711188306812523817624319633363099818286801
BTW, my personal best so far is 48-digit factor from M4937, leaving big factored range from M4721 to M5309. [/SIZE][/FONT] |
Here's a nice 3-way split from aliquot sequence 363270:i1560:[code]factoring 182882740250376378784775952350220058372378173011568288753346996549351152126622176649207093 (90 digits)
... prp29 factor: 31932466382572068400836013921 prp30 factor: 589885961872637328991780506079 prp31 factor: 9708948464517250743010152612427[/code] |
There was a 3 way split on a c150 for aliquot sequence 4788:2428.
prp48 factor: 211583091426921250197446583560454596406151386691 prp49 factor: 8232643115090532013514350738188694142495501455897 prp54 factor: 345355615167159325280013895125653060899714762489093471 |
[QUOTE=Greebley;185559]There was a 3 way split on a c150 for aliquot sequence 4788:2428.[/QUOTE]Actually, I was looking less at the 3-wayness of the split and more at the form of the three final factors: p29*p30*p31.....
I had one other factorization like that that was pointed out to me. A long time ago with 48462:i1307, the final three factors were:[code]p35 = 12227683419462138385285836135775679 p36 = 234307806739938689440551229698967739 p37 = 2086075102836210920652212076645329317[/code] |
C136 cracked into P67.P69; a big-chunk split
For 7^300 + 6^300, a C136 with virtually no hope of being cracked by ECM.
[CODE]p67 factor: 6792164864433933370738850253808680786479089876417483540151155425601 p69 factor: 252984352088587257222515657552381661427235379526912445868815965156801[/CODE] For no discernible reason, I always assume a C136 has a factor under 10^45. For 4^353 - 3^353, the entire composite split into 5 factors: p18.p26.p45.p55.p71 [CODE]346122561135612227 85163816319967233465212077 520380172865178220545508740587263091647271867 1319838283283976337392937406312894083222727502025671959 16628399621909980283703781934701517251218487822301432005515773984964743 [/CODE] This would have taken 20x the number of CPU hours, but I caught a lucky ECM hit almost immediately on the p45, leaving a C125 GNFS that was no problem. |
Yeah, it is fun. Thanks to Tom! A clear and easy-to-use reservation system.
I've also got a p63.p65 and a p53.p54... waiting now for a clear split. :smile: |
9^222+7^222
A cold, dark night here in Singleton Removal Pass, CO.
But some good news on the C138 cofactor of 9^222+7^222, which split as p45.p46.p47: [CODE] p45: 519301821176592798457623203852440533087964849 p46: 7153529786163961021754833948192631031687402229 p47: 91114939647669207489447123432275469014705290861 [/CODE] |
[QUOTE=FactorEyes;187232][CODE]
p45: 519301821176592798457623203852440533087964849 p46: 7153529786163961021754833948192631031687402229 p47: 91114939647669207489447123432275469014705290861 [/CODE][/QUOTE]:sad: Well, that beats both of mine.... |
This factorization of a c87 as p28*p29*p31 was close to being another of those "almost-3-brills":
[code]236605510786928420632575797575071468573797802029930684681900774777493120296973662827297 = 1430253671505288487894274041 * 69768865360470064670348846963 * 2371101384507506691968688372659[/code] However, the p31 was found first, and in a very unusual way: [code]Aug 29 2009, 15:18:29] c87: running 74 ecm curves at B1=11e3... Using B1=[COLOR="Red"]11000[/COLOR], B2=1873422, polynomial x^1, sigma=1369965933 Step 1 took 141ms Step 2 took 156ms ********** Factor found in step 2: 2371101384507506691968688372659 [Aug 29 2009, 15:18:33] *** prp31 = 2371101384507506691968688372659[/code] This is my personal best for ECM at 11e3; does anyone have anything better? |
[QUOTE=10metreh;187948]
However, the p31 was found first, and in a very unusual way: [code]Aug 29 2009, 15:18:29] c87: running 74 ecm curves at B1=11e3... Using B1=[COLOR="Red"]11000[/COLOR], B2=1873422, polynomial x^1, sigma=1369965933 Step 1 took 141ms Step 2 took 156ms ********** Factor found in step 2: 2371101384507506691968688372659 [Aug 29 2009, 15:18:33] *** prp31 = 2371101384507506691968688372659[/code] This is my personal best for ECM at 11e3; does anyone have anything better?[/QUOTE] WOW, that's a lucky punch!! BTW: it would be interesting to collect such "large" factors found by incredibily low B1's in an own thread... :wink: |
[quote=10metreh;187948]snip
This is my personal best for ECM at 11e3; does anyone have anything better?[/quote] GMP-ECM 6.1.3 [powered by GMP 4.2.2] [ECM] Input number is (0110^113+1)/0111/6329/25087/3957487 (214 digits) Using B1=11000, B2=1873422, polynomial x^1, sigma=1933409206 Step 1 took 375ms Step 2 took 203ms ********** Factor found in step 2: 124617241876033553575749568635413 Found probable prime factor of 33 digits: 124617241876033553575749568635413 Probable prime cofactor ((0110^113+1)/0111/6329/25087/3957487)/124617241876033553575749568635413 has 182 digits that's the best I got at B1=11e3, about 6 months ago. |
11^225-2^225 cofactor c125 =
p63 factor: 137971968062830363280049719008816436390979051494316688994186101 p63 factor: 671941337930937512734180444532484779528410015025704923535439101 :smile: |
34 digit factor found at B1=50000 (25-digit level):
GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P-1] Input number is (2^1787+1)/3 (538 digits) Run 131 out of 214: Using B1=50000, B2=15446350, polynomial x^2, sigma=275952116 Step 1 took 2297ms Step 2 took 1625ms ********** Factor found in step 2: 1507239430231527531716343919007089 Found probable prime factor of 34 digits: 1507239430231527531716343919007089 Composite cofactor ((2^1787+1)/3)/1507239430231527531716343919007089 has 505 digits |
onwards, son of Bonacci
[code]
fibonacci(1091) = 13126104546421803634380630263104078519429043694065692605495299885243873 * 34506002668546852317129808214792806402535464223966239212210650860155169664746000782626121065181130381015734910384761295494037326216851092086670944120048373033 [/code] SNFS (difficulty = size of number, which is why this is gratuitous): polynomial [code] A6 1 A5 0 A4 15 A3 20 A2 30 A1 18 A0 5 R0 -fibonacci(181) R1 fibonacci(182) [/code] 30-bit large primes, small prime bound 50M both sides, sieved algebraic side 20M-75M in ~3500 CPU-hours on various systems between 2 and 18 September (94716875 raw relations, 82114579 unique). Six days on a 2.5GHz quad-core Phenom to do the linear algebra with msieve; final matrix 7642809x7643033. |
p57 by ECM with B1 = 3M
Just found this report while preparing for an update of the Generalized Cullen & Woodall numbers.
[code][2009-09-25 02:22:26 GMT] GC_9_369_C351: probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=3933722077254573047641104432697964360070287393192927208173 Method=ECM B1=3000000 Sigma=3202184098 [2009-09-25 02:22:26 GMT] GC_9_369_C351: Probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=69195691762746874558950027792004627474720840991488099531129085382132917297468333086407665753912885871112480886486804987121631180413730061663649238187639199319767068531719923067209966260990277038677149176727877410132825517172273061369667374456935383000887809628959212133751835629050919608144339 Method=ECM B1=3000000 Sigma=3202184098[/code] The number is the 351-digit cofactor of 369 * 9^369 + 1. That is by far the biggest factor I've yet found with such a small B1. According to Paul Zimmerman's tables, it is the biggest [i]ever[/i] to be found with B1=3M. Paul |
[QUOTE=xilman;191235]Just found this report while preparing for an update of the Generalized Cullen & Woodall numbers.
[code][2009-09-25 02:22:26 GMT] GC_9_369_C351: probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=3933722077254573047641104432697964360070287393192927208173 Method=ECM B1=3000000 Sigma=3202184098 [2009-09-25 02:22:26 GMT] GC_9_369_C351: Probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=69195691762746874558950027792004627474720840991488099531129085382132917297468333086407665753912885871112480886486804987121631180413730061663649238187639199319767068531719923067209966260990277038677149176727877410132825517172273061369667374456935383000887809628959212133751835629050919608144339 Method=ECM B1=3000000 Sigma=3202184098[/code] The number is the 351-digit cofactor of 369 * 9^369 + 1. That is by far the biggest factor I've yet found with such a small B1. According to Paul Zimmerman's tables, it is the biggest [i]ever[/i] to be found with B1=3M. Paul[/QUOTE] :shock: :w00t: WooOOOOoooHooOOOOOoo!! :bow wave: |
[QUOTE=xilman;191235]Just found this report while preparing for an update of the Generalized Cullen & Woodall numbers.
[code][2009-09-25 02:22:26 GMT] GC_9_369_C351: probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=3933722077254573047641104432697964360070287393192927208173 Method=ECM B1=3000000 Sigma=3202184098 [2009-09-25 02:22:26 GMT] GC_9_369_C351: Probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=69195691762746874558950027792004627474720840991488099531129085382132917297468333086407665753912885871112480886486804987121631180413730061663649238187639199319767068531719923067209966260990277038677149176727877410132825517172273061369667374456935383000887809628959212133751835629050919608144339 Method=ECM B1=3000000 Sigma=3202184098[/code] The number is the 351-digit cofactor of 369 * 9^369 + 1. That is by far the biggest factor I've yet found with such a small B1. According to Paul Zimmerman's tables, it is the biggest [i]ever[/i] to be found with B1=3M. Paul[/QUOTE] It's a p58 not a p57... |
[QUOTE=xilman;191235]Just found this report while preparing for an update of the Generalized Cullen & Woodall numbers.
[code][2009-09-25 02:22:26 GMT] GC_9_369_C351: probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=3933722077254573047641104432697964360070287393192927208173 Method=ECM B1=3000000 Sigma=3202184098 [2009-09-25 02:22:26 GMT] GC_9_369_C351: Probable factor returned by paul@leyland.vispa.net (adnams2)! Factor=69195691762746874558950027792004627474720840991488099531129085382132917297468333086407665753912885871112480886486804987121631180413730061663649238187639199319767068531719923067209966260990277038677149176727877410132825517172273061369667374456935383000887809628959212133751835629050919608144339 Method=ECM B1=3000000 Sigma=3202184098[/code] The number is the 351-digit cofactor of 369 * 9^369 + 1. That is by far the biggest factor I've yet found with such a small B1. According to Paul Zimmerman's tables, it is the biggest [i]ever[/i] to be found with B1=3M. Paul[/QUOTE] Do you have the curve sigma value so that the group order can be computed? |
[QUOTE=R.D. Silverman;191245]Do you have the curve sigma value so that the group order
can be computed?[/QUOTE] He did give the sigma. Group order is: [code]? \rsea.gp ? \recmsigma.gp ? p=3933722077254573047641104432697964360070287393192927208173 %1 = 3933722077254573047641104432697964360070287393192927208173 ? s=3202184098 %2 = 3202184098 ? ellsea(ecmsigma(s,p),p) %3 = 3933722077254573047641104432782741609536385711607116873736 ? factorint(%) %4 = [2 3] [3 4] [29 1] [313 1] [4177 1] [7699 1] [13883 1] [20731 1] [54217 1] [131293 1] [326503 1] [463831 1] [1564081 1] [42854923 1] [/code] |
[QUOTE=jrk;191247]He did give the sigma.
Group order is: [code]? \rsea.gp ? \recmsigma.gp ? p=3933722077254573047641104432697964360070287393192927208173 %1 = 3933722077254573047641104432697964360070287393192927208173 ? s=3202184098 %2 = 3202184098 ? ellsea(ecmsigma(s,p),p) %3 = 3933722077254573047641104432782741609536385711607116873736 ? factorint(%) %4 = [2 3] [3 4] [29 1] [313 1] [4177 1] [7699 1] [13883 1] [20731 1] [54217 1] [131293 1] [326503 1] [463831 1] [1564081 1] [42854923 1] [/code][/QUOTE]Thanks for performing the computation That is a remarkably smooth group order. Note that the factor would have been found in stage one with parameters optimal for finding 50-digit primes. Finding a 58-digit prime in the second stage with p50 parameters would have been pleasing enough. Paul |
[QUOTE=10metreh;191240]It's a p58 not a p57...[/QUOTE]It is? I miscounted.
You're right! It is even more unusual in that case. Paul |
Paul,
malibu.gen.cam.ac.uk:8194 seems to be down. Carlos |
[QUOTE=em99010pepe;191254]Paul,
malibu.gen.cam.ac.uk:8194 seems to be down. Carlos[/QUOTE]Correct. I didn't think anyone other than me was using it. If you wish to contribute to the factoring of generalized Cullen & Woodall numbers, please use the server on my home machine at 83.217.167.177:8194 That machine does have a DNS registration but it's not a particularly friendly one (essentially it's the IP addres plus some extraneous junk) so I always publicise the raw IP address. Malibu is still up and running, but as my contract with the Genetics Dept at Cambridge University expires in another 2 days I thought it a good idea to shut down the server. Paul |
This is a bit nice step-1 ECM hit.
[quote] GMP-ECM 6.2.3 [powered by GMP 4.2.4] [ECM] Input number is 7908926676514675413083853032827063880118980193445471625562601469958414706043143581401715516956542424923236530406833110566233 (124 digits) Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=7372562557 Step 1 took 4180ms ********** Factor found in step 1: 90267127858585686761229484150679606606868203 Found probable prime factor of 44 digits: 90267127858585686761229484150679606606868203 Composite cofactor 87616908437642552977838315920860564586991837524724010046764766223080042854872011 has 80 digits [/quote] |
[QUOTE=Yeong Uk Jo;192178]This is a bit nice step-1 ECM hit.[/QUOTE]
:w00t: That looks like a *very* lucky hit! |
[QUOTE=Andi47;192235]:w00t:
That looks like a *very* lucky hit![/QUOTE] Probability about 4.5 x 10^-7. |
[quote=Andi47;192235]:w00t:
That looks like a *very* lucky hit![/quote] Extremely lucky, indeed! GMP-ECM calculates a 1 in 2089304 (probability about ~4.79*10^-7) chance for a 45-digit factor in step 1. Anyone care to calculate the group order (or whatever it's called)? (the minimum B1 to find it in step 1, i.e. the largest factor size, should be between 760000 and 770000, from running the same sigma with varying B1 levels) Edit: Never mind, I found some [URL="http://www.mersenneforum.org/showpost.php?p=56055&postcount=7"]code for it[/URL] ([URL="http://magma.maths.usyd.edu.au/calc/"]calculator/evaluator moved here[/URL]). It's [URL="http://factordb.com/search.php?id=72831691"]this number[/URL], with min. B1 = 765899 (to find in Step 1), or min. B1 = 147031, min. B2 = 765899 (to find in Step 2). By picking the B1 and B2 just perfectly, I can re-find this factor in under 1.5 seconds, vs. the ~9.5 seconds a B1 of 1000000 takes. :smile: |
[QUOTE=Yeong Uk Jo;192178]This is a bit nice step-1 ECM hit.[/QUOTE]
Cofator = 87616908437642552977838315920860564586991837524724010046764766223080042854872011 6725886983982318771880439066030047436221 x 13026818417600827639174618332243277437991 |
I(1198) CF<118> 1710386215845906974897106817162996476688897422433594979236672346651898190811892498146079534736726738325272145704291841 =
552087064158419374947426751986111445101908649705091474880309 x 3098037115673331319837279938413799675926967687690564696349 |
12[SUP]299[/SUP]-1 c174 splits by gnfs as
[FONT=Arial Narrow]p81=697991007926456759867763797920697380555799972539371350183399903406406626529359323[/FONT] [FONT=Arial Narrow]p93=632579713668994505806721568584133445028115113935761696306160562336073281822252317312806529187[/FONT] |
[quote=ugly2dog;192518]
[code] I(1198) CF<118> 1710386215845906974897106817162996476688897422433594979236672346651898190811892498146079534736726738325272145704291841 = 552087064158419374947426751986111445101908649705091474880309 x 3098037115673331319837279938413799675926967687690564696349 [/code][/quote] Nice split! How long did this take, and did you use multiple threads? [SIZE=1]p.s. Serge,[/SIZE] [SIZE=1]Nice job as well, of course, but gotta encourge newcomers and all...[/SIZE] |
"Nice split! How long did this take, and did you use multiple threads?"
It took a little over 10 days with two threads on core2duo 2.4GHz [WinXP] with intermittent heavy usage. The program occasionally drops to one threads only for short, but consistent periods of time. I really didn't have time to monitor it while it was running. |
A nice P+1 hit with low B1:
[code]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P+1] Input number is 98574137650378747154268459914600766723260038216357693592104375646816403136258801 (80 digits) Using B1=110000, B2=341719732, polynomial x^1, x0=3526353810 Step 1 took 296ms Step 2 took 1016ms ********** Factor found in step 2: 22085152151389226940117611 Found probable prime factor of 26 digits: 22085152151389226940117611 Composite cofactor 4463366925193590644027309453204158022788059292540694291 has 55 digits[/code] P+1 = 2^2 * 3 * 23 * 29^2 * 241 * 11717 * 11789 * 16073 * 177823, so the values used, especially B2, were a big overestimate: [code]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P+1] Input number is 98574137650378747154268459914600766723260038216357693592104375646816403136258801 (80 digits) Using B1=16073, B2=299478, polynomial x^1, x0=4079356229 Step 1 took 78ms Step 2 took 47ms ********** Factor found in step 2: 22085152151389226940117611 Found probable prime factor of 26 digits: 22085152151389226940117611 Composite cofactor 4463366925193590644027309453204158022788059292540694291 has 55 digits[/code] BTW: c55 = 223936174625047412246863 * 19931424356368191892415176213757 |
Fibinocci(1202) 118 digit co-factor.
3949724026510719582327275767874592483696860971400801320378389432836421667088917824217177894469816845043829444138320479 = 26315372138382470904009809410251331242219701 x 150091893275938965565142165169464683420682759092285062166834604838859194179 10/13/09 03:47:03 v1.12 @ Home starting SIQS on c118: 3949724026510719582327275767874592483696860971400801320378389432836421667088917824217177894469816845043829444138320479 10/13/09 03:47:03 v1.12 @ Home, random seeds: 1183955572, 920765628 ..... 10/27/09 21:52:40 v1.12 @ Home, largest cycle: 23 relations 10/27/09 21:52:42 v1.12 @ Home, matrix is 388000 x 388302 (133.3 MB) with weight 33390002 (85.99/col) 10/27/09 21:52:42 v1.12 @ Home, sparse part has weight 33390002 (85.99/col) 10/27/09 21:52:48 v1.12 @ Home, filtering completed in 3 passes 10/27/09 21:52:48 v1.12 @ Home, matrix is 373943 x 374007 (129.4 MB) with weight 32425455 (86.70/col) 10/27/09 21:52:48 v1.12 @ Home, sparse part has weight 32425455 (86.70/col) 10/27/09 21:52:51 v1.12 @ Home, saving the first 48 matrix rows for later 10/27/09 21:52:51 v1.12 @ Home, matrix is 373895 x 374007 (111.7 MB) with weight 29208391 (78.10/col) 10/27/09 21:52:51 v1.12 @ Home, sparse part has weight 27039828 (72.30/col) 10/27/09 21:52:51 v1.12 @ Home, matrix includes 64 packed rows 10/27/09 21:52:51 v1.12 @ Home, using block size 65536 for processor cache size 2048 kB 10/27/09 21:52:58 v1.12 @ Home, commencing Lanczos iteration 10/27/09 21:52:58 v1.12 @ Home, memory use: 89.9 MB 10/27/09 22:18:00 v1.12 @ Home, lanczos halted after 5915 iterations (dim = 373893) 10/27/09 22:18:00 v1.12 @ Home, recovered 17 nontrivial dependencies 10/27/09 22:18:13 v1.12 @ Home, prp44 = 26315372138382470904009809410251331242219701 10/27/09 22:18:45 v1.12 @ Home, prp75 = 150091893275938965565142165169464683420682759092285062166834604838859194179 10/27/09 22:18:45 v1.12 @ Home, Lanczos elapsed time = 1807.8120 seconds. 10/27/09 22:18:45 v1.12 @ Home, Sqrt elapsed time = 44.2190 seconds. 10/27/09 22:18:45 v1.12 @ Home, SIQS elapsed time = 1276301.4065 seconds. 10/27/09 22:18:45 v1.12 @ Home, 10/27/09 22:18:45 v1.12 @ Home, 10/27/09 22:18:53 v1.12 @ Home, Total factoring time = 1403155.5158 seconds I had it minimized in the tray and forgot it was running. |
Impressive result with QS, among the largest jobs YAFU has tackled, to my knowledge!
However, I find it surprising that this number has not already been factored, are you sure it wasn't? Lastly, if you are going to be doing a lot of work with 100+ digit numbers, it would really help to use ggnfs. As much as I like to see my program factor big numbers, it really is a waste of computer energy to use it for numbers this size. See [url=http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html]here[/url] |
[QUOTE=ugly2dog;194044]Fibinocci(1202) 118 digit co-factor.
3949724026510719582327275767874592483696860971400801320378389432836421667088917824217177894469816845043829444138320479 = 26315372138382470904009809410251331242219701 x 150091893275938965565142165169464683420682759092285062166834604838859194179 10/13/09 03:47:03 v1.12 @ Home starting SIQS on c118: 3949724026510719582327275767874592483696860971400801320378389432836421667088917824217177894469816845043829444138320479 10/13/09 03:47:03 v1.12 @ Home, random seeds: 1183955572, 920765628 ..... 10/27/09 21:52:40 v1.12 @ Home, largest cycle: 23 relations 10/27/09 21:52:42 v1.12 @ Home, matrix is 388000 x 388302 (133.3 MB) with weight 33390002 (85.99/col) 10/27/09 21:52:42 v1.12 @ Home, sparse part has weight 33390002 (85.99/col) 10/27/09 21:52:48 v1.12 @ Home, filtering completed in 3 passes 10/27/09 21:52:48 v1.12 @ Home, matrix is 373943 x 374007 (129.4 MB) with weight 32425455 (86.70/col) 10/27/09 21:52:48 v1.12 @ Home, sparse part has weight 32425455 (86.70/col) 10/27/09 21:52:51 v1.12 @ Home, saving the first 48 matrix rows for later 10/27/09 21:52:51 v1.12 @ Home, matrix is 373895 x 374007 (111.7 MB) with weight 29208391 (78.10/col) 10/27/09 21:52:51 v1.12 @ Home, sparse part has weight 27039828 (72.30/col) 10/27/09 21:52:51 v1.12 @ Home, matrix includes 64 packed rows 10/27/09 21:52:51 v1.12 @ Home, using block size 65536 for processor cache size 2048 kB 10/27/09 21:52:58 v1.12 @ Home, commencing Lanczos iteration 10/27/09 21:52:58 v1.12 @ Home, memory use: 89.9 MB 10/27/09 22:18:00 v1.12 @ Home, lanczos halted after 5915 iterations (dim = 373893) 10/27/09 22:18:00 v1.12 @ Home, recovered 17 nontrivial dependencies 10/27/09 22:18:13 v1.12 @ Home, prp44 = 26315372138382470904009809410251331242219701 10/27/09 22:18:45 v1.12 @ Home, prp75 = 150091893275938965565142165169464683420682759092285062166834604838859194179 10/27/09 22:18:45 v1.12 @ Home, Lanczos elapsed time = 1807.8120 seconds. 10/27/09 22:18:45 v1.12 @ Home, Sqrt elapsed time = 44.2190 seconds. 10/27/09 22:18:45 v1.12 @ Home, SIQS elapsed time = 1276301.4065 seconds. 10/27/09 22:18:45 v1.12 @ Home, 10/27/09 22:18:45 v1.12 @ Home, 10/27/09 22:18:53 v1.12 @ Home, Total factoring time = 1403155.5158 seconds I had it minimized in the tray and forgot it was running.[/QUOTE] This makes ZERO sense. Are you sure that you have specified the number correctly??? Even Fibonacci numbers split in half, algebraically!!!! F1202 = F601 * L601 and was completed many, many years ago. |
[QUOTE=R.D. Silverman;194206]This makes ZERO sense. Are you sure that you have specified the number
correctly??? Even Fibonacci numbers split in half, algebraically!!!! F1202 = F601 * L601 and was completed many, many years ago.[/QUOTE] I also checked the Fibonacci website. Currently, there are no composites that have 118 digits....... |
The given factor does indeed divide Fibonacci(1202); indeed, it divides Lucas(601); indeed, the number that's factored is Lucas(601) / (6011 * 16829).
Blair Kelly has collected the factorisations of all Lucas(n) and Fibonacci(n) for all n<1018 (*) and many n<10000 at [url]http://home.att.net/~blair.kelly/mathematics/fibonacci/[/url] and has at [url]http://home.att.net/~blair.kelly/mathematics/fibonacci/smallest.txt[/url] a list of probably-GNFS candidates; figuring out good SNFS candidates among the Fibonacci numbers is left as an exercise for the reader. * This may be one of the few occurrences of '1018' which is [b]not[/b] a typo for 10[SUP]18[/SUP] |
I just now PM'ed Syd, the owner of the factor database. The lucas number entries there are not correct.
|
[QUOTE=fivemack;194217]The given factor does indeed divide Fibonacci(1202); indeed, it divides Lucas(601); indeed, the number that's factored is Lucas(601) / (6011 * 16829).
[/QUOTE] As I said, L601 was completed a LONG time ago. Why was it being done again? |
c113 from 842592:6669 was cracked by ECM as p56*p57
[quote]Factor=39659056817298977052313431042539933940395678655080862877 Method=ECM B1=11000000 Sigma=4281364321[/quote] |
[QUOTE=unconnected;194596]c113 from 842592:6669 was cracked by ECM as p56*p57[/QUOTE]
Finding a p56 with B1 = 11M is very improbable. Please post the group order for this sigma. |
[quote=R.D. Silverman;194672]Finding a p56 with B1 = 11M is very improbable.
Please post the group order for this sigma.[/quote] I thought you knew how to calculate it. Anyway...[code]Magma V2.15-14 Wed Nov 4 2009 01:30:20 [Seed = 3764032704] ------------------------------------- [ <2, 2>, <3, 2>, <7, 1>, <101, 1>, <137, 1>, <211, 1>, <4493, 1>, <4583, 1>, <8179, 1>, <86629, 1>, <110969, 1>, <124139, 1>, <400643, 1>, <762973, 1>, <877386637, 1> ] Total time: 2.350 seconds, Total memory usage: 10.28MB [/code]B1=11000000, min. B1= 762973 B2 maybe was 35133391030 (GMP-ECM default for this B1), min. B2 877386637 Both well within bounds. So well within bounds, in fact, that B1=1M with GMP-ECM's default B2 with this sigma will find the factor. Yes, it's extremely unlikely, but with the info he gave us, I see no reason to doubt it. As for just how unlikely, GMP-ECM says to expect 283939 curves to find a 55-digit factor with that B1 and its default B2. |
[QUOTE=Mini-Geek;194674]I thought you knew how to calculate it. Anyway...[code]Magma V2.15-14 Wed Nov 4 2009 01:30:20 [Seed = 3764032704]
------------------------------------- [ <2, 2>, <3, 2>, <7, 1>, <101, 1>, <137, 1>, <211, 1>, <4493, 1>, <4583, 1>, <8179, 1>, <86629, 1>, <110969, 1>, <124139, 1>, <400643, 1>, <762973, 1>, <877386637, 1> ] Total time: 2.350 seconds, Total memory usage: 10.28MB [/code]B1=11000000, min. B1= 762973 B2 maybe was 35133391030 (GMP-ECM default for this B1), min. B2 877386637 Both well within bounds. So well within bounds, in fact, that B1=1M with GMP-ECM's default B2 with this sigma will find the factor. Yes, it's extremely unlikely, but with the info he gave us, I see no reason to doubt it. As for just how unlikely, GMP-ECM says to expect 283939 curves to find a 55-digit factor with that B1 and its default B2.[/QUOTE] I wasn't doubting it; I was just curious as the the group order. I never seem to get this lucky! I know the algorithms for computing the order. But I do not have any software that actually does it. I have no copies of Magma, Pari, Mathematica, etc. |
[quote=R.D. Silverman;194676]I know the algorithms for computing the order. But I do not have any
software that actually does it. I have no copies of Magma, Pari, Mathematica, etc.[/quote] Oh, ok. I got the code from this post: [URL]http://www.mersenneforum.org/showpost.php?p=56055&postcount=7[/URL] The Magma calculator has since moved to: [URL]http://magma.maths.usyd.edu.au/calc/[/URL] (it works online, which works fine for calculating any group order I've seen, but might not work for larger calculations) |
[CODE]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM]
Input number is 333290344900608194933508421371821217790719930592413794566541523351063376116663003759519239680171163300141221753473967638089669 (126 digits) Using [B]B1=3000000,[/B] B2=5706890290, polynomial Dickson(6), sigma=687558056 Step 1 took 7920ms Step 2 took 4420ms ********** Factor found in step 2: 1892246421565230418535340768938924014883097858799411 Found probable prime factor of 52 digits: 1892246421565230418535340768938924014883097858799411 Probable prime cofactor 176134747093307610021550023590170289685800705301739126718184451260438314279 has 75 digits[/CODE] {aliq.195528:i[U]8005[/U]} |
[QUOTE=Batalov;194899][CODE]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM]
Input number is 333290344900608194933508421371821217790719930592413794566541523351063376116663003759519239680171163300141221753473967638089669 (126 digits) Using [B]B1=3000000,[/B] B2=5706890290, polynomial Dickson(6), sigma=687558056 Step 1 took 7920ms Step 2 took 4420ms ********** Factor found in step 2: 1892246421565230418535340768938924014883097858799411 Found probable prime factor of 52 digits: 1892246421565230418535340768938924014883097858799411 Probable prime cofactor 176134747093307610021550023590170289685800705301739126718184451260438314279 has 75 digits[/CODE] {aliq.195528:i[U]8005[/U]}[/QUOTE] You were lucky. B1=3M is only just above the lowest possible B1 to find that factor. <2, 3>, <3, 2>, <97, 1>, <479, 1>, <997, 1>, <2707, 1>, <74527, 1>, <515401, 1>, <1470401, 1>, <2807087, 1>, <2967491, 1>, <445466003, 1> |
YAGF
105^86 + 86^105 =
10973 * 94871534549590877107381460468659102174881045819957918685521991879 * 127313974445081578469294452799668319338804405453398952109489475656292207910681493583668286596226632148608797954877333676828625803286003 (actually quite a long run; quintic polynomial, 28-bit LP, SP 2^24 on both sides, sieved 2^23 .. 3*2^23 with 64-bit 14e for 26.9M relations at about 0.1s/rel, then 41hrs on dual-core K8/2200 to finish) Tom |
[QUOTE=bsquared;132505]Just finished my largest SNFS to date: 12^163 - 11^163
C176, difficulty 176. Isn't it nice when there are no wasted factors in SNFS jobs :) [code] [SIZE=2]Wed Apr 30 18:33:37 2008 Msieve v. 1.32[/SIZE] [SIZE=2]Wed Apr 30 18:33:37 2008 random seeds: 0f9bbe40 a72a3a5a[/SIZE] [SIZE=2]Wed Apr 30 18:33:37 2008 factoring 80638567651605134105801341144295703524688610355698302434289991680094789293158377759055342137656314689398379368412370811546059861224314747399102796095874850337752864376275025997 (176 digits)[/SIZE] [SIZE=2]Wed Apr 30 18:33:39 2008 searching for 15-digit factors[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 commencing number field sieve (176-digit input)[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 R0: -410186270246002225336426103593500672[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 R1: 23225154419887808141001767796309131[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 A0: -144[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 A1: 0[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 A2: 0[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 A3: 0[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 A4: 0[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 A5: 121[/SIZE] [SIZE=2]Wed Apr 30 18:33:41 2008 size score = 1.380090e-012, Murphy alpha = 0.611155, combined = 1.125728e-012[/SIZE] [SIZE=2]Wed Apr 30 18:34:01 2008 restarting with 9580213 relations[/SIZE] [SIZE=2]Wed Apr 30 18:34:01 2008 [/SIZE] [SIZE=2]Wed Apr 30 18:34:01 2008 commencing relation filtering[/SIZE] [SIZE=2]Wed Apr 30 18:34:01 2008 commencing duplicate removal, pass 1[/SIZE] [SIZE=2]Wed Apr 30 18:35:26 2008 found 858406 hash collisions in [B]9580213 relations[/B][/SIZE] [SIZE=2]Wed Apr 30 18:35:26 2008 commencing duplicate removal, pass 2[/SIZE] [SIZE=2]Wed Apr 30 18:36:10 2008 found 713339 duplicates and [B]8866874 unique relations[/B][/SIZE] [SIZE=2]Wed Apr 30 18:36:10 2008 memory use: 50.6 MB[/SIZE] <snip> [SIZE=2]Wed Apr 30 21:21:26 2008 prp80 factor: 34957698771189765331782973598371343662802452976654329112913699889505994900648923[/SIZE] [SIZE=2]Wed Apr 30 21:21:27 2008 prp97 factor: 2306747025295127756657870419577411038780260831935613811132503821954020694612281320931385429666039[/SIZE] [SIZE=2]Wed Apr 30 21:21:27 2008 elapsed time 02:47:50[/SIZE] [/code] - ben.[/QUOTE] Just stumbled across this one while searching the forum for NFS "pearls of wisdom": Do you still have your poly file - did you do this one with 26 bit large primes? |
27 bit, I believe...
Aha, yes, it was: [CODE] n: 80638567651605134105801341144295703524688610355698302434289991680094789293158377759055342137656314689398379368412370811546059861224314747399102796095874850337752864376275025997 type: snfs skew: 1 c5: 121 c0: -144 Y1: 23225154419887808141001767796309131 Y0: -410186270246002225336426103593500672 rlim: 8000000 alim: 8000000 lpbr: 27 lpba: 27 mfbr: 50 mfba: 50 rlambda: 2.5 alambda: 2.5 [/CODE] |
54-digit ECM factor
Here's a recent 54-digit factor I found with GMP-ECM.
[code] GMP-ECM 6.0 [powered by GMP 4.1.4] [ECM] Input number is 1464101628306218327243090276822854018935464651910463764066214979033633930636362446271755126971623164200983332175440071790729516180679 (133 digits) Using B1=43000000, B2=178426462987, polynomial Dickson(12), sigma=1473889351 Step 1 took 584415ms Step 2 took 186993ms ********** Factor found in step 2: 174071699157900184787364437355306447146342552877155999 Found probable prime factor of 54 digits: 174071699157900184787364437355306447146342552877155999 Probable prime cofactor 8410911339344909091341667306229145403177569945874969629295402028296318670895321 has 79 digits [/code] |
c114 from 15390:626 was cracked by ECM as c60*p55
[quote]#echo 597927055108713748291508574638291501695489098309506381634785109702091216625669589946656654132268730613211062015799 | ecm -v -sigma 2661974196 11000000 GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM] Input number is 597927055108713748291508574638291501695489098309506381634785109702091216625669589946656654132268730613211062015799 (114 digits) Using MODMULN Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=2661974196 dF=32768, k=3, d=324870, d2=11, i0=23 Step 1 took 90829ms ********** Factor found in step 1: 272969751600338039375342766729615709883919925055452090135999 Found composite factor of 60 digits: 272969751600338039375342766729615709883919925055452090135999 Probable prime cofactor 2190451695117318227316629216836407632313501702575320201 has 55 digits[/quote]c60 splits as p29*p31 |
[QUOTE=unconnected;197846]c114 from 15390:626 was cracked by ECM as c60*p55
c60 splits as p29*p31[/QUOTE] There is something about this claim that I simply do not believe. At B = 11M, how could it miss both a p29 and p31 while finding a p55?? This stretches the limits of incredulity. |
[QUOTE=R.D. Silverman;197912]There is something about this claim that I simply do
not believe. At B = 11M, how could it miss both a p29 and p31 while finding a p55?? This stretches the limits of incredulity.[/QUOTE] I thought the c60 was found by ECM, not the p55. Nothing seems wrong about that. |
[quote=10metreh;197915]I thought the c60 was found by ECM, not the p55. Nothing seems wrong about that.[/quote]
You are right, c60 was found. It isn't strange that was с60, instead of p29 or p31? What is probability of that? |
[quote=unconnected;197922]You are right, c60 was found. It isn't strange that was с60, instead of p29 or p31? What is probability of that?[/quote]
i think that the probabiblity of finding the c60 is the probability of finding the p29*probability of finding the p31 |
RSA-170 factored
RSA-170 has been factored by D. Bonenberger and M. Krone with the General Number Field Sieve: [URL="http://public.fh-wolfenbuettel.de/~bonenber/rsa170.txt"]http://public.fh-wolfenbuettel.de/~bonenber/rsa170.txt[/URL]
RSA-170 = 3586420730428501486799804587268520423291459681059978161140231860633948450858040593963 * 7267029064107019078863797763923946264136137803856996670313708936002281582249587494493 |
I just received notification of this via email. I also notice that RSA-180 hasn't been factored yet...
|
[QUOTE=jasonp;200220]I just received notification of this via email. I also notice that RSA-180 hasn't been factored yet...[/QUOTE]
The decimal challenge numbers were replaced by challenge numbers in bits, before they were all dropped. I do remember RSA160 being factored by Franke, et.al. (back when our friend Thorsten was still a second author); it was done as a test case _after_ RSA640. We have two gnfs's queued, EM43 and 2L2254, in the same range as RSA180 --- which seems to indicate that Tom, Greg/NFS@Home and Batalov-Dodson all consider the decimal RSA-challenge numbers as less interesting. By-the-way, there are/were a lot, up to RSA500? -Bruce |
[QUOTE=bdodson;200266]By-the-way, there are/were a lot, up to RSA500?
-Bruce[/QUOTE] For the number see: [URL="http://en.wikipedia.org/wiki/RSA_numbers"]http://en.wikipedia.org/wiki/RSA_numbers[/URL] |
[QUOTE=R. Gerbicz;200301]For the number see: [URL="http://en.wikipedia.org/wiki/RSA_numbers"]http://en.wikipedia.org/wiki/RSA_numbers[/URL][/QUOTE]
Interesting. Arjen's post on the factorization of RSA130 lists "Bruce Dodson (Lehigh)" as the single largest sieving contributor, 28%; but I don't appear to have made the NMBRTHRY post. I was a coauthor on the paper, but that doesn't appear to have been sufficient to make the wiki. Ah, Herman's report on the factorization of RSA140 does include me (26.6% this time), and his reference for RSA130 is [code] [Cetal] Cowie, Dodson, E.-H., Lenstra, Montgomery, Zayer, AsiaCrypt'96 Springer LNCS #1163 [/code] The link used for the wiki credit is for postprocessing, rather than the factorization. The title of the RSA130 paper's pehaps still of some current interest [code] A world wide number field sieve factoring record: on to 512-bits [/code] as 17.7% of the sieving was from "the www-factoring project" (including Furmanski). Arjen does mention sieving as having started in Sept, with the www-project picking up late, in Dec. As I recall, they were at 2.2% near the end of sieving; and made a late push to hit their 17.7. But anyway, this was the second web-based factoring project (17.7%, at least); following the Lenstra-Manasse "factor by email" project, which included early ecm, and QS, but is best remembered for the first snfs (a C138) and then F8, the 512-bit snfs number. Sieving factorization has _always_ been a leading distributed computing app; and we're now in c. 4th generation with NFS@Home/BOINC (3rd having been NFSNet). ECM as well. Best ever, maybe? -bd PS -- Ah, so on R. Gerbicz's post; RSA500 was only the last of the sequence RSA100, RSA110, ..., RSA500 going up by 10-decimal digits each; but there was also RSA617 (= RSA2048) before the binary ones, and RSA155 (=RSA512) as well ... Hmm. If we're looking for a non-gratuitous number, looks like there's RSA704, between RSA640 and RSA768. And RSA232 is decimal. Ah, and a different 768-bit number. Looks like there was an intermediate decimal list tracking the 64-bit binary increments. Oops, that was RSA617, 2048-bits, but different than RSA2048. Who knew? |
almost nice split from alq10212.2244 c127:
[CODE]Thu Jan 7 12:06:06 2010 prp63 factor: 455221926972731082673883906812910052211479159961891753702147573 Thu Jan 7 12:06:06 2010 prp64 factor: 5525567792780249685649634474569027312570329396141714860660336861[/CODE] |
Pretty nice for a B1=1.5M
[FONT=Arial Narrow]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM] Input number is 73727933541017653167185877466251298026998961578400830737279335410176531671858774662512980269989615784008307372793354101765316718587746625129802699896157840083073727933541017653167185877466251298027 (197 digits) Using B1=1500000, B2=2140044280, polynomial Dickson(6), sigma=987115356 Step 1 took 7120ms Step 2 took 3900ms ********** Factor found in step 2: 18195047252241968932445162733612535247087014043 Found probable prime factor of 47 digits: 18195047252241968932445162733612535247087014043 Probable prime cofactor 4052088050056204039119907675067446997048585489235726975662931358397142316627117355006880321551792793362790686617388639518444629688194109725667368917489 has 151 digits[/FONT] |
[QUOTE=Batalov;204702][FONT=Arial Narrow]Probable prime cofactor 4052088050056204039119907675067446997048585489235726975662931358397142316627117355006880321551792793362790686617388639518444629688194109725667368917489 has 151 digits[/FONT][/QUOTE]Using Dario's ECM applet, it says that it is prime!
|
When I found a p37 factor with B1=5e4 on 3 January, I thought that was lucky. But now:
[code]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM] Input number is 843169125898519813628602521233377841138740530817746772120057123378260425682281979199 (84 digits) Using B1=[color=red]50000[/color], B2=12746592, polynomial x^2, sigma=2765250738 Step 1 took 656ms Step 2 took 532ms ********** Factor found in step 2: 38524357812610479457509335800735476146693 Found probable prime factor of 41 digits: 38524357812610479457509335800735476146693 Probable prime cofactor 21886649739882715622844451102347639054569843 has 44 digits[/code] (c84 is from line 1257 of aliquot sequence 819600) :toot: Does anyone know what the biggest factor ever found with 5e4 is? |
[quote=10metreh;206811]When I found a p37 factor with B1=5e4 on 3 January, I thought that was lucky. But now:
[code]GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM] Input number is 843169125898519813628602521233377841138740530817746772120057123378260425682281979199 (84 digits) Using B1=[COLOR=red]50000[/COLOR], B2=12746592, polynomial x^2, sigma=2765250738 Step 1 took 656ms Step 2 took 532ms ********** Factor found in step 2: 38524357812610479457509335800735476146693 Found probable prime factor of 41 digits: 38524357812610479457509335800735476146693 Probable prime cofactor 21886649739882715622844451102347639054569843 has 44 digits[/code](c84 is from line 1257 of aliquot sequence 819600) :toot: Does anyone know what the biggest factor ever found with 5e4 is?[/quote] [ <2, 3>, <3, 1>, <5, 1>, <41, 1>, <53, 1>, <83, 1>, <433, 1>, <557, 1>, <601, 1>, <739, 1>, <2309, 1>, <9613, 1>, <11633, 1>, <32839, 1>, <1959701, 1> ] |
[QUOTE=10metreh;206811]Does anyone know what the biggest factor ever found with 5e4 is?[/QUOTE]I don't. Perhaps this is something we could ask PaulZ to record along with his table of largest factors found with any B1/B2 value.
A major problem is that the probability of finding a factor does not depend solely on the B1 value. B2 is important. Even more important is the number of curves run. How would you propose to incorporate this into a table of champions? Paul |
A nice split
r2/r1 is just about 1.013
Number: 29999_192 N=96147100344714093985880165790142508713790938454554091728820058311092885918809960853895469472773862773301432799536380961132175497 ( 128 digits) Divisors found: r1=9740471141873076715269094836964843996395634689724625712596839367 r2=9870888065300008002666195086781466583752845796759751444217049391 Version: Total time: 70.00 hours. Scaled time: 167.45 units (timescale=2.392). Factorization parameters were as follows: # Murphy_E = 9.470857e-11, selected by Jeff Gilchrist n: 96147100344714093985880165790142508713790938454554091728820058311092885918809960853895469472773862773301432799536380961132175497 Y0: -4728337515127376913733073 Y1: 113391337021723 c0: -68746208699076990334683890878800 c1: 2556257913066612300971980446 c2: -15170833482453671465739 c3: -20681738268242644 c4: 50385102936 c5: 40680 skew: 464131.78 type: gnfs # selected mechanically rlim: 8000000 alim: 8000000 lpbr: 28 lpba: 28 mfbr: 54 mfba: 54 rlambda: 2.5 alambda: 2.5 Factor base limits: 8000000/8000000 Large primes per side: 3 Large prime bits: 28/28 Max factor residue bits: 54/54 Sieved algebraic special-q in [4000000, 8400001) Primes: rational ideals reading, algebraic ideals reading, Relations: 19065947 Max relations in full relation-set: Initial matrix: Pruned matrix : 1260002 x 1260249 Total sieving time: 61.63 hours. Total relation processing time: 4.29 hours. Matrix solve time: 3.76 hours. Time per square root: 0.33 hours. Prototype def-par.txt line would be: gnfs,127,5,maxs1,maxskew,goodScore,efrac,j0,j1,eStepSize,maxTime,8000000,8000000,28,28,54,54,2.5,2.5,100000 total time: 70.00 hours. --------- CPU info (if available) ---------- Intel(R) Core(TM)2 Quad CPU Q6700 @ 2.66GHz stepping 0b Intel(R) Core(TM)2 Quad CPU Q6700 @ 2.66GHz stepping 0b Intel(R) Core(TM)2 Quad CPU Q6700 @ 2.66GHz stepping 0b Memory: 8046640k/8912896k available (2550k kernel code, 339524k reserved, 1291k data, 208k init) Calibrating delay loop (skipped), value calculated using timer frequency.. 5345.61 BogoMIPS (lpj=2672808) Calibrating delay using timer specific routine.. 5344.68 BogoMIPS (lpj=2672344) Calibrating delay using timer specific routine.. 5344.67 BogoMIPS (lpj=2672339) Calibrating delay using timer specific routine.. 5237.81 BogoMIPS (lpj=2618905) |
Five factors between 23 and 30 digits
aliquot sequence 1920 index 2124 splits as 2^2 . 3 . 7 . 97 . 12611 . P23 . P25 . P26 . P28 . P30
with large factors 43715010634395960945991 8257710475368317381357887 14062317576359023621153853 2136527974410831993786057559 849472442753123035317600227699 which is quite pretty and vaguely surprising. |
Well, I've just recently noticed another similar curio:
[quote=Batalov;206323]Nice line with p23.p24.p25.p25.p25 -- [code]556276:6779 . 788871340341057562889230923678722189737792940800022551501177995987544153414255611539335238436104792425694403749441775012787706257880 = 2^3 * 5 * 883 * 27079631 * 91094766202869033075899 * 361000310979526340890151 * 1248561491484813471034241 * 2030361154450937185791841 * 9893694771484052066672231[/code][/quote] (I went on to check some old .elf files; didn't find anything similar in 3 million lines.) |
[QUOTE=Yeong Uk Jo;207222]r2/r1 is just about 1.013
Number: 29999_192 N=96147100344714093985880165790142508713790938454554091728820058311092885918809960853895469472773862773301432799536380961132175497 ( 128 digits) Divisors found: r1=9740471141873076715269094836964843996395634689724625712596839367 r2=9870888065300008002666195086781466583752845796759751444217049391 [/QUOTE]Darn....missed it by [i]that[/i] much. This is from aliquot sequence 171018:1932. r2/r1 is 1.016.[code]factoring 2769699872893724998777280362628763246881778451759748760598693420616396464782953 (79 digits) prp40 factor: 1650731648154373712516554591214197107991 prp40 factor: 1677861980771030335098583193907462086783[/code] |
RSA-180 factored
RSA-180 =
400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377 * 476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833 A [URL="http://en.wikipedia.org/w/index.php?title=RSA_numbers&diff=prev&oldid=361109802"]Wikipedia edit[/URL] by an IP address registered in Moscow says: "RSA-180 was factored on May 8, 2010 by S. A. Danilov and I. A. Popovyan from Moscow State University, Russia. The factorization was found using the [URL="http://en.wikipedia.org/wiki/General_Number_Field_Sieve"]General Number Field Sieve[/URL] algorithm implementation running on 3 Intel Core i7 PCs." I haven't seen other mention of this. Wikipedia is not always reliable but the factorization is correct. |
My first p50-digit factor in two years (a.f.a.i.r. ...I had a p56 in the first day of my ECMing, but nothing but a few p49s in between; granted, I never ECMed just for ECMing)...
[FONT=Arial Narrow]Input number is 276249363376530523409280639717315262381353781466043253655792070660429289799029604351245743892224245080473070069478798426088869000784041 (135 digits)[/FONT] [FONT=Arial Narrow]Run 1317 out of 2000: Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=2708170207 Step 1 took 30665ms Step 2 took 15273ms ********** Factor found in step 2: [/FONT] [FONT=Arial Narrow]Found probable prime factor of 50 digits: 11503934461120817806394297433479143709264161283779 Probable prime cofactor has 86 digits[/FONT] |
(41^137-1)/40
ECM to t50 was done by yoyo@home SNFS sieving was done by RSALS Post Processing was done by Michael Rao This is a Brent composite that had no known factors. P66 x P155 [code] P66: 161033973705341754697154184520324001898167340683045689065770231389 P155: 13880684065684569491359317232294346200171620088300352485145905214604506443519652814063086066838446421188243573906274202230093165037609560104584786537650493[/code] |
Another Brent Composite with no known factors
(229^103-1)/228 ECM to t50 was done by yoyo@home SNFS sieving was done by RSALS Post Processing was done by Jeff Gilchrist P57 x P185 [code]P57: 268362433332419607426712500668487479781321407137778067937 P185: 18897228431405738066692044884523569849973250950468415595822949505504061540201281773035338111521604479828346442753167705447548016373710008855028996830938575885167309088122242073769290283[/code] |
c103 with a 3-way split (from aliquot sequence 41916):
[CODE]prp34 factor: 3351171782449542012498325222773137 prp34 factor: 7542144712915888051238977936543171 prp35 factor: 67340189601709029451666811897595767[/CODE] smells a bit like an ECM miss. (this one [I]has had[/I] 651@1e6). |
Another day, another p50:
3,1317M c150 = [FONT=Arial Narrow]Input number is 134334378587665946471267183035011069371867992103492968128193357546608845318563925400458505568168559187151459935412018714514857987996669119402175614727 (150 digits) Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=212849622 Step 1 took 35863ms Step 2 took 17481ms ********** Factor found in step 2: Found probable prime factor of 50 digits: 15625305790155774800504213544664082865394459261063 Probable prime cofactor has 100 digits [/FONT] |
Brent composites with no previously known factors of 12 or more digits. 211^103-1 was cracked in ECM prefactoring. 727^79-1 had
yoyo@home ECM through t50 RSALS SNFS sieving [code] 211^103-1 P46: 2673016773059390866847396713181717347377970273 P177: 168844400309543224776452178164986374130705983357226294632545828012827726753318999768883684415379024810376371450320366427976170084341903852792493402065981811174062733171985132393 727^79-1 P83: 79100334539201141396745982114077306712457214343784359318799331632881963257976907911 P141: 200494986318800422795008525000394773223643771305790583027076117436533593190553667229530696982229261743140802717175917985282255592480093908767 [/code] |
Two more Brent composites with no previously known factors. Both 3-way splits!
yoyo@home ECM through t50 RSALS SNFS sieving Zeta-flux post processing [code] 89^127-1 P73: 1542584165434188558612221936635610306778187202197322724416250064619485969 P83: 42144825992878691648173420252403116194671322494572303686656733963019004462527718251 P91: 6532133283972835794382402793231305032201025006812273619032758128189442472270068318927914549 149^113-1 P61: 4569559907373826702264262051063478068210801364456001155971749 P64: 1152939018693409402929137393489825913238036240799210582829324917 P120: 476547178626480187177080584502781689594303653541238606260232084509441154197582254915773854376306170062651904606800566697 [/code] |
Gratuitious pretty thing
aliquot 8352 term 1644:
[code] prp74 factor: 44329974027102880693818435089160800889366296733560132544266413065572660437 prp75 factor: 443229449797114236892000988227975424999586166370410892032904641950100995803 [/code] |
Another 3-way split for a Brent composite with no previously known factors.
yoyo@home ECM through t50 RSALS SNFS sieving Jeff Gilchrist post processing [code] 241^97-1: P59: 22262439588426127312176939919585003986195622459798868964251 P66: 296718988305708628532234459882263254001581931236312842841776780497 P105: 717007658591148002638962287337974607052540471568034084769294811772172349055422379034148722337528949589571[/code] |
2803^79+1 = [URL="http://factordb.com/search.php?id=16882"][COLOR=#000000]22[/COLOR][/URL] * [URL="http://factordb.com/search.php?id=1471"][COLOR=#000000]701[/COLOR][/URL] * [URL="http://factordb.com/search.php?id=14472"][COLOR=#000000]2687[/COLOR][/URL] * [URL="http://factordb.com/search.php?id=302283"][COLOR=#000000]35393[/COLOR][/URL] * [URL="http://factordb.com/search.php?id=1173756"][COLOR=#000000]61463[/COLOR][/URL] * [URL="http://factordb.com/search.php?id=6948588"][COLOR=#000000]4093307[/COLOR][/URL] * p10 * p 12 * p17* p22*p191
|
RSA-119
[URL="http://www.loria.fr/~zimmerma/records/rsa.html"]RSA-119[/URL] = P60 * Q60
P60 = 106582741029862212583249815536611312249501518146343497063387 Q60 = 520907515065337429500108915077818773621294300970429704758393 P60 - 1 = 2 * 11 * 599597 * P52 P60 + 1 = 2^2 * 3^5 * 1487 * 7559 * 46551476728292341783 * P30 Q60 - 1 = 2^3 * 7 * 283 * 51197 * 81667 * 90122494145897 * P32 Q60 + 1 = 2 * 3 * 19 * 37 * 454738643 * P48 |
[QUOTE=warut;221136][URL="http://www.loria.fr/~zimmerma/records/rsa.html"]RSA-119[/URL] = P60 * Q60
P60 = 106582741029862212583249815536611312249501518146343497063387 Q60 = 520907515065337429500108915077818773621294300970429704758393 P60 - 1 = 2 * 11 * 599597 * P52 P60 + 1 = 2^2 * 3^5 * 1487 * 7559 * 46551476728292341783 * P30 Q60 - 1 = 2^3 * 7 * 283 * 51197 * 81667 * 90122494145897 * P32 Q60 + 1 = 2 * 3 * 19 * 37 * 454738643 * P48[/QUOTE] AFAIK, there is no "RSA-119". |
The link points to Paul Zimmermann's page. Now he'll have to pick another RSA number to keep away the misguided people with new algorithms (I wonder if he gets any such people...)
|
| All times are UTC. The time now is 23:21. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.