Polynomial Request Thread - Page 210

swellman · 2022-10-23, 23:10

Quote:

Originally Posted by VBCurtis

I think this job is fastest as a 34/34LP with MFB of 66-67/98-99, but for test-sieving we should either use lims that nfs@home would use with ggnfs (like 200/260) *or* use larger & faster lims like 350/500M but test-sieve with CADO.

May as well test-sieve using the settings and tools that will be used to run the factorization, you know?

I will test sieve both polys using ggnfs on the -a side with 34/34, MFB 67/99, lims of 190/260, and lambdas = mfb / log2(lim) + 0.05, i.e. (2.5/3.6), Q in batches of 1000 at Q of 65, 100, 150, 200, 250, 300, 350… until 1.9B estimated # of raw relations is reached. This is a baseline comparison to settle the issue of deg 5 or 6. I suspect the test will show a deg 5 works best, and if so then we will continue looking for one with the highest escore practicable. But if the current best deg 6 poly is say 40% better than deg 5 right now, perhaps we can stop searching the deg 5 space? If memory serves, the crossover point is over 210 and if so this exercise will likely confirm it yet again.

Quote:

alambda of 4.6 seems crazy for this test- is that a typo?

No idea. I won’t test with this value.

wombatman · 2022-10-24, 00:37

Quote:

Originally Posted by VBCurtis

I think this job is fastest as a 34/34LP with MFB of 66-67/98-99, but for test-sieving we should either use lims that nfs@home would use with ggnfs (like 200/260) *or* use larger & faster lims like 350/500M but test-sieve with CADO.

May as well test-sieve using the settings and tools that will be used to run the factorization, you know?

alambda of 4.6 seems crazy for this test- is that a typo?

It wasn't a typo. I was just trying a wide array of parameter values to try and get a sense for where the optimums might be. It was sized well above any composites I had worked on, so I didn't have a good feel for it.

swellman · 2022-10-25, 18:40

Just FYI, I’m still test sieving the best deg 5 and 6 polys as a sanity check.

Also CADO just finished searching a5 of 5-25M (and multiples thereof) but found nothing worth reporting. Moving on to a5 of 25-50M. Results expected within a week.

wombatman · 2022-10-26, 05:17

Quote:

Originally Posted by swellman

Just FYI, I’m still test sieving the best deg 5 and 6 polys as a sanity check.

Also CADO just finished searching a5 of 5-25M (and multiples thereof) but found nothing worth reporting. Moving on to a5 of 25-50M. Results expected within a week.

Appreciated as always. MSieve is still moving the 197MB .ms file. Only two hits above 1.25e-15 were posted.

swellman · 2022-10-27, 13:28

Test sieving results of HP2 (4496) i314 on 16e using 34/34-bit LPBs. I tweaked a couple of parameters from my earlier posted plans but these are very minor. All sieving used ggnfs run single threaded on an 80% tasked 24-core Haswell. The timing data seems a bit noisy due to all the other work so take it with a grain of salt.

As a check, early on I ran a few comparative tests with the smaller lim on the sieving side (i.e. rlim = 260M, alim = 190M) but this strategy generated fewer relations than the one used below.

Degree 6 (escore = 1.856e-15):

Code:

n: 8095101662371927421703337019465587498085337648622133688278589711654019359923503887978141510461468343349838217540569173400647791769725685803537804186347867144149599002247585690859122186539724272741806859085719
skew: 140138.379
type: gnfs
lss: 0
c0: 25913254528907171652995260756449843374970
c1: -1290547516892777857501992555209822939
c2: 6199518954766254144637219981714
c3: 264525951419727864944487871
c4: 67907082683742692904
c5: -4745861603713440
c6: 4669896000
Y0: -2803680302662889860338703572179527
Y1: 1891192000626364510493327
rlim: 190000000
alim: 260000000
lpbr: 34
lpba: 34
mfbr: 67
mfba: 99
rlambda: 2.5
alambda: 3.66

Results of sieving on the algebraic side with Q in blocks of 1000:

Code:

MQ        Norm_yield      Speed (sec/rel)
65           4690              0.656
100          4037              0.763
150          3400              0.734
200          3108              0.798
250          2828              0.849
300          2592              0.902
350          2411              0.852
400          2039              1.110
500          2138              1.107
600          1998              1.143
700          1919              1.341
800          1883              1.195

Suggesting a sieving range for Q of 65-790M to generate 1.8e9 raw relations.

Degree 5 (escore = 1.297e-15):

Code:

