mersenneforum.org Factoring for a publication
 Register FAQ Search Today's Posts Mark Forums Read

2021-06-12, 06:46   #232
Max0526

"Max"
Jun 2016
Toronto

19×47 Posts
SNFS spinner works!

Quote:
 Originally Posted by Max0526 @fivemack Regarding your comments in the sheet on the highest difficulty SNFS degree 4 job ever run at the forum (8, -8) http://factordb.com/index.php?id=1100000002598203189 c229/snfs275.5, c253/snfs275.2 (t45 done on both) I am happy to say that (at least) c253 could be represented by 8 (not just 4) different SNFS polys. I got 6 explicitly so far and still working on the other 2 (next level math is involved). The two best I know are below. If anything better comes up, I'll update. The formulas are coming too. Code: (8, -8) c253 / snfs276 --> poly 1 n: 8804520161676131700982540766264320490679194033982281399896425294638109453150751678880580616975539504041811224827523553098748730672460054169092839796707517989930320213119027214444156828381573746656945529005366269066529760620006615774307975893498163091241 # a = 1106273959150699304135127106363386120968812205980268960573631929106481/126098023634219809899835084852688502789500914867461314423771553552960 Y0: -1106273959150699304135127106363386120968812205980268960573631929106481 Y1: 126098023634219809899835084852688502789500914867461314423771553552960 # poly 2*x^4 - 30*x^3 + 169*x^2 - 420*x + 196*2 c0: 392 c1: -420 c2: 169 c3: -30 c4: 2 skew: 4.97043 # E = 8.65288632e-17 ------------------------------------------ (8, -8) c253 / snfs276 --> poly 5 n: 8804520161676131700982540766264320490679194033982281399896425294638109453150751678880580616975539504041811224827523553098748730672460054169092839796707517989930320213119027214444156828381573746656945529005366269066529760620006615774307975893498163091241 a = 700645316548417658401985828694234244401797260158210592496450279693521/10786963307681811764114618362962601770038791026484251295375326612440 Y0: -700645316548417658401985828694234244401797260158210592496450279693521 Y1: 10786963307681811764114618362962601770038791026484251295375326612440 # poly x^4 - 24*x^3 + 288*x^2 - 4320*x + 32400 <-- a different poly here c0: 32400 c1: -4320 c2: 288 c3: -24 c4: 1 skew: 21.08616 # E = 9.26201191e-17 <-- higher score
I built the SNFS spinner and it works!
The two polys above easily spin up 9%, and above 1e-16.
Code:
1,0,2,-12,10,64721779846090870584687710177775610620232746158905507772251959674640,-635923536702326787817298118516458633781564513999305084724198320018881
2.80011 1.01256249e-16

2,2,1,4,8,126098023634219809899835084852688502789500914867461314423771553552960,-601881864613820064535786766952632109810808546510423702878545714894641
2.23217 1.01166588e-16

1,0,8,-96,160,32360889923045435292343855088887805310116373079452753886125979837320,-635923536702326787817298118516458633781564513999305084724198320018881
5.58749 1.00195264e-16
If anybody wants to try spinning a poly, please let me know.

@swishzzz
Is it possible to try with Python please?
1) feed in the text file with 7 comma separated values for c4,c3,c2,c1,c0,Y1,Y0 on each line, the test file is attached;
2) connect to http://myfactorcollection.cownoise.c...lculators.html, the top form Optimal Skew;
3) send records through Optimal Skew form and receive the skew and E score for each;
4) pick the line with the best E score;
5) how long would it take to process 100 records?

@bsquared
Is anything like this possible to implement with your newly gained knowledge and skills in github yafu?
Attached Files
 test.txt (10.5 KB, 14 views)

 2021-06-12, 07:17 #233 Max0526   "Max" Jun 2016 Toronto 19·47 Posts stage 11 I added more factorable lines in stage 11 and cleaned the GCDs. Many smaller numbers. If you decide to participate, please book and ECM first.
2021-06-12, 07:55   #234
Max0526

