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 :bob:

C177_148_94 was suggested as GNFS, but its SNFS difficulty is not too high:

Difficulty 248: 4879681*(47[sup]24[/sup])[sup]6[/sup] + 29986576*(2[sup]6[/sup]*37[sup]15[/sup])[sup]6[/sup] = 58008018918812545143463727211454278525294078099759247887923759309261425 * C177

Difficulty 254: 1369*(47[sup]25[/sup])[sup]6[/sup] + 35344*(2[sup]6[/sup]*37[sup]16[/sup])[sup]6[/sup] = 175423268180778312831796670198430324228190852757122036482075886926082969832425 * C177

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
[/code]

The sextic SNFS polynomial produced by snfspoly has hideous coefficients, yeah... but a quintic of that SNFS difficulty is no piece of cake either.

[QUOTE=swellman;430943]

[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
[/code][/QUOTE]

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.

[QUOTE=bsquared;430976]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.[/QUOTE]

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 [i]likely[/i] best solved via GNFS.

[QUOTE=swellman;430979]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.
[/QUOTE]

You've used it a lot more than I have :smile:. 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.

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.

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!

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[/code]
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.

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?