mersenneforum.org Choice of SNFS polynomial degree
 Register FAQ Search Today's Posts Mark Forums Read

 2016-12-27, 04:38 #1 lavalamp     Oct 2007 London, UK 22·7·47 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^17-1, 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)?
 2016-12-27, 07:04 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 672 Posts Test-sieving is the way to answer these questions- but you have to test q-values 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 same-sized 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, test-sieving is the way forward.
2016-12-27, 07:46   #3
axn

Jun 2003

7×683 Posts

Quote:
 Originally Posted by lavalamp 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.
Are you sieving the deg-6 on the algebraic side? That _should_ be better than sieving on the rational side.

2016-12-27, 07:49   #4
axn

Jun 2003

7×683 Posts

Quote:
 Originally Posted by lavalamp degree 5, difficulty 211
Are you trying to sieve x^5-34179328063^3 ?!! What about 34179328063^2*x^5-1 ?

2016-12-27, 11:44   #5
lavalamp

Oct 2007
London, UK

22×7×47 Posts

Quote:
 Originally Posted by VBCurtis 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 same-sized coefficients on the polys.
So what are the optimal ranges for degree 4, 5, 6, 7, 8?

Quote:
 Originally Posted by axn Are you sieving the deg-6 on the algebraic side? That _should_ be better than sieving on the rational side.
I'm sieving whatever factmsieve.py is sieving.

Quote:
 Originally Posted by axn Are you trying to sieve x^5-34179328063^3 ?!! What about 34179328063^2*x^5-1 ?
Surely that would be worse with such a large a5 coefficient? Regardless, neither one of these would be the fastest, the degree 6 and 8 polynomials are both quite nice; x^6 - p and x^8 + x^7 - 7x^6 - 6x^5 + 15x^4 + 10x^3 - 10x^2 - 4x + 1.

This is why I initially chose the degree 8 polynomial, it has such small coefficients.

2016-12-27, 12:00   #6
axn

Jun 2003

7×683 Posts

Quote:
 Originally Posted by lavalamp I'm sieving whatever factmsieve.py is sieving.
You should figure out which is it, and if necessary, force the script to choose the "right" side to sieve.
Quote:
 Originally Posted by lavalamp Surely that would be worse with such a large a5 coefficient?
You seem to be under the impression that the leading coefficient is somehow "special"? Your choice of deg-5 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:
 Originally Posted by lavalamp Regardless, neither one of these would be the fastest, the degree 6 and 8 polynomials are both quite nice; x^6 - p and x^8 + x^7 - 7x^6 - 6x^5 + 15x^4 + 10x^3 - 10x^2 - 4x + 1. This is why I initially chose the degree 8 polynomial, it has such small coefficients.
I do believe that the deg-6 is better than the deg-5 I proposed. However, coefficients are only part of he story. Larger coefficients as well as larger degree both mean larger number that needs to be smooth. We need to choose a degree such that both the algebraic and rational polys yield roughly equal-sized numbers ("norms") that need to be smooth. If they are lopsided, then it would make our task much more difficult, as the bigger side would be much more difficult to be smooth (which is the reason why I suggested to sieve the algebraic side for the deg-6, as that would be the bigger side).

 2016-12-27, 13:59 #7 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 167716 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.
2016-12-27, 16:45   #8
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

672 Posts

Quote:
 Originally Posted by lavalamp So what are the optimal ranges for degree 4, 5, 6, 7, 8?
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 210-215, 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 115-215ish
deg 6 215-320ish
deg 7 >320
SNFS ranges should be similar, ceteris paribus.

 2016-12-28, 21:31 #9 swellman     Jun 2012 55208 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 (14-18 hours) in processing each relation in the sqrt phase of a septic. Can't imagine a degree 8!
2016-12-29, 00:28   #10
lavalamp

Oct 2007
London, UK

24448 Posts

Quote:
 Originally Posted by axn Are you sieving the deg-6 on the algebraic side? That _should_ be better than sieving on the rational side.
It appears that (at least in this case) factmsieve.py is sieving on the rational side. However it now has 86% of the estimated minimum relations, and I do not know how to tell it to use the algebraic side, so I think I will let this one finish. Perhaps next time I will experiment further.

Quote:
 Originally Posted by VBCurtis For GNFS: deg 4 under 115 digits deg 5 115-215ish deg 6 215-320ish deg 7 >320 SNFS ranges should be similar, ceteris paribus.
Thank-you, I'll bear these ranges in mind for future poly selection.

Last fiddled with by lavalamp on 2016-12-29 at 00:29

 2018-02-10, 07:27 #11 lavalamp     Oct 2007 London, UK 22·7·47 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 14 2017-02-18 19:46 wblipp Factoring 6 2011-08-23 04:59 Batalov Factoring 1 2009-11-17 21:18 joral Factoring 6 2008-09-26 22:15 R.D. Silverman NFSNET Discussion 4 2007-04-11 20:39

All times are UTC. The time now is 00:54.

Mon Nov 30 00:54:41 UTC 2020 up 80 days, 22:05, 3 users, load averages: 1.39, 1.38, 1.32