 mersenneforum.org How To Evaluate SNFS Polynomial Tricks?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2011-04-10, 22:50 #1 wblipp   "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^7-1)/(p-1) when it is the range that is optimal for 5th degree polynomials. The obvious polynomial is the sixth degree x6+x5+x4+x3+x1+x+1 Is it ever better to use: (p+1)x5+x4+x3+x1+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.   2011-04-11, 01:36 #2 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 41×229 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.126e-24, alpha 1.694, combined = 1.542e-14 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 msieve-able files and a command-line. 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=x-a where |a|<=5); I can tell more about this particular case if anyone's interested.   2011-04-11, 02:57   #3
wblipp

"William"
May 2003
New Haven

3·787 Posts Quote:
 Originally Posted by Batalov 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=x-a where |a|<=5); I can tell more about this particular case if anyone's interested.
Oddperfect is doing a bunch of p^11-1 from Pascals t files of first composites, so I'm very interested in hearing about this.

William   2011-04-11, 04:11 #4 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 41·229 Posts Well, this is not going to help with b11-1. This is for the Aurifeuillian 1122m+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^4-363*t^2) %7 = (-14641*N^2 - 1331*N - 1331)/N ? f/N^5-(t^5+11*t^4-363*t^2-1331*t) %8 = -1331 ? f/N^5-(t^5+11*t^4-363*t^2-1331*t-1331) %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^4-363*t^2-1331*t-1331 %2 = x^5 + 16*x^4 + 54*x^3 - 287*x^2 - 2008*x - 3013 ? t=x-1 ? t^5+11*t^4-363*t^2-1331*t-1331 %4 = x^5 + 6*x^4 - 34*x^3 - 307*x^2 - 644*x - 353 ? t=x-2 ? t^5+11*t^4-363*t^2-1331*t-1331 %6 = x^5 + x^4 - 48*x^3 - 179*x^2 - 151*x + 23 ? t=x-3 ? t^5+11*t^4-363*t^2-1331*t-1331 %8 = x^5 - 4*x^4 - 42*x^3 - 39*x^2 + 64*x + 43 ? t=x-4 ? t^5+11*t^4-363*t^2-1331*t-1331 %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 :-) Then the skew for all candidate polynomials can be optimized by test sieving... The last one was used for factoring 11,539M.   2011-04-15, 16:22   #5
chris2be8

Sep 2009

34·52 Posts Quote:
 Originally Posted by wblipp The specific question I'm wondering about today is factoring (p^7-1)/(p-1) when it is the range that is optimal for 5th degree polynomials. The obvious polynomial is the sixth degree x6+x5+x4+x3+x1+x+1 Is it ever better to use: (p+1)x5+x4+x3+x1+x+1
I don't think it ever will be. Factoring (p^17-1)/(p-1) I found that the quintic with c5: p*p and c0: 1 was slower than a sextic (c6: 1 and c0: p) or a quartic (c4: p and c0:1). The huge coefficients were killers. Even at about 100 digits a sextic is only about twice as slow as a quartic.

The only step I can think of is to halve the degree to degree 3. That might be faster at about 80-90 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post mhill12 Factoring 59 2013-09-09 22:40 ryanp Factoring 9 2013-04-03 06:33 wblipp Factoring 6 2011-08-23 04:59 fivemack Factoring 2 2007-07-09 15:09 R.D. Silverman NFSNET Discussion 4 2007-04-11 20:39

All times are UTC. The time now is 01:20.

Tue Apr 13 01:20:58 UTC 2021 up 4 days, 20:01, 1 user, load averages: 2.62, 2.36, 2.40

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