Polynomial Request Thread

[VBCurtis]

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.

[charybdis]

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

[charybdis]

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.

[unconnected]

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.

352877742600973079835183371695411433700853057958818602576415399270295381830689655616389775032026933352863953179853062837564251029973458211102638237510254736154595759284806157937293481849369639

I've got a bunch of polys with e-score >1.1, but no better than 1.189, here it is:

# 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

[Gimarel]

Here you go:

# 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

[unconnected]

Thank you, very good poly!

[henryzz]

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.

[charybdis]

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:

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.

[henryzz]

Originally Posted by charybdis

Here are some more, including a couple of smaller ones:

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.

[charybdis]

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.

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.

[henryzz]

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).