mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2022-09-10, 04:59   #1
charybdis
 
charybdis's Avatar
 
Apr 2020

53·7 Posts
Default 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.
charybdis is offline   Reply With Quote
Old 2022-09-10, 21:57   #2
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

47468 Posts
Default

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
frmky is offline   Reply With Quote
Old 2022-09-11, 02:03   #3
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·2,557 Posts
Default

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
EdH is offline   Reply With Quote
Old 2022-09-11, 10:21   #4
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

19·151 Posts
Default

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 )
firejuggler is online now   Reply With Quote
Old 2022-09-12, 05:03   #5
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2×7×181 Posts
Default

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
frmky is offline   Reply With Quote
Old 2022-09-12, 05:49   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23·5·139 Posts
Default

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.

Last fiddled with by VBCurtis on 2022-09-13 at 23:55
VBCurtis is offline   Reply With Quote
Old 2022-09-12, 05:51   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

97·103 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2022-09-12, 07:09   #8
charybdis
 
charybdis's Avatar
 
Apr 2020

53·7 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.

Last fiddled with by charybdis on 2022-09-12 at 07:10
charybdis is offline   Reply With Quote
Old 2022-09-12, 12:20   #9
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

19×151 Posts
Default

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 is online now   Reply With Quote
Old 2022-09-13, 22:34   #10
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

19·151 Posts
Default

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
firejuggler is online now   Reply With Quote
Old 2022-09-13, 23:54   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10101101110002 Posts
Default

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
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 10:56.


Thu Dec 8 10:56:12 UTC 2022 up 112 days, 8:24, 0 users, load averages: 1.13, 0.93, 0.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