How To Evaluate SNFS Polynomial Tricks?

[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

x⁶+x⁵+x⁴+x³+x¹+x+1

Is it ever better to use:

(p+1)x⁵+x⁴+x³+x¹+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.

[Batalov]

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.

[wblipp]

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

[Batalov]

Well, this is not going to help with b¹¹-1.
This is for the Aurifeuillian 11^22m+11+1, but here goes, without comment:

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

[chris2be8]

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

x⁶+x⁵+x⁴+x³+x¹+x+1

Is it ever better to use:

(p+1)x⁵+x⁴+x³+x¹+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