mersenneforum.org GNFS targets which need more ECM
 Register FAQ Search Today's Posts Mark Forums Read

 2016-04-02, 18:56 #34 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 144668 Posts 10400 stage-1 curves run on C190_149_91, 84% of them taken to stage 2, found a P55 but it turns out that it had already been submitted
 2016-04-03, 23:56 #35 XYYXF     Jan 2005 Minsk, Belarus 24·52 Posts C177_148_94 was suggested as GNFS, but its SNFS difficulty is not too high: Difficulty 248: 4879681*(4724)6 + 29986576*(26*3715)6 = 58008018918812545143463727211454278525294078099759247887923759309261425 * C177 Difficulty 254: 1369*(4725)6 + 35344*(26*3716)6 = 175423268180778312831796670198430324228190852757122036482075886926082969832425 * C177
 2016-04-07, 11:00 #36 swellman     Jun 2012 23×13×37 Posts C177_148_94 is on the list of possible GNFS candidates because the best SNFS poly I could find using Yafu would take an estimated 247M core-seconds to sieve versus ~85M core-seconds using GNFS. If my estimates are off then perhaps GNFS is not the best path forward. Can anybody provide a quick and dirty GNFS poly we can test with? Using an ECM rule of thumb of 0.31*GNFS gives ~t55, which this number has already survived. The 5000 curves @B1=26e7 listed in this thread may be unnecessary though certainly prudent (for peace of mind if nothing else). Best SNFS poly I found follows: Code: n: 509324937687618809222445320276337252810119679947032399409215533120195327608346172383916906170272967333837017570484086026229163006167878198943819573285050609840596958297287281873 # 148^94+94^148, difficulty: 248.37, anorm: 3.92e+033, rnorm: -1.41e+055 # scaled difficulty: 251.97, suggest sieving rational side # size = 1.438e-017, alpha = 0.000, combined = 7.015e-014, rroots = 1 type: snfs size: 248 skew: 20.7443 c5: 1 c0: 3841451 Y1: -3096263264537031876137686856267255616967297523567 Y0: 159982589693655584703558945119488 rlim: 57000000 alim: 57000000 lpbr: 31 lpba: 31 mfbr: 62 mfba: 62 rlambda: 2.7 alambda: 2.7
 2016-04-07, 20:40 #37 debrouxl     Sep 2009 3D316 Posts The sextic SNFS polynomial produced by snfspoly has hideous coefficients, yeah... but a quintic of that SNFS difficulty is no piece of cake either.
2016-04-07, 20:54   #38
bsquared

"Ben"
Feb 2007

22×3×311 Posts

Quote:
 Originally Posted by swellman Code: n: 509324937687618809222445320276337252810119679947032399409215533120195327608346172383916906170272967333837017570484086026229163006167878198943819573285050609840596958297287281873 # 148^94+94^148, difficulty: 248.37, anorm: 3.92e+033, rnorm: -1.41e+055 # scaled difficulty: 251.97, suggest sieving rational side # size = 1.438e-017, alpha = 0.000, combined = 7.015e-014, rroots = 1 type: snfs size: 248 skew: 20.7443 c5: 1 c0: 3841451 Y1: -3096263264537031876137686856267255616967297523567 Y0: 159982589693655584703558945119488 rlim: 57000000 alim: 57000000 lpbr: 31 lpba: 31 mfbr: 62 mfba: 62 rlambda: 2.7 alambda: 2.7
Was this the winner of the automated test sieving in yafu? For numbers of this size it is probably worthwhile to do more test sieving, especially if the sextics were close performance-wise. Chunks of 2 to 5k special-q in several locations throughout the estimated sieve region.

2016-04-07, 21:56   #39
swellman

Jun 2012

1111000010002 Posts

Quote:
 Originally Posted by bsquared Was this the winner of the automated test sieving in yafu? For numbers of this size it is probably worthwhile to do more test sieving, especially if the sextics were close performance-wise. Chunks of 2 to 5k special-q in several locations throughout the estimated sieve region.
It is the optimal Yafu answer. I've done several hundred of these, and the decision on whether a Yafu generated poly is optimal is usually an obvious yes/no or "it doesn't matter", meaning two polys are so close in performance that even if the ultimate winner turns out to be slightly suboptimal it's so close to the optimal solution that the total sieving time difference is near negligible. Just my opinion of course.

