Register FAQ Search Today's Posts Mark Forums Read

2022-04-09, 15:52   #2179
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2×2,689 Posts

Quote:
 Originally Posted by charybdis 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.

2022-04-09, 15:57   #2180
charybdis

Apr 2020

32·89 Posts

Quote:
 Originally Posted by swellman 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

2022-04-09, 15:59   #2181
charybdis

Apr 2020

32·89 Posts

Quote:
 Originally Posted by VBCurtis 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

 2022-04-09, 19:25 #2182 unconnected     May 2009 Russia, Moscow 279410 Posts 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
 2022-04-11, 04:57 #2183 Gimarel   Apr 2010 22·3·19 Posts 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
 2022-04-11, 08:14 #2184 unconnected     May 2009 Russia, Moscow 1010111010102 Posts Thank you, very good poly!
2022-04-11, 19:40   #2185
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

23·7·107 Posts

Quote:
 Originally Posted by charybdis 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

2022-04-11, 20:57   #2186
charybdis

Apr 2020

11001000012 Posts

Quote:
 Originally Posted by henryzz 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.

2022-04-12, 10:03   #2187
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

23·7·107 Posts

Quote:
 Originally Posted by charybdis 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.

2022-04-12, 11:57   #2188
charybdis

Apr 2020

32·89 Posts

Quote:
 Originally Posted by henryzz 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.

2022-04-12, 13:06   #2189
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

23×7×107 Posts

Quote:
 Originally Posted by charybdis 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).

 Similar Threads Thread Thread Starter Forum Replies Last Post ixfd64 mersennewiki 169 2018-09-21 05:43 carpetpool Miscellaneous Math 14 2017-02-18 19:46 cheesehead Forum Feedback 6 2009-07-28 13:02 R.D. Silverman NFSNET Discussion 13 2005-09-16 20:07 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