mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-12, 06:46   #232
Max0526
 
"Max"
Jun 2016
Toronto

19×47 Posts
Default SNFS spinner works!

Quote:
Originally Posted by Max0526 View Post
@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
File Type: txt test.txt (10.5 KB, 14 views)
Max0526 is offline   Reply With Quote
Old 2021-06-12, 07:17   #233
Max0526
 
"Max"
Jun 2016
Toronto

19·47 Posts
Default 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.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 07:55   #234
Max0526
 
"Max"
Jun 2016
Toronto

19×47 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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)));
Max0526 is offline   Reply With Quote
Old 2021-06-12, 10:32   #235
charybdis
 
charybdis's Avatar
 
Apr 2020

5558 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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
charybdis is offline   Reply With Quote
Old 2021-06-12, 13:03   #236
Max0526
 
"Max"
Jun 2016
Toronto

19×47 Posts
Default

Quote:
Originally Posted by charybdis View Post
??? 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.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 13:55   #237
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

73618 Posts
Default

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.
EdH is offline   Reply With Quote
Old 2021-06-12, 14:24   #238
Max0526
 
"Max"
Jun 2016
Toronto

19×47 Posts
Default

Quote:
Originally Posted by EdH View Post
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.
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.
Max0526 is offline   Reply With Quote
Old 2021-06-12, 15:55   #239
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·132·19 Posts
Default 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.
fivemack is offline   Reply With Quote
Old 2021-06-12, 16:17   #240
Max0526
 
"Max"
Jun 2016
Toronto

19·47 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
Max0526 is offline   Reply With Quote
Old 2021-06-12, 18:05   #241
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

32·52·17 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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.
EdH is offline   Reply With Quote
Old 2021-06-12, 19:05   #242
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

260310 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think) baih Miscellaneous Math 9 2020-09-21 07:11
OpenCL GPU P-1 Factoring and ECM Factoring 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.