I have found a lot of scatter when plotting sieving times vs SNFS difficulty - hardly surprising - and this particular case is especially hideous as Lionel notes. It's just a case where the ugly SNFS poly can likely be beat by a decent GNFS poly.

That said, of course we can use SNFS to factor this number. My list is hardly authoritative - it's just a set of candidates that are likely best solved via GNFS.

2016-04-07, 22:02   #40
bsquared

"Ben"
Feb 2007

1110100101002 Posts

Quote:
 Originally Posted by swellman It is the optimal Yafu answer. I've done several hundred of these, and the decision on whether a Yafu generated poly is optimal is usually an obvious yes/no or "it doesn't matter", meaning two polys are so close in performance that even if the ultimate winner turns out to be slightly suboptimal it's so close to the optimal solution that the total sieving time difference is near negligible. Just my opinion of course.
You've used it a lot more than I have . Just pointing out that if two polynomials are "nearly the same", then the differences are magnified when applied to very large sieving tasks. You're right that the better question in this case is probably SNFS vs. GNFS.

 2016-04-07, 22:24 #41 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2·2,819 Posts I'll let a GPU run a few hours to get an "in the vicinity" poly for your comparison task this evening. We can estimate the improvement for a full poly-search using the estimated-good poly score that msieve produces in case the test is inconclusive.
 2016-04-07, 22:27 #42 swellman     Jun 2012 23·13·37 Posts Agreed. Before embarking on a big factoring job, one should definitely perform extensive test sieving. 1% difference in performance is negligible when it's a 1000 hour job, not so much when it's 200000 hours. So back to an earlier question - does anyone have a quick and dirty GNFS poly so we can decide a path forward? ETA: thanks VBCurtis! Last fiddled with by swellman on 2016-04-07 at 22:28
 2016-04-08, 03:03 #43 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2×2,819 Posts 2 GPU-hr produced this: Code: N 509324937687618809222445320276337252810119679947032399409215533120195327608346172383916906170272967333837017570484086026229163006167878198943819573285050609840596958297287281873 SKEW 44744195.26 R0 -15372279160491459270723477022022637 R1 42075573946251179 A0 -28036751366398061170413492158368626575647616 A1 2446095126548667802453043510317136360 A2 132445682988042341783594025606 A3 -4958312126359633450937 A4 102677914180448 A5 593340 skew 44744195.26, size 2.117e-17, alpha -7.554, combined = 1.104e-13 rroots = 3 Msieve says target score is 1.22e-13, but this poly exceeds the previous best found for a c178 on the forum, so it's at least decent. I'd guess 7-10% improvement for a full search.
 2016-04-08, 16:33 #44 swellman     Jun 2012 23·13·37 Posts I ran some test sieving using a Win64 box with an i5-3340M processor. Results follow, but GNFS is the clear winner. poly siever lpbr/a a/r ETA (wks) yield a/rlim (M) spec_Q0 (M) spec_Q range gnfs 15e 31 a 55 1.70 120 40 4000 gnfs 14e 31 a 61 0.78 120 40 4000 gnfs 15e 31 a 56 1.58 150 50 4000 gnfs 14e 31 a 65 0.74 150 50 4000 snfs 15e 31 r 108 1.32 57 28.5 4000 snfs 14e 31 r 83 0.58 57 28.5 4000 snfs 14e 31 r 82 0.58 57 28.5 10000 gnfs 15e 31 a 49 1.68 150 50 10000 Do we need to run more ECM (5000 curves @B1=26e7) prior to starting GNFS?

 Similar Threads Thread Thread Starter Forum Replies Last Post XYYXF XYYXF Project 87 2022-04-27 10:59 XYYXF XYYXF Project 57 2017-07-04 19:15 XYYXF XYYXF Project 25 2016-11-20 21:35 pinhodecarlos NFS@Home 0 2014-12-24 19:13 pinhodecarlos NFS@Home 34 2014-04-01 21:27

All times are UTC. The time now is 18:37.

Sat Feb 4 18:37:18 UTC 2023 up 170 days, 16:05, 1 user, load averages: 0.94, 1.04, 0.99