mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2022-04-09, 15:52   #2179
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×2,689 Posts
Default

Quote:
Originally Posted by charybdis View Post
I'm assuming that GNFS will outperform the difficulty-271 octics for 2,2694L/M, though it might be a good idea for someone to make sure by test-sieving against another 204-digit GNFS (3,748+ springs to mind).
I'm game for this comparison, and I think I have test data in my archives from 3,748+.
Can you post the correct poly? I'm too lazy to solve it myself.
VBCurtis is offline   Reply With Quote
Old 2022-04-09, 15:57   #2180
charybdis
 
charybdis's Avatar
 
Apr 2020

32·89 Posts
Default

Quote:
Originally Posted by swellman View Post
The CNs on Yoyo are likely another year chewing through the rest of the 1987 era base-2 Cunninghams. But I can do about ~1000 curves/day at the B1=850M on my local big box for a c20X. Say 3000 curves on each composite? More? I can start the effort tomorrow once the current work finishes. Help from others would be most welcome.
I don't know how much work Sam did on these, but the smallest factor that's turned up since the extensions were added was a p61 factor of a c321; doubtless these c20x had more ECM than c300+. So these might already have enough ECM done, but we don't know that for sure. I don't think there's a right amount to run, just do whatever's not too inconvenient for you. If you're Ryan, that probably means running a full t65 on each number, and I'm not going to complain about that
charybdis is offline   Reply With Quote
Old 2022-04-09, 15:59   #2181
charybdis
 
charybdis's Avatar
 
Apr 2020

32·89 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I'm game for this comparison, and I think I have test data in my archives from 3,748+.
Can you post the correct poly? I'm too lazy to solve it myself.
Octics are 4x^8 - 4x^6 + 2x^4 - 2x^2 + 1 and 4x^8 + 4x^6 + 2x^4 + 2x^2 + 1 for L/M respectively with rational poly x-2^112.

Last fiddled with by charybdis on 2022-04-09 at 16:05
charybdis is offline   Reply With Quote
Old 2022-04-09, 19:25   #2182
unconnected
 
unconnected's Avatar
 
May 2009
Russia, Moscow

279410 Posts
Default

Hi guys, please help with the poly for this number, it's coming from aliquot sequence 785232:i11564 and has been extensively pretesting with ECM.

Code:
352877742600973079835183371695411433700853057958818602576415399270295381830689655616389775032026933352863953179853062837564251029973458211102638237510254736154595759284806157937293481849369639
I've got a bunch of polys with e-score >1.1, but no better than 1.189, here it is:
Code:
# norm 6.924663e-19 alpha -8.346006 e 1.189e-14 rroots 5
skew: 674203189.34
c0: -12156751162560026744092104233803184753091159062565
c1: 72189372820466863675203441698166602254409
c2: 414382659223223227257288010313925
c3: -1294095825076902904381917
c4: -1100937170066360
c5: 244524
Y0: -17055346886074176922358825954465247094
Y1: 81657367824113953559
unconnected is offline   Reply With Quote
Old 2022-04-11, 04:57   #2183
Gimarel
 
Apr 2010

22·3·19 Posts
Default 785232:i11564

Here you go:
Code:
# norm 1.240318e-18 alpha -7.532287 e 1.760e-14 rroots 5
skew: 11166512.66
c0: 44549465986335687101170388652004286183559000
c1: 1859383291756161743996868361630553379
c2: -2480181312007428947856509788106
c3: -32775893275167804691699
c4: 27296412874693386
c5: 158760000
Y0: -5365159453367507252900879330459589554
Y1: 216465220778528055553
Gimarel is offline   Reply With Quote
Old 2022-04-11, 08:14   #2184
unconnected
 
unconnected's Avatar
 
May 2009
Russia, Moscow

1010111010102 Posts
Default

Thank you, very good poly!
unconnected is offline   Reply With Quote
Old 2022-04-11, 19:40   #2185
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23·7·107 Posts
Default

Quote:
Originally Posted by charybdis View Post
Octics are 4x^8 - 4x^6 + 2x^4 - 2x^2 + 1 and 4x^8 + 4x^6 + 2x^4 + 2x^2 + 1 for L/M respectively with rational poly x-2^112.

Are there any slightly larger candidates with the same algebraic polynomials that would be best as snfs? I wonder whether there is any sense in attempting a nfs factory approach to factoring them.


I have been wondering for a while if it would be worth creating some forum datasets for common snfs algebraic polynomials (e.g. x^6+x^5+x^4+x^3+x^2+x+1). Octics may be good candidates as the rational side would be easier to factor.

Last fiddled with by henryzz on 2022-04-11 at 19:42
henryzz is offline   Reply With Quote
Old 2022-04-11, 20:57   #2186
charybdis
 
charybdis's Avatar
 
Apr 2020

11001000012 Posts
Default

Quote:
Originally Posted by henryzz View Post
Are there any slightly larger candidates with the same algebraic polynomials that would be best as snfs? I wonder whether there is any sense in attempting a nfs factory approach to factoring them.
Here are some more, including a couple of smaller ones:

