mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-12-27, 04:38   #1
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

22·7·47 Posts
Question 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)?
lavalamp is offline   Reply With Quote
Old 2016-12-27, 07:04   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

672 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2016-12-27, 07:46   #3
axn
 
axn's Avatar
 
Jun 2003

7×683 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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 is offline   Reply With Quote
Old 2016-12-27, 07:49   #4
axn
 
axn's Avatar
 
Jun 2003

7×683 Posts
Default

Quote:
Originally Posted by lavalamp View Post
degree 5, difficulty 211
Are you trying to sieve x^5-34179328063^3 ?!! What about 34179328063^2*x^5-1 ?
axn is offline   Reply With Quote
Old 2016-12-27, 11:44   #5
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

22×7×47 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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 View Post
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 View Post
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.
lavalamp is offline   Reply With Quote
Old 2016-12-27, 12:00   #6
axn
 
axn's Avatar
 
Jun 2003

7×683 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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 View Post
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 View Post
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).
axn is offline   Reply With Quote
Old 2016-12-27, 13:59   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

167716 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2016-12-27, 16:45   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

672 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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.
VBCurtis is offline   Reply With Quote
Old 2016-12-28, 21:31   #9
swellman
 
swellman's Avatar
 
Jun 2012

55208 Posts
Default

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!
swellman is online now   Reply With Quote
Old 2016-12-29, 00:28   #10
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

24448 Posts
Default

Quote:
Originally Posted by axn View Post
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 View Post
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
lavalamp is offline   Reply With Quote
Old 2018-02-10, 07:27   #11
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

22·7·47 Posts
Default

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?
lavalamp is offline   Reply With Quote
Reply

Thread Tools


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

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

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