n: 8095101662371927421703337019465587498085337648622133688278589711654019359923503887978141510461468343349838217540569173400647791769725685803537804186347867144149599002247585690859122186539724272741806859085719
skew: 771127364.56
type: gnfs
lss: 0
Y0: -17068243492239505219994785346910834818341
Y1: 1873940548553722757
c0: 165792391853474935561243616954647727516748946250496
c1: 2160239644350504494844955872920952825447896
c2: -21514458180493538566295548810659238
c3: -5887571126475837688637761
c4: 35919796435243602
c5: 5588280
rlim: 190000000
alim: 260000000
lpbr: 34
lpba: 34
mfbr: 67
mfba: 99
rlambda: 2.5
alambda: 3.66

Results of test sieving on the algebraic side with Q in blocks of 1000:

Code:

MQ       Norm_yield      Speed (sec/rel)
65          3142              0.943
100         2971              0.848
150         2776              1.002
200         2702              0.899
250         2616              0.864
300         2432              1.112
350         2414              0.959
400         2334              0.978
500         2153              1.032
600         2122              1.213
700         2032              1.199
800         1957              1.283
840         1911              1.165

Suggesting a sieving range for Q of 65-835M to generate 1.8e9 raw relations.

Comparing the performance of the two polynomials, if we had to choose today then the degree 6 clearly wins. But based on the respective sieving ranges

Degree 6: 65-790M = 725M

Degree 5: 65-835M = 770M

the degree 6 is only ~6% "better" than the current degree 5. As such, if we can find a degree 5 polynomial > 1.06 * 1.297e-15 = 1.378e-15 or say 1.38e-15 then we have a competitive (or better) degree 5.

All back of the envelope of course, perhaps others can provide a deeper analysis. But I think finding even a near record degree 5 (record 208 is 1.439e-15) will be the optimal path for sieving. Now we just have to find it!

wombatman · 2022-10-28, 01:18

Quote:

Originally Posted by swellman

Test sieving results of HP2 (4496) i314 on 16e using 34/34-bit LPBs. I tweaked a couple of parameters from my earlier posted plans but these are very minor. All sieving used ggnfs run single threaded on an 80% tasked 24-core Haswell. The timing data seems a bit noisy due to all the other work so take it with a grain of salt.

As a check, early on I ran a few comparative tests with the smaller lim on the sieving side (i.e. rlim = 260M, alim = 190M) but this strategy generated fewer relations than the one used below.

Degree 6 (escore = 1.856e-15):

Code:

n: 8095101662371927421703337019465587498085337648622133688278589711654019359923503887978141510461468343349838217540569173400647791769725685803537804186347867144149599002247585690859122186539724272741806859085719
skew: 140138.379
type: gnfs
lss: 0
c0: 25913254528907171652995260756449843374970
c1: -1290547516892777857501992555209822939
c2: 6199518954766254144637219981714
c3: 264525951419727864944487871
c4: 67907082683742692904
c5: -4745861603713440
c6: 4669896000
Y0: -2803680302662889860338703572179527
Y1: 1891192000626364510493327
rlim: 190000000
alim: 260000000
lpbr: 34
lpba: 34
mfbr: 67
mfba: 99
rlambda: 2.5
alambda: 3.66

Results of sieving on the algebraic side with Q in blocks of 1000:

Code:

MQ        Norm_yield      Speed (sec/rel)
65           4690              0.656
100          4037              0.763
150          3400              0.734
200          3108              0.798
250          2828              0.849
300          2592              0.902
350          2411              0.852
400          2039              1.110
500          2138              1.107
600          1998              1.143
700          1919              1.341
800          1883              1.195

Suggesting a sieving range for Q of 65-790M to generate 1.8e9 raw relations.

Degree 5 (escore = 1.297e-15):

Code:

n: 8095101662371927421703337019465587498085337648622133688278589711654019359923503887978141510461468343349838217540569173400647791769725685803537804186347867144149599002247585690859122186539724272741806859085719
skew: 771127364.56
type: gnfs
lss: 0
Y0: -17068243492239505219994785346910834818341
Y1: 1873940548553722757
c0: 165792391853474935561243616954647727516748946250496
c1: 2160239644350504494844955872920952825447896
c2: -21514458180493538566295548810659238
c3: -5887571126475837688637761
c4: 35919796435243602
c5: 5588280
rlim: 190000000
alim: 260000000
lpbr: 34
lpba: 34
mfbr: 67
mfba: 99
rlambda: 2.5
alambda: 3.66

Results of test sieving on the algebraic side with Q in blocks of 1000:

Code:

