Choice of SNFS polynomial degree

lavalamp · 2016-12-27, 04:38

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

VBCurtis · 2016-12-27, 07:04

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.

axn · 2016-12-27, 07:46

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.

axn · 2016-12-27, 07:49

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 ?

lavalamp · 2016-12-27, 11:44

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.

axn · 2016-12-27, 12:00

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

henryzz · 2016-12-27, 13:59

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.

VBCurtis · 2016-12-27, 16:45

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.

swellman · 2016-12-28, 21:31

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!

lavalamp · 2016-12-29, 00:28

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.

lavalamp · 2018-02-10, 07:27

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?

2016-12-27, 04:38	#1
lavalamp Oct 2007 Manchester, UK 1381₁₀ 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)?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
SNFS Polynomial for 919^87-1	wblipp	Factoring	6	2011-08-23 04:59
On the skew choice for SNFS	Batalov	Factoring	1	2009-11-17 21:18
GNFS polynomial degree	joral	Factoring	6	2008-09-26 22:15
SNFS Polynomial	R.D. Silverman	NFSNET Discussion	4	2007-04-11 20:39

2016-12-27, 07:04	#2
VBCurtis "Curtis" Feb 2005 Riverside, CA 1774₁₆ 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, 13:59	#7
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 14131₈ 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-28, 21:31	#9
swellman Jun 2012 7·11·53 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!

2018-02-10, 07:27	#11
lavalamp Oct 2007 Manchester, UK 1,381 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?