Code:
221	2	2634	L	264.2	0.83	/3
254	2	2658	M	266.6	0.95	/3
204	2	2694	L	270.2	0.75	/3
204	2	2694	M	270.2	0.75	/3
241	2	2706	M	271.5	0.88	/3
241	2	2742	L	275.1	0.87	/3
261	2	2766	M	277.5	0.94	/3
224	2	2778	M	278.7	0.8	/3
276	2	2778	L	278.7	0.99	/3
281	2	2802	L	281.1	0.99	/3
The polynomials for some of these would more normally be written as x^8 - 2x^6 + 2x^4 - 4x^2 + 4 for L and the equivalent for M, but we can reverse the order of the coefficients of the algebraic and rational polys.

Two obstacles that immediately stand out: Greg would need to get the batch smoothness step set up on NFS@Home, and the disk space requirements would be rather large.
charybdis is offline   Reply With Quote
Old 2022-04-12, 10:03   #2187
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23·7·107 Posts
Default

Quote:
Originally Posted by charybdis View Post
Here are some more, including a couple of smaller ones:

Code:
221    2    2634    L    264.2    0.83    /3
254    2    2658    M    266.6    0.95    /3
204    2    2694    L    270.2    0.75    /3
204    2    2694    M    270.2    0.75    /3
241    2    2706    M    271.5    0.88    /3
241    2    2742    L    275.1    0.87    /3
261    2    2766    M    277.5    0.94    /3
224    2    2778    M    278.7    0.8    /3
276    2    2778    L    278.7    0.99    /3
281    2    2802    L    281.1    0.99    /3
The polynomials for some of these would more normally be written as x^8 - 2x^6 + 2x^4 - 4x^2 + 4 for L and the equivalent for M, but we can reverse the order of the coefficients of the algebraic and rational polys.

Two obstacles that immediately stand out: Greg would need to get the batch smoothness step set up on NFS@Home, and the disk space requirements would be rather large.
I was more envisoning using the cado siever and running it as a forum project as I believe it would be more robust to the odd parameterisations that this would generate. For example putting 4x^8 + 4x^6 + 2x^4 + 2x^2 + 1 and x-2^3, n=68165761 through lasieve produces some SCHED_PATHOLOGY errors for me.

The most critical thing for disk space is the proportion of relations smooth on the algebraic side that are smooth on the rational side. An octic means the rational side isn't actually that big which might make this possible. Will attempt to get some numbers when I have a chance.


Maybe some form of proof of concept polynomial where candidate factorisations are smaller might be better than this one. The degree halved polynomials for x^17-1 or x^19-1 might be good candidates as the OPN project has lots of candidates and alternative polynomials aren't amazing. I am unsure what the best size ratio between the common/unique polys is. I suspect that very difficult common polynomials may be the best candidates.
henryzz is offline   Reply With Quote
Old 2022-04-12, 11:57   #2188
charybdis
 
charybdis's Avatar
 
Apr 2020

32·89 Posts
Default

Quote:
Originally Posted by henryzz View Post
I was more envisoning using the cado siever and running it as a forum project as I believe it would be more robust to the odd parameterisations that this would generate.
These numbers are probably a bit too big for a forum project. We're still talking about several times the effort that a single difficulty-27x octic would take. For a sense of scale, a cursory glance at the Q ranges for the two numbers currently sieving on 16e-small suggests that octic-263 (2,2622L, so the same polynomial as the above numbers) is more difficult than GNFS-203. This also ends any doubts I had about 2,2694L/M being better as GNFS.
If there are some smaller OPN composites with the x^17-1 reciprocal octic then they may be more reasonable candidates for a forum effort.

Quote:
The most critical thing for disk space is the proportion of relations smooth on the algebraic side that are smooth on the rational side. An octic means the rational side isn't actually that big which might make this possible. Will attempt to get some numbers when I have a chance.
Does CADO allow for checking smooth algebraic norms against multiple rational polynomials at once as they are generated, as Kleinjung's code did for the Mersennes? It has batch smoothness code but I didn't think it could be used for multiple numbers at the same time.
charybdis is offline   Reply With Quote
Old 2022-04-12, 13:06   #2189
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23×7×107 Posts
Default

Quote:
Originally Posted by charybdis View Post
Does CADO allow for checking smooth algebraic norms against multiple rational polynomials at once as they are generated, as Kleinjung's code did for the Mersennes? It has batch smoothness code but I didn't think it could be used for multiple numbers at the same time.
No. This would be a nice way of doing it although it requires knowing the set of numbers to factorise prior to starting.


The method currently available to the forum involves using the normal sieve routines with a polynomial on one side that is trivially smooth for every a/b pair and then running the code from https://mersenneforum.org/showthread.php?t=24729 on the results. As far as I am aware Kleinjung's factory code isn't available to the forum.

Your numbers suggest to me that an octic polynomial may be hard enough that many(10s if not 100s) factorisations need to be enabled in order to be faster. This may not completely exclude the x^17-1 reciprocal octic. The sextic for x^7-1 would also be a good candidate(for lots of smaller snfs at least).
henryzz is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 18:48.


Sat Aug 13 18:48:45 UTC 2022 up 37 days, 13:36, 2 users, load averages: 1.08, 1.13, 1.09

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.

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