MQ       Norm_yield      Speed (sec/rel)
65          3142              0.943
100         2971              0.848
150         2776              1.002
200         2702              0.899
250         2616              0.864
300         2432              1.112
350         2414              0.959
400         2334              0.978
500         2153              1.032
600         2122              1.213
700         2032              1.199
800         1957              1.283
840         1911              1.165

Suggesting a sieving range for Q of 65-835M to generate 1.8e9 raw relations.

Comparing the performance of the two polynomials, if we had to choose today then the degree 6 clearly wins. But based on the respective sieving ranges

Degree 6: 65-790M = 725M

Degree 5: 65-835M = 770M

the degree 6 is only ~6% "better" than the current degree 5. As such, if we can find a degree 5 polynomial > 1.06 * 1.297e-15 = 1.378e-15 or say 1.38e-15 then we have a competitive (or better) degree 5.

All back of the envelope of course, perhaps others can provide a deeper analysis. But I think finding even a near record degree 5 (record 208 is 1.439e-15) will be the optimal path for sieving. Now we just have to find it!

Thanks for the thorough test sieving! My degree 5 search ended with no hits other than the two I posted, but I can revisit with a more permissive stage 1 norm.

VBCurtis · 2022-10-28, 02:30

The thing about targeting a deg 5 score is that the original-style Murphy E-score is only about +-10% accurate on these GNFS200+ sized jobs. So, rather than think "I need an 8% better scoring deg 5 poly to win", it's more like "I need an 8% less unlucky poly of similar score". That is, if the first deg 5 poly was unlucky at all... I would have expected a deg 6 at this size to sieve as if its score was around 20% lower, which would be a high 1.4.... so maybe the deg 5 poly was already a bit lucky in the sense that it sieves a bit better than the E-score predicts, or the deg 6 is a little unlucky in the same sense.

Is the 1.8 scoring deg 6 a big outlier? I mean, could we expect to find another one of similar score in reasonable time? Maybe we can find a luckier deg 6 of similar score, one that sieves better?

I think theory indicates 210 digits as deg 6 cutoff, but outlier finds trump "best degree" for a couple digits above and below 210. Also, CADO might just be good at deg 6 searching....

swellman · 2022-10-28, 13:49

Don’t forget we used a degree 5 on the GNFS 208 job 71111_329 last year, but that was a record escore that still stands today. We didn’t bother searching for a degree 6. I note that we ultimately used a 33/34 job on 16e_small.

Agreed that there seems to be a spectrum of escores and polynomials rather than rigid quantum levels in this area 206-212(?). That said, it would seem if we find a great degree 5 it could be the optimum sieving polynomial. If we aren’t fortunate enough to find such then we’ve still got a decent degree 6 poly.

I’m still searching for a degree 5 using CADO. Willing to search a5 upwards of 350M. At least 16e_small can factor the job.

swellman · 2022-10-30, 12:55

Quote:

Originally Posted by swellman

Also CADO just finished searching a5 of 5-25M (and multiples thereof) but found nothing worth reporting.

Moving on to a5 of 25-50M. Results expected within a week.

Search with a5 < 50M completed with nothing above 1.1e-15.

Moving on to 50 M < a5 < 100M.

wombatman · 2022-11-04, 16:18

100M < a5 < 110M also gives nothing with better than 1.1e-15. I'm including the best one below in case it spins to something much better:

Code:

n: 8095101662371927421703337019465587498085337648622133688278589711654019359923503887978141510461468343349838217540569173400647791769725685803537804186347867144149599002247585690859122186539724272741806859085719
skew: 68412445.184
c0: -6490975461005746863801015784256416300983191375520
c1: -231258586814488967345438539136760969775530
c2: 10440225468560980050813725518972721
c3: 156529928643307208197868833
c4: -1449302374271799648
c5: -2603240640
Y0: -9431566359373311653513993787769012301589
Y1: 4279013937881714834902949
# MurphyE (Bf=3.436e+10,Bg=1.718e+10,area=1.476e+17) = 9.065e-09
# f(x) = -2603240640*x^5-1449302374271799648*x^4+156529928643307208197868833*x^3+10440225468560980050813725518972721*x^2-231258586814488967345438539136760969775530*x-6490975461005746863801015784256416300983191375520
# g(x) = 4279013937881714834902949*x-9431566359373311653513993787769012301589
# skew 68412445.18, size 1.230e-20, alpha -8.246, combined = 1.090e-15 rroots = 5

swellman · 2022-11-09, 13:48

CADO got a hit:

Code:

