Polynomial selection for 2,1109+ c225

charybdis · 2022-09-10, 04:59

2,2246M is done, meaning that 2,1109+ c225 is now the only clear GNFS target left among the remaining numbers from the 1987 edition of the Cunningham book. Let's find a good polynomial for NFS@Home to sieve with.

The composite is

Code:

126451876805119252959661548967232013601866431183534308908427174011662073024932261126233275630388431500884665768427172907593022873289431612806891303891687570778305960728323476541491713906981621716831593952842244282430058291761

To the best of my knowledge, no number between 222 and 229 digits has ever been factored with GNFS, so there are no nearby record scores to compare with, but extrapolating from other degree 6 scores suggests we should aim for a score of at least 2e-16.

For CADO users, something like P=15M, incr=420, nq=46656, sopteffort=10, ropteffort=100 would be a good start parameter-wise (and don't forget degree=6). Those with good GPUs may wish to try msieve-gpu stage 1 followed by CADO sopt, which is a technique that has produced some exceptional polynomials in the past; if you would like to try this, ensure that you have either the latest CADO or a version from before 11 March this year, otherwise you will encounter this bug.

There's no rush, don't worry if you need to wait for cooler weather. I intend to start searching with CADO in a week or so.

frmky · 2022-09-10, 21:57

Just to get the party started, here are a couple of early hits.

Code:

R0: -890858233525730603070019268730360731
R1: 10637678344873644797
A0: 299836229189041894895839186985662895951560076832
A1: -237194224808389178293161225128621163060026
A2: -46081070789360664784376386970027831
A3: 51529985200329980370627087588
A4: -18026757896690121716396
A5: -2852764153396262
A6: 252972720
skew 4096052.87, size 1.995e-16, alpha -8.045, combined = 1.486e-16 rroots = 4

R0: -1543011722806615565935575378314030175
R1: 842031878738877989
A0: 6350450293847067402197405075596797572174622865528576
A1: -3139610947120576605897442761369137813674879640
A2: -843606577109644671310292753045506226718
A3: 6622510117319190858833637755861
A4: 734856321473040043162292
A5: -2244560413626756
A6: 9369360
skew 41379413.60, size 1.738e-16, alpha -12.221, combined = 1.288e-16 rroots = 4

EdH · 2022-09-11, 02:03

Here's a spin for the previous two:

Code:

Y0: -890858233519512848164405588725579840
Y1: 10637678344873644797
c0: 20679080292568510209376599202651938080731751
c1: -16905369045270557188781384384089427958
c2: -2071016516892570126261873688125653
c3: -647249845227500980682508056
c4: 25067605669229211438126
c5: 1965584270847302
c6: -252972720
skew: 313566.209
# lognorm 60.98, E 53.93, alpha -7.05 (proj -2.10), 6 real roots
# MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.983e-16

Best poly cownoise values: 589597.92262      2.01167412e-16

firejuggler · 2022-09-11, 10:21

I'll try casually. Msieve doesn't seem good. ( can't get 1.53 gpu to run due to ptx incompatibility. GTX 1660 TI and cuda 7.5 )

frmky · 2022-09-12, 05:03

After a couple A40-months, I found two more higher scoring polys from msieve.

Code:

# norm 2.363604e-16 alpha -9.855342 e 1.471e-16 rroots 4
skew: 4188324.95
c0: 4890952461071308375125802645743946534044245681184
c1: 1464426985010460823704889708794214954589992
c2: -597300025874739851693961141580723240
c3: -434858756700091304313330515360
c4: -60480910188020917238229
c5: 36012170114448258
c6: 2327925600
Y0: -615402652607881386341306354933736125
Y1: 1564161336280197503

# norm 2.516901e-16 alpha -11.340645 e 1.540e-16 rroots 4
skew: 5962737.46
c0: 36610384221328653794084765331280784334500166002560
c1: -6597385732367497117864187808228061224463212
c2: -3597302716498354719019930592716700096
c3: -998777198088521283283165788933
c4: -364143521396930855524484
c5: 52296633709802010
c6: 3398194800
Y0: -577802612761468877350169963836667229
Y1: 42417278640103023257

But using Ed's script, they didn't improve quite as much as the early hit above.

Code:

Y0: -615402652608941593664973108163639561
Y1: 1564161336280197503
c0: 99837092116108261904550451646795621673004800
c1: -2024046815793900142308556853273336977440
c2: -15463527646675689570225765198286064
c3: 119928244381367488132162484048
c4: 166485563730524246399709
c5: -26544794673725058
c6: -2327925600
skew: 467990.840
# lognorm 63.90, E 54.90, alpha -9.00 (proj -2.97), 6 real roots
# MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.990e-16

Best poly cownoise values: 771030.94076      1.99451279e-16

VBCurtis · 2022-09-12, 05:49

My first run with CADO:

Code:

c0: -2310835730251156327778236511197625826302780208
c1: 442704803492886905636371260028570831748
c2: 32698967345475004746748591472162564
c3: 4077124657453197102154489355
c4: -35221438603837936231384
c5: -21786327094255250
c6: 5319514200
Y0: -859967642928493740637122025458452125
Y1: 188619699713867324748872261
# MurphyE (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 2.033e-09

Cownoise stats: skew 1025513.35579 score 1.62798458e-16

This was admin 3e8, admax 35e7, incr 60060. I'll continue searching up way high to stay out of the way of the regular searchers.

Batalov · 2022-09-12, 05:51

Let's not forget that we also have a free polynomial with

Code:

R0: -49039857307708443467467104868809893875799651909875269632
R1: 1
A0: 2
A1: 0
A2: 0
A3: 0
A4: 0
A5: 0
A6: 1
skew 1.12, size 2.613e-16, alpha 1.888, combined = 1.760e-16 rroots = 0

We need to beat that significantly.

charybdis · 2022-09-12, 07:09

Quote:

Originally Posted by Batalov

Let's not forget that we also have a free polynomial with

Code:

R0: -49039857307708443467467104868809893875799651909875269632
R1: 1
A0: 2
A1: 0
A2: 0
A3: 0
A4: 0
A5: 0
A6: 1
skew 1.12, size 2.613e-16, alpha 1.888, combined = 1.760e-16 rroots = 0

We need to beat that significantly.

I expected that it wouldn't be too hard to beat that e-score, and I was right. What I hadn't counted on was the SNFS poly overperforming its e-score by over 40%(!) compared to the two top-scoring GNFS polys. Maybe SNFS is faster after all; we probably need a GNFS poly scoring ~2.5e-16 to compete with it.

I think we've reached a point where the parameters used to generate the msieve/cownoise e-scores are so far from what will actually be used during sieving that the scores only bear a vague resemblance to sieving speed. Plugging some more realistic values into CADO's polyselect3 (-Bf 34359738368.0 -Bg 34359738368.0 -area 2147483648000000000.0) gives the SNFS poly a score almost twice as high as the GNFS polys.

firejuggler · 2022-09-12, 12:20

I went very granular and got

Code:

skew: 685194.469
c0: 13546832639784934995088934891473021436914757595
c1: -243239753933587411699854385797238306940956
c2: 18952157534337102628447505483356966
c3: 653316556750163296492944500212
c4: -2574375769149943375426741
c5: -195684033327748056
c6: 81908173620
Y0: -1041043757015113400466899425916289274
Y1: 2830716526317416698316524373
# MurphyE (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 1.756e-09

firejuggler · 2022-09-13, 22:34

second run

Code:

n: 126451876805119252959661548967232013601866431183534308908427174011662073024932261126233275630388431500884665768427172907593022873289431612806891303891687570778305960728323476541491713906981621716831593952842244282430058291761
skew: 697478.803
c0: 26487282380138522677004084831483303431066050150
c1: -24753607872970529743670167294611358561023
c2: -432036146231461013035116862579046871
c3: 257470942642010751446884931927
c4: 1341532846594386074140153
c5: -223518134738310192
c6: -233429676480
Y0: -1033071967615446320814534193404610478
Y1: 21370116632131503382859723
# MurphyE (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 1.776e-09

VBCurtis · 2022-09-13, 23:54

firejuggler and I are using the same CADO sieve/Murphy-score params (taken from the c230.params file) for score evaluation.
Here's my second-run best:

Code:

skew: 349620.103
c0: -35261944489889081487427593499134306423434235
c1: 1147840847825503997219617398569984615228
c2: -6032823929352871049090059774838128
c3: -8280172716447232050639984506
c4: 93116889162997251267859
c5: 46149285013390062
c6: 9179450280
Y0: -813240839151117999538946984841129674
Y1: 4775593547116029134541157
# MurphyE (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 2.210e-09

I've edited the post from my first poly to show this CADO score also. This one is 9% better, from admin 35e7 admax 45e7 incr 60060.

It seems to me that scoring 2e-16 on cownoise is fairly easy. A 2.2 should be reachable without difficulty, but getting to 2.5 to beat the SNFS poly will take some luck or lots of work.
We need the combo of a poly scoring 2.0+ before spin plus a lucky extra-20% spin. In CADO-score terms, a 2.4 before spin with a lucky spin is likely necessary to beat the SNFS poly; also, we can't be sure that "spinning" to optimize regular E-score actually sieves better than these CADO polys that score best on a sieve region we're actually going to use. That is, "spin" may be a bit of an illusion on deg 6 sized jobs.
I'm willing to keep searching, but I'll pause until we decide whether to just use the SNFS poly for the job.

For those of you searching with CADO, I suggest you use the params.c230 file as your template, and edit the poly select parameters to suit your run. Doing so will produce CADO Murphy scores consistent with those on this thread, reducing our labor to check cownoise and improving the predictive power of the score.

2022-09-10, 04:59	#1
charybdis Apr 2020 5²×37 Posts	Polynomial selection for 2,1109+ c225 2,2246M is done, meaning that 2,1109+ c225 is now the only clear GNFS target left among the remaining numbers from the 1987 edition of the Cunningham book. Let's find a good polynomial for NFS@Home to sieve with. The composite is Code: 126451876805119252959661548967232013601866431183534308908427174011662073024932261126233275630388431500884665768427172907593022873289431612806891303891687570778305960728323476541491713906981621716831593952842244282430058291761 To the best of my knowledge, no number between 222 and 229 digits has ever been factored with GNFS, so there are no nearby record scores to compare with, but extrapolating from other degree 6 scores suggests we should aim for a score of at least 2e-16. For CADO users, something like P=15M, incr=420, nq=46656, sopteffort=10, ropteffort=100 would be a good start parameter-wise (and don't forget degree=6). Those with good GPUs may wish to try msieve-gpu stage 1 followed by CADO sopt, which is a technique that has produced some exceptional polynomials in the past; if you would like to try this, ensure that you have either the latest CADO or a version from before 11 March this year, otherwise you will encounter this bug. There's no rush, don't worry if you need to wait for cooler weather. I intend to start searching with CADO in a week or so.

2022-09-12, 05:51	#7
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10057₁₀ Posts	Let's not forget that we also have a free polynomial with Code: R0: -49039857307708443467467104868809893875799651909875269632 R1: 1 A0: 2 A1: 0 A2: 0 A3: 0 A4: 0 A5: 0 A6: 1 skew 1.12, size 2.613e-16, alpha 1.888, combined = 1.760e-16 rroots = 0 We need to beat that significantly.

2022-09-13, 23:54	#11
VBCurtis "Curtis" Feb 2005 Riverside, CA 2²·1,409 Posts	firejuggler and I are using the same CADO sieve/Murphy-score params (taken from the c230.params file) for score evaluation. Here's my second-run best: Code: skew: 349620.103 c0: -35261944489889081487427593499134306423434235 c1: 1147840847825503997219617398569984615228 c2: -6032823929352871049090059774838128 c3: -8280172716447232050639984506 c4: 93116889162997251267859 c5: 46149285013390062 c6: 9179450280 Y0: -813240839151117999538946984841129674 Y1: 4775593547116029134541157 # MurphyE (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 2.210e-09 I've edited the post from my first poly to show this CADO score also. This one is 9% better, from admin 35e7 admax 45e7 incr 60060. It seems to me that scoring 2e-16 on cownoise is fairly easy. A 2.2 should be reachable without difficulty, but getting to 2.5 to beat the SNFS poly will take some luck or lots of work. We need the combo of a poly scoring 2.0+ before spin plus a lucky extra-20% spin. In CADO-score terms, a 2.4 before spin with a lucky spin is likely necessary to beat the SNFS poly; also, we can't be sure that "spinning" to optimize regular E-score actually sieves better than these CADO polys that score best on a sieve region we're actually going to use. That is, "spin" may be a bit of an illusion on deg 6 sized jobs. I'm willing to keep searching, but I'll pause until we decide whether to just use the SNFS poly for the job. For those of you searching with CADO, I suggest you use the params.c230 file as your template, and edit the poly select parameters to suit your run. Doing so will produce CADO Murphy scores consistent with those on this thread, reducing our labor to check cownoise and improving the predictive power of the score. Last fiddled with by VBCurtis on 2022-09-14 at 00:06

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial selection	Max0526	NFS@Home	9	2017-05-20 08:57
Updated polynomial selection	jasonp	Msieve	65	2011-05-01 19:06
GNFS polynomial selection	Unregistered	Information & Answers	3	2011-04-16 14:24
2^877-1 polynomial selection	fivemack	Factoring	47	2009-06-16 00:24
Polynomial selection	CRGreathouse	Factoring	2	2009-05-25 07:55

2022-09-11, 10:21	#4
firejuggler "Vincent" Apr 2010 Over the rainbow 2²×7×103 Posts	I'll try casually. Msieve doesn't seem good. ( can't get 1.53 gpu to run due to ptx incompatibility. GTX 1660 TI and cuda 7.5 )