20161227, 04:38  #1 
Oct 2007
Manchester, UK
2·3·227 Posts 
Choice of SNFS polynomial degree
Lately I've been doing some SNFS factoring and I'm curious as to how to determine the best degree for the polynomial.
For instance, I'm currently working on 34179328063^171, and derived 4 different polynomials, with different degrees and the following SNFS difficulty levels: degree 4, difficulty 180 (but with a somewhat large c4 coefficient) degree 5, difficulty 211 degree 6, difficulty 190 degree 8, difficulty 169 I tried test sieving them all, and found that my degree 8 polynomial performed the best, followed by degree 6, then 4, and trailing a long way behind, degree 5. Now of course, the SNFS difficulty is clearly having a large effect on sieving, so I chose the degree 8 poly thinking "how much can poly degree REALLY matter?" However, after a while, sieve speed slowed down drastically, so I switched to the degree 6 poly and have been progressing with that. This has also slowed down, but not anywhere near as much. So I am still left with uncertainty of how to best choose a polynomial. Test sieving didn't work for me, since apparently the speed can change. I have heard people mention the "norm" of a polynomial, but I don't know how to calculate it or what it means. I've also read that the alpha value can be used (I think mprime outputs this?) but that SNFS polynomials usually have bad alpha values anyway. Is there some clear metric by which I can choose and/or compare polynomials? Are degree 8 polynomials inherently evil? What size range of numbers are polynomials optimal for (and what is the penalty for straying outside of this range)? 
20161227, 07:04  #2 
"Curtis"
Feb 2005
Riverside, CA
1001110001100_{2} Posts 
Testsieving is the way to answer these questions but you have to test qvalues across the entire expected range that you'll need to run. Sometimes the faster poly also has lower yield, and so has to test quite a few more q into higher ranges where it's not faster anymore.
I don't know what the penalty is for nonoptimal degree (and said penalty definitely varies as one gets closer or further from optimal range), but the transitions from one "best" degree to another are very close to where they are for GNFS polys. That is, around 210 difficulty one would choose deg6 over deg5 given samesized coefficients on the polys. Or, anywhere between 200 and 220 the smaller poly coefficients may help more than the "wrong" degree hurts. This all assumes both polys are solving the same difficulty. When they're not, like in your problem, testsieving is the way forward. 
20161227, 07:46  #3 
Jun 2003
12037_{8} Posts 
Are you sieving the deg6 on the algebraic side? That _should_ be better than sieving on the rational side.

20161227, 07:49  #4 
Jun 2003
3·17·101 Posts 

20161227, 11:44  #5  
Oct 2007
Manchester, UK
2·3·227 Posts 
Quote:
Quote:
Quote:
This is why I initially chose the degree 8 polynomial, it has such small coefficients. 

20161227, 12:00  #6  
Jun 2003
141F_{16} Posts 
You should figure out which is it, and if necessary, force the script to choose the "right" side to sieve.
You seem to be under the impression that the leading coefficient is somehow "special"? Your choice of deg5 poly has a larger a0 coefficient _and_ a larger rational coefficient, so it would be _much_ worse than what I proposed. You should try it out and see. Quote:


20161227, 13:59  #7 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011100100010_{2} Posts 
It would probably help to mention the numbers that need to be smooth:
Algebraic degree 4: Poly: \(a_4x^4+a_3x^3+a_2x^2+a_1x^1+a_0\) Number which needs to be smooth: \(a_4a^4+a_3a^3b+a_2a^2b^2+a_1ab^3+a_0b^4\) Rational: Poly: \(b_1*x+b_0\) Number which needs to be smooth: \(b_1a+b_0b\) This suggests that it doesn't matter whether it is \(a_4\) or \(a_0\) that is small. I suspect that the convention of having \(a_4\) being small with each coefficient afterwards increasing is due to originally requiring \(a_4\) to be 1. This is followed much more in gnfs. If the size of coefficients is: \(a_4, a_3, a_2, a_1, a_0\) from smallest to largest, then numbers are more likely to be smooth with smaller b than a. If the size of coefficients is: \(a_0, a_1, a_2, a_3, a_4\) from smallest to largest, then numbers are more likely to be smooth with smaller a than b. Anyone more knowledgeable got any further comments on this? I assume that it doesn't change much in polynomial selection reversing the size of coefficients(it would seem harder to me if anything) With increased degree the algebraic polynomial increases more as a and b grow. The trade off is the smaller coefficients in the rational polynomial. It is best to sieve on the larger size as you get the special q as a factor for free. It seems to me that larger coefficients matter less for larger degree polynomials. 
20161227, 16:45  #8 
"Curtis"
Feb 2005
Riverside, CA
2^{2}·3^{2}·139 Posts 
I've toyed with deg 6 vs deg 7 with SNFS, and the transition appears to be up near 1100 bits (320+ digits). 7 to 8 is much much higher than I've ever contemplated, mid 400s I think. There's a theoretical formula for optimal degree choice, but the formula appears to understate reality by a few digits (ex: deg 5 is competitive with deg 6 for GNFS 210215, which is above the theoretical cutoff; this may be due to more difficult poly select for deg 6 GNFS, though). For GNFS:
deg 4 under 115 digits deg 5 115215ish deg 6 215320ish deg 7 >320 SNFS ranges should be similar, ceteris paribus. 
20161228, 21:31  #9 
Jun 2012
3,203 Posts 
One thing to consider if you start playing with deg 7 or 8 polynomials is the difficulties you could face in the nc3 phase of the factorization. See this post for some advice on this issue. Ryan Propper, who has some breathtaking resources available to him, reported incredibly long times (1418 hours) in processing each relation in the sqrt phase of a septic. Can't imagine a degree 8!

20161229, 00:28  #10  
Oct 2007
Manchester, UK
2·3·227 Posts 
Quote:
Thankyou, I'll bear these ranges in mind for future poly selection. Last fiddled with by lavalamp on 20161229 at 00:29 

20180210, 07:27  #11 
Oct 2007
Manchester, UK
2·3·227 Posts 
I'm curious if anyone knows the optimal ranges for higher degree polynomials, even though those numbers are clearly out of the range of current hardware.
In particular I was thinking about the number 10^999+13 which I spent a good while running ECM on. It has very good polynomials for degree 8, 9, 10 and 11, but hypothetically what would be optimal for this monster? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Discriminant is n^k for an n1 degree polynomial  carpetpool  Miscellaneous Math  14  20170218 19:46 
SNFS Polynomial for 919^871  wblipp  Factoring  6  20110823 04:59 
On the skew choice for SNFS  Batalov  Factoring  1  20091117 21:18 
GNFS polynomial degree  joral  Factoring  6  20080926 22:15 
SNFS Polynomial  R.D. Silverman  NFSNET Discussion  4  20070411 20:39 