mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-04-10, 22:50   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default 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.
wblipp is offline   Reply With Quote
Old 2011-04-11, 01:36   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41×229 Posts
Default

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.

Batalov is offline   Reply With Quote
Old 2011-04-11, 02:57   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
wblipp is offline   Reply With Quote
Old 2011-04-11, 04:11   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41·229 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2011-04-15, 16:22   #5
chris2be8
 
chris2be8's Avatar
 
Sep 2009

34·52 Posts
Default

Quote:
Originally Posted by wblipp View Post
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
chris2be8 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SNFS Polynomial selection help? mhill12 Factoring 59 2013-09-09 22:40
SNFS polynomial with very low yield ryanp Factoring 9 2013-04-03 06:33
SNFS Polynomial for 919^87-1 wblipp Factoring 6 2011-08-23 04:59
Concocting an SNFS polynomial for 2^2376-1 fivemack Factoring 2 2007-07-09 15:09
SNFS Polynomial 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.