GNFS targets which need more ECM - Page 4

fivemack · 2016-04-02, 18:56

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

XYYXF · 2016-04-03, 23:56

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

Difficulty 248: 4879681*(47²⁴)⁶ + 29986576*(2⁶*37¹⁵)⁶ = 58008018918812545143463727211454278525294078099759247887923759309261425 * C177

Difficulty 254: 1369*(47²⁵)⁶ + 35344*(2⁶*37¹⁶)⁶ = 175423268180778312831796670198430324228190852757122036482075886926082969832425 * C177

swellman · 2016-04-07, 11:00

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

debrouxl · 2016-04-07, 20:40

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

bsquared · 2016-04-07, 20:54

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.

swellman · 2016-04-07, 21:56

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.

bsquared · 2016-04-07, 22:02

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.

VBCurtis · 2016-04-07, 22:24

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.

swellman · 2016-04-07, 22:27

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!

VBCurtis · 2016-04-08, 03:03

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.

swellman · 2016-04-08, 16:33

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?

2016-04-07, 11:00	#36
swellman Jun 2012 2²·13·59 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, 22:27	#42
swellman Jun 2012 2²×13×59 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Ready GNFS targets	XYYXF	XYYXF Project	86	2020-03-07 16:23
SNFS targets which need more ECM	XYYXF	XYYXF Project	57	2017-07-04 19:15
Ready SNFS targets	XYYXF	XYYXF Project	25	2016-11-20 21:35
3,697+ (GNFS 220.9)	pinhodecarlos	NFS@Home	0	2014-12-24 19:13
3,766+ (GNFS 215.5)	pinhodecarlos	NFS@Home	34	2014-04-01 21:27

2016-04-02, 18:56	#34
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1913₁₆ 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 620₈ Posts	C177_148_94 was suggested as GNFS, but its SNFS difficulty is not too high: Difficulty 248: 4879681(47²⁴)⁶ + 29986576(2⁶37¹⁵)⁶ = 58008018918812545143463727211454278525294078099759247887923759309261425 C177 Difficulty 254: 1369(47²⁵)⁶ + 35344(2⁶37¹⁶)⁶ = 175423268180778312831796670198430324228190852757122036482075886926082969832425 C177

2016-04-07, 20:40	#37
debrouxl Sep 2009 977 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, 22:24	#41
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 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-08, 16:33	#44
swellman Jun 2012 2²×13×59 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?