"Max"
Jun 2016
Toronto

19×47 Posts

Quote:
 Originally Posted by Max0526 Found the paper: https://hal.inria.fr/hal-01089507/fi...t-20140905.pdf I was wrong. How could I forget? The whole point of writing that paper was to introduce the L^2-norm as an alternative (and better) predictor of how good the GNFS poly is after the size and root optimization. Formula (2.2) on page 2, where d is a poly degree (d = 4 for us now), s is the skew (could be taken as a standard estimate from c0 and c4 for each poly during the spin). We can drop (1/2)log and pi/7168, and set c5=c6=0. Nine simple terms before simplification (it will simplify when s is given explicitly, and all ci~=ci*s^(i-2) are set). The lower the L^2-norm, the better the poly. Will code and report the results during the weekend.
The L^2-norm ended up being implemented like this in the degree 4 SNFS spinner
Code:
### s:=(abs(1.0*c0/c4))^(1/4); <-- SNFS skew
### s2:=s^2;
s2:=sqrt(abs(1.0*c0/c4));
L2:=log(1.0*(252*c0*c4+14*c1*c3+7*c2^2+s2*5*(2*c2*c4+c3^2)+1/s2*21*(2*c0*c2+c1^2)));

2021-06-12, 10:32   #235
charybdis

Apr 2020

5558 Posts

Quote:
 Originally Posted by Max0526 Found the paper: https://hal.inria.fr/hal-01089507/fi...t-20140905.pdf I was wrong. How could I forget? The whole point of writing that paper was to introduce the L^2-norm as an alternative (and better) predictor of how good the GNFS poly is after the size and root optimization. Formula (2.2) on page 2, where d is a poly degree (d = 4 for us now), s is the skew (could be taken as a standard estimate from c0 and c4 for each poly during the spin). We can drop (1/2)log and pi/7168, and set c5=c6=0. Nine simple terms before simplification (it will simplify when s is given explicitly, and all ci~=ci*s^(i-2) are set). The lower the L^2-norm, the better the poly. Will code and report the results during the weekend.
??? I don't see any claim that the L^2-norm is a better predictor; in fact the authors even say on page 3 that the root-adjusted L^2-norm is only a rough estimate of polynomial performance and that Murphy's E score is better! And that's the root-adjusted L^2-norm, not the L^2-norm itself, which is only intended to estimate the size of the norms, not the root properties of the polynomial.

The usefulness of the L^2-norm is that, unlike Murphy-E, it can be easily calculated (by formula 2.2), so the authors used it to design a slightly improved polynomial selection algorithm.

There is a more recent paper which does find an improved version of Murphy's E-score.

Last fiddled with by charybdis on 2021-06-12 at 10:33

2021-06-12, 13:03   #236
Max0526

"Max"
Jun 2016
Toronto

19×47 Posts

Quote:
 Originally Posted by charybdis ??? I don't see any claim that the L^2-norm is a better predictor; in fact the authors even say on page 3 that the root-adjusted L^2-norm is only a rough estimate of polynomial performance and that Murphy's E score is better! And that's the root-adjusted L^2-norm, not the L^2-norm itself, which is only intended to estimate the size of the norms, not the root properties of the polynomial. The usefulness of the L^2-norm is that, unlike Murphy-E, it can be easily calculated (by formula 2.2), so the authors used it to design a slightly improved polynomial selection algorithm. There is a more recent paper which does find an improved version of Murphy's E-score.
Thank you for the post, charybdis!
My wrong evaluation of the ideas presented in Shi Bai's paper was misleading, and I am sorry for that. You are right everywhere. And thank you for the link to the more recent publication.

 2021-06-12, 13:55 #237 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 73618 Posts Is my earlier posting for GNFS spinning of any use for SNFS polynomials? (I got sidetracked when I was trying to convert your Maple portion.) I have a Python version of my Bash script that I posted, but neither go past the CADO-NFS s/r routines.
2021-06-12, 14:24   #238
Max0526

