20150527, 20:14  #1 
"Daniel Jackson"
May 2011
14285714285714285714
2×3×127 Posts 
How To Calculate SNFS Poly?
How do I calculate a SNFS poly? Is there an easy formula based on N?
Last fiddled with by Stargate38 on 20150527 at 20:17 
20150527, 20:21  #2 
"Curtis"
Feb 2005
Riverside, CA
5^{2}·229 Posts 
Give an example of the form of the number you wish to factor. There are many cases.

20150527, 20:35  #3 
"Daniel Jackson"
May 2011
14285714285714285714
2×3×127 Posts 
(n^{2p}+1)/(n^{2}+1) with prime p
n^{2[SUP]x}[/SUP]+1 a^{n}±b^{n} (take out algebraic factors first) i.e. 4607450010708798^{8}+1 (known factor before I factored it: 449). I wasted 23 CPUdays doing GNFS on it, before I realized that I could have done it in a matter of hours with SNFS. Last fiddled with by Stargate38 on 20150527 at 20:42 
20150527, 21:30  #4 
"William"
May 2003
Near Grandkid
946_{16} Posts 
Have you read the Mersenne Wiki article on polynomial selection?

20150527, 21:47  #5 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×313 Posts 

20150527, 21:52  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·313 Posts 
Quote:
For your first question (n^2p + 1)/(n^2+1) may I suggest performing the division and looking at the result? One gets a dense polynomial of degree 2p2........ n^(2^x) + 1 is algebraically prime. for a^n +/ b^n, start by factoring it, completely. Or are you asking about the primitive cofactor? Last fiddled with by R.D. Silverman on 20150527 at 21:54 

20150527, 22:12  #7 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1C35_{16} Posts 
Yafu can do automatic snfs poly selection for the example as well as the second two forms (though I don't know if it can take advantage of the power of 2 exponent, or if that's even possible).
Last fiddled with by Dubslow on 20150527 at 22:13 
20150527, 23:09  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×313 Posts 
Quote:
The OP asked HOW. Suggesting to use a black box does not answer that question. Indeed. Your statement "I don't know........possible." suggests that you should not have even tried to answer this question. (Hint: Once you have decided the degree for the SNFS algebraic polynomial for 2^2^n+1, it is trivial first year algebra to find the representation). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SNFS poly for b^n1, n prime?  ryanp  Factoring  6  20130719 17:23 
Ooops....SNFS poly for primes?  schickel  FactorDB  0  20111216 18:07 
SNFS Poly creation for n=2*x^2  1  JoeCrump  Factoring  3  20091029 21:00 
Homogeneous Cunningham snfs poly selection?  nuggetprime  Factoring  22  20080815 10:01 
How do you calculate?  fropones  Lone Mersenne Hunters  1  20030527 23:01 