20200916, 02:01  #1 
Sep 2020
7 Posts 
Difficulty of SNFS polynomials
I have recently come across SNFS factorization, and I have yet to find an answer to the following questions: How is the SNFS difficulty calculated? Is there an equation for calculating it?

20200916, 03:16  #2 
"Curtis"
Feb 2005
Riverside, CA
7·643 Posts 
It's generally the size of the input, or the size of the original composite that generates the polynomial (for example, you might have a 25 digit factor already, but doing SNFS on the original number is faster than doing GNFS on the cofactor, so the SNFS difficulty doesn't match the composite size).
Say I'm trying to factor 2^901  1. That can be written 2x^6  1, with x equal to 2^150. That nice poly is what SNFS would use so even if a couple of factors are known and the cofactor is 200 digits, this SNFS job at ~270 digits would be easier than a GNFS of 200. 
20200916, 06:54  #3 
Jul 2003
So Cal
2^{2}·3^{3}·19 Posts 
SNFS requires two polynomials, a degree polynomial , and a linear polynomial, , which share a common root modulo the number you are factoring. The difficulty is given by the size of .
In the example above, and . , , and . So the difficulty is given by the size of , the number being factored. Difficulty is usually expressed as the common log of the number, . 
20200916, 07:41  #4  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2×3×1,733 Posts 
Quote:
A linear polynomial is almost always used (but not exclusively) because of the difficulty of finding good polynomials when neither are linear. 

20200916, 14:34  #5  
Aug 2006
5938_{10} Posts 
Quote:


20200916, 20:02  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·3·7·137 Posts 
Are there any good examples of snfs with nonlinear polynomials? As far as I know only gnfs has been done with nonlinear.

20200916, 22:40  #7 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
289E_{16} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Lucas and Fibonacci SNFS polynomials.  chris2be8  Factoring  26  20190103 16:49 
SNFS polynomials via lindep  fivemack  YAFU  22  20120312 18:48 
SNFS polynomials.  chris2be8  FactorDB  1  20120310 16:49 
SNFS polynomials for k*b^n+1  mdettweiler  Factoring  15  20100114 21:13 
Better measures of SNFS difficulty  fivemack  Factoring  4  20070630 09:20 