20110410, 22:50  #1 
"William"
May 2003
New Haven
3·787 Posts 
How To Evaluate SNFS Polynomial Tricks?
The specific question I'm wondering about today is factoring (p^71)/(p1) when it is the range that is optimal for 5th degree polynomials. The obvious polynomial is the sixth degree
x^{6}+x^{5}+x^{4}+x^{3}+x^{1}+x+1 Is it ever better to use: (p+1)x^{5}+x^{4}+x^{3}+x^{1}+x+1 And is there some method other than experimentation and trial sieving to answer this? There are other situations where tradeoffs can be made by shuffling values between the variables and the coefficients. I'm wondering if there is any easy way to tell when it's likely to be worthwhile. 
20110411, 01:36  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·1,877 Posts 
I have a simple trick (and somewhere on the forum some harder ones).
Prerequisites: 1. a poly file (say, test.poly) 2. the factMsieve.pl script Testing (without actually sieving): 1. Edit the factMsieve.pl script: set $DOCLASSICAL=1; 2. run "factMsieve.pl test" and kill it when this line will be printed: skew 1.00, size 2.126e24, alpha 1.694, combined = 1.542e14 rroots = 0 mostly you need the Murphy E score (a.k.a. combined) 3. Copy test.poly to test2.poly and make edits 4. run "factMsieve.pl test2" etc. You will be looking for the best E score. That's all. The script only helps you to prepare msieveable files and a commandline. This method doesn't quite work for comparing polynomials of degrees more different than 1 apart (e.g. for 4 vs 6, or 4 vs 8 you'd need some test sieving for the final decision). _________ I've used it for evaluating some simple rotations of (for example) 11L/M polynomials (a degree 5 poly after a x=t+1/t substitution; replacing x with t=xa where a<=5); I can tell more about this particular case if anyone's interested. 
20110411, 02:57  #3  
"William"
May 2003
New Haven
3×787 Posts 
Quote:
William 

20110411, 04:11  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·1,877 Posts 
Well, this is not going to help with b^{11}1.
This is for the Aurifeuillian 11^{22m+11}+1, but here goes, without comment: Code:
? factor(11^11*N^22+1) %1 = [11*N^2 + 1 1] [161051*N^10  161051*N^9 + 73205*N^8  14641*N^7  1331*N^6 + 1331*N^5  121*N^4  121*N^3 + 55*N^2  11*N + 1 1] [161051*N^10 + 161051*N^9 + 73205*N^8 + 14641*N^7  1331*N^6  1331*N^5  121*N^4 + 121*N^3 + 55*N^2 + 11*N + 1 1] ? f=161051*N^10 + 161051*N^9 + 73205*N^8 + 14641*N^7  1331*N^6  1331*N^5  121*N^4 + 121*N^3 + 55*N^2 + 11*N + 1 ? t=11*N+1/N %3 = (11*N^2 + 1)/N ? f/N^5(t^5) %4 = (161051*N^8 + 14641*N^6  14641*N^5  1331*N^4  1331*N^3 + 121*N^2 + 11)/N^4 ? f/N^5(t^5+11*t^4) %5 = (43923*N^4  14641*N^3  9317*N^2  1331*N  363)/N^2 ? f/N^5(t^5+11*t^4363*t^2) %7 = (14641*N^2  1331*N  1331)/N ? f/N^5(t^5+11*t^4363*t^21331*t) %8 = 1331 ? f/N^5(t^5+11*t^4363*t^21331*t1331) %10 = 0 #this is a good initial poly, ...but we can possibly do a bit better: #new session ? t=x+1 ? t^5+11*t^4363*t^21331*t1331 %2 = x^5 + 16*x^4 + 54*x^3  287*x^2  2008*x  3013 ? t=x1 ? t^5+11*t^4363*t^21331*t1331 %4 = x^5 + 6*x^4  34*x^3  307*x^2  644*x  353 ? t=x2 ? t^5+11*t^4363*t^21331*t1331 %6 = x^5 + x^4  48*x^3  179*x^2  151*x + 23 ? t=x3 ? t^5+11*t^4363*t^21331*t1331 %8 = x^5  4*x^4  42*x^3  39*x^2 + 64*x + 43 ? t=x4 ? t^5+11*t^4363*t^21331*t1331 %10 = x^5  9*x^4  16*x^3 + 53*x^2 + 37*x  23 #this poly is pretty good, small coeffs, and Murphy E score agrees :) 
20110415, 16:22  #5  
Sep 2009
7E6_{16} Posts 
Quote:
The only step I can think of is to halve the degree to degree 3. That might be faster at about 8090 digits (and SNFS could still beat QS). But it's not worth it unless you have a lot of numbers like that to do. Chris K 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SNFS Polynomial selection help?  mhill12  Factoring  59  20130909 22:40 
SNFS polynomial with very low yield  ryanp  Factoring  9  20130403 06:33 
SNFS Polynomial for 919^871  wblipp  Factoring  6  20110823 04:59 
Concocting an SNFS polynomial for 2^23761  fivemack  Factoring  2  20070709 15:09 
SNFS Polynomial  R.D. Silverman  NFSNET Discussion  4  20070411 20:39 