"Max"
Jun 2016
Toronto

19×47 Posts

Quote:
 Originally Posted by EdH Is my earlier posting for GNFS spinning of any use for SNFS polynomials? (I got sidetracked when I was trying to convert your Maple portion.) I have a Python version of my Bash script that I posted, but neither go past the CADO-NFS s/r routines.
It definitely would be if we try!
Last time I tried to optimize a known SNFS poly on CADO manually (probably years ago now), it returned some ridiculous version of the poly that was obviously worse by both lognorm and the E score. I couldn't figure out why it would report it as a result.
Thank you for the idea, EdH!
There are many 4/8 SNFS poly packs for some numbers already posted in the thread. If/when you have time, please feel free to feed any of them into your existing Python/CADO spinner.
Let us know please, especially if any of them spins up.

 2021-06-12, 15:55 #239 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2·132·19 Posts Nice split C156 from line 55 splits as Code: p78 factor: 208030089699658289822530838465866133665512884513204464375029444713302449264703 p78 factor: 974982439992577307530683544126660941864526132438167923989094894696074180145839 About three wall-clock days of sieving plus six hours for the linear algebra, on 20-core Xeon E5-2673v4. Probably rushed the polynomial selection a bit, score was 2.203e-12 while I'd usually want 2.5e-12 for this size number. Stage 7 is now entirely a pleasing green.
2021-06-12, 16:17   #240
Max0526

"Max"
Jun 2016
Toronto

19·47 Posts

Quote:
 Originally Posted by fivemack C156 from line 55 splits as Code: p78 factor: 208030089699658289822530838465866133665512884513204464375029444713302449264703 p78 factor: 974982439992577307530683544126660941864526132438167923989094894696074180145839 About three wall-clock days of sieving plus six hours for the linear algebra, on 20-core Xeon E5-2673v4. Probably rushed the polynomial selection a bit, score was 2.203e-12 while I'd usually want 2.5e-12 for this size number. Stage 7 is now entirely a pleasing green.
This is what we call a nice split! c156=2*p78! Done and done!
Thank you, fivemack!
Could you please send me that c156 GNFS poly? How did you select it? msieve GPU or CADO?
Could you also take a look at https://mersenneforum.org/showpost.p...postcount=228?

EDIT:
fivemack, I hope you haven't started line 88 (5, -8) yet. If you haven't, could you please hold on for a bit, just to give me a chance to look at all available SNFS polys and their spins for that c209? It would be a perfect training ground for the definitely possible (just checked) polys 5-8 and the newly baked spinner.

Last fiddled with by Max0526 on 2021-06-12 at 17:01

2021-06-12, 18:05   #241
EdH

"Ed Hall"
Dec 2009

32·52·17 Posts

Quote:
 Originally Posted by Max0526 It definitely would be if we try! Last time I tried to optimize a known SNFS poly on CADO manually (probably years ago now), it returned some ridiculous version of the poly that was obviously worse by both lognorm and the E score. I couldn't figure out why it would report it as a result. Maybe a newer CADO is better in that regard. Thank you for the idea, EdH! There are many 4/8 SNFS poly packs for some numbers already posted in the thread. If/when you have time, please feel free to feed any of them into your existing Python/CADO spinner. Let us know please, especially if any of them spins up.
I will have to play in that arena later today.

For now, all the smaller composites are factored and the c312 is nearing t50.

 2021-06-12, 19:05 #242 firejuggler     Apr 2010 Over the rainbow 260310 Posts (11,-1) c160= 783834531741188343291076442119519 * P127 c171= 10909091155385421570068617489 * P143 (10,-5) c192 =415912252448292884427458837* P165 Last fiddled with by firejuggler on 2021-06-12 at 19:33

 Similar Threads Thread Thread Starter Forum Replies Last Post baih Miscellaneous Math 9 2020-09-21 07:11 xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 06:32.

Wed Jul 28 06:32:50 UTC 2021 up 5 days, 1:01, 0 users, load averages: 1.86, 1.92, 1.86