n: 8095101662371927421703337019465587498085337648622133688278589711654019359923503887978141510461468343349838217540569173400647791769725685803537804186347867144149599002247585690859122186539724272741806859085719
skew: 100566981.63
c0: 11723235909691983027743306329098857594310171655296
c1: -707753756330993822823023676037298428698288
c2: -9044231835578216071902622120895041
c3: 156514944528553735898454733
c4: 590628419557225820
c5: -1841994000
Y0: -9745246322083856027919476915374329400726
Y1: 889878325900711221231313
# MurphyE (Bf=3.436e+10,Bg=1.718e+10,area=1.476e+17) = 1.014e-08
# f(x) = -1841994000*x^5+590628419557225820*x^4+156514944528553735898454733*x^3-9044231835578216071902622120895041*x^2-707753756330993822823023676037298428698288*x+11723235909691983027743306329098857594310171655296
# g(x) = 889878325900711221231313*x-9745246322083856027919476915374329400726
# skew 100566981.63, size 1.628e-020, alpha -9.019, combined = 1.319e-015 rroots = 5

Using the cownoise suggested skew improves things a bit:

Code:

n: 8095101662371927421703337019465587498085337648622133688278589711654019359923503887978141510461468343349838217540569173400647791769725685803537804186347867144149599002247585690859122186539724272741806859085719
skew: 134510202.90
c0: 11723235909691983027743306329098857594310171655296
c1: -707753756330993822823023676037298428698288
c2: -9044231835578216071902622120895041
c3: 156514944528553735898454733
c4: 590628419557225820
c5: -1841994000
Y0: -9745246322083856027919476915374329400726
Y1: 889878325900711221231313
# MurphyE (Bf=3.436e+10,Bg=1.718e+10,area=1.476e+17) = 1.014e-08
# f(x) = -1841994000*x^5+590628419557225820*x^4+156514944528553735898454733*x^3-9044231835578216071902622120895041*x^2-707753756330993822823023676037298428698288*x+11723235909691983027743306329098857594310171655296
# g(x) = 889878325900711221231313*x-9745246322083856027919476915374329400726
# skew 134510202.90, size 1.628e-020, alpha -9.019, combined = 1.325e-015 rroots = 5

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GIMPS wiki account request thread	ixfd64	mersennewiki	169	2018-09-21 05:43
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
Lost Prime Raider password request thread	cheesehead	Forum Feedback	6	2009-07-28 13:02
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07
Deutscher Thread (german thread)	TauCeti	NFSNET Discussion	0	2003-12-11 22:12

2022-10-25, 18:40	#2302
swellman Jun 2012 2·17·113 Posts	Just FYI, I’m still test sieving the best deg 5 and 6 polys as a sanity check. Also CADO just finished searching a5 of 5-25M (and multiples thereof) but found nothing worth reporting. Moving on to a5 of 25-50M. Results expected within a week.

2022-10-28, 02:30	#2306
VBCurtis "Curtis" Feb 2005 Riverside, CA 1010111111100₂ Posts	The thing about targeting a deg 5 score is that the original-style Murphy E-score is only about +-10% accurate on these GNFS200+ sized jobs. So, rather than think "I need an 8% better scoring deg 5 poly to win", it's more like "I need an 8% less unlucky poly of similar score". That is, if the first deg 5 poly was unlucky at all... I would have expected a deg 6 at this size to sieve as if its score was around 20% lower, which would be a high 1.4.... so maybe the deg 5 poly was already a bit lucky in the sense that it sieves a bit better than the E-score predicts, or the deg 6 is a little unlucky in the same sense. Is the 1.8 scoring deg 6 a big outlier? I mean, could we expect to find another one of similar score in reasonable time? Maybe we can find a luckier deg 6 of similar score, one that sieves better? I think theory indicates 210 digits as deg 6 cutoff, but outlier finds trump "best degree" for a couple digits above and below 210. Also, CADO might just be good at deg 6 searching....

2022-10-28, 13:49	#2307
swellman Jun 2012 7402₈ Posts	Don’t forget we used a degree 5 on the GNFS 208 job 71111_329 last year, but that was a record escore that still stands today. We didn’t bother searching for a degree 6. I note that we ultimately used a 33/34 job on 16e_small. Agreed that there seems to be a spectrum of escores and polynomials rather than rigid quantum levels in this area 206-212(?). That said, it would seem if we find a great degree 5 it could be the optimum sieving polynomial. If we aren’t fortunate enough to find such then we’ve still got a decent degree 6 poly. I’m still searching for a degree 5 using CADO. Willing to search a5 upwards of 350M. At least 16e_small can factor the job.