20210530, 06:12  #1 
Aug 2020
79*6581e4;3*2539e3
601 Posts 
How to identify SNFS candidates and factor them?
Since I just spent five days factoring a number with GNFS that could have been done in an hour using SNFS, I'd really like to know how to identify candidates for SNFS and how to factor them efficiently.
All I know (If I got it correct) is that all Mersenne/Proth/Riesel/... numbers should be candidates for SNFS since they all are of the form k*b^n+c. Is there a guide or howto on how to identify candidates, prepare a polynomial and which software to use for factoring? 
20210530, 07:21  #2 
Mar 2019
311 Posts 
Generally speaking, numbers of the form \(b^n1\) or \(b^n+1\) or one of their divisors work best, though there are some other forms that work.
https://www.rieselprime.de/ziki/Spec...er_field_sieve and https://www.rieselprime.de/ziki/SNFS...mial_selection have some more background reading. As far as running the factorization, YAFU is very helpful at generating the actual poly for you. It can run the whole factorization, or you can use the poly in conjunction with other tools like CADO or GGNFS. Last fiddled with by mathwiz on 20210530 at 07:23 
20210530, 13:27  #3 
Apr 2020
5^{3}×7 Posts 
YAFU is the fireandforget method, or at least it should be, because a bug seems to have crept in; hopefully Ben will fix this soon.
CADO can run SNFS perfectly well. EdH has written a guide for running SNFS with CADO, though it still relies on YAFU for the polynomial so won't work until the bug is fixed. It's mostly very good, but with one small caveat (lambdas are not directly comparable between YAFU and CADO so best to just leave out the lambda lines completely, CADO can choose its own) and one big caveat, which is that copying the tasks.sieve.rels_wanted line across from the CADO parameter file could lead to collecting vastly more relations than are needed if YAFU's chosen lpb bounds differ from CADO's. The easiest way around this is probably to use YAFU's own estimate of required relations. This is fudge(lpbr) * 2^lpbr / log(2^lpbr) + fudge(lpba) * 2^lpba / log(2^lpba) where the logs are natural log and the fudge factors are given by the following table: Code:
lpb fudge(lpb) 24 0.40 25 0.50 26 0.60 27 0.70 28 0.76 29 0.84 30 0.89 31 0.91 32 0.95 33 0.98 If you don't want to wait for the YAFU bug to be fixed, it's not hard to adapt the techniques for b^n+1 in the links that mathwiz gave to k*b^n+c. Last fiddled with by charybdis on 20210530 at 13:33 
20210530, 14:47  #4 
"Curtis"
Feb 2005
Riverside, CA
5565_{10} Posts 
For your proth searches, you want to write your input number as a * (x^5) + c.
Then c5 = a, c0 = c, y1 = 1, y0 = x (I forget if it's positive or negative). 5th degree polys are best for roughly 120 to 200 digits; above 200 digits you would use the same concept but a 6th degree polynomial. There's a gray area where you might test both 5th and 6th degree. So, say you want to factor 13*2^698 + 1. 698 is close to 700, so multiplying my input by 4 gives me 13*2^700 + 4. My poly would be 13*(2^140)^5 + 4, so c5 = 13, c0 = 4, and y0 = 2^140. For 13*2^697+1, I would take out 2 2's from the large power, making 52*2^695+1. c5=52, c0 = 1, y0=2^139. In your efforts, since your leading coefficient is already large, you won't want to pull out 2's in this manner rather, you'll use the first style to make c0 bigger rather than making c1 bigger. SNFS difficulty is mostly linked to the size of the largest poly coefficient, so you want to avoid making c5 bigger. I use wolfram alpha to get the expansions of large powers of 2. The reference sites mentioned in earlier posts are much more detailed, but I thought maybe a concrete example would be of use. 
20210530, 15:16  #5  
Apr 2020
5^{3}·7 Posts 
Quote:
Quote:
We ought to take the rational norm into account too. This is Y1*a + Y0*b, so the second term massively dominates. The skew varies by a factor of 2 between the two polynomials, so the "make c0 larger" polynomial has b values around a factor of sqrt(2) smaller than the "make c5 larger" poly. But its Y0 value is doubled (2^140 vs 2^139 for your example), so the rational norm is larger too. If you calculate some Escores you'll see that they bear this out. 

20210530, 15:59  #6  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2D42_{16} Posts 
Quote:
There are so many numbers which can be represented in that way it is hard to be more precise. For instance, you may be interested in factoring integers N=1+2x+6x^{2}24x^{3}120x^{4}+720x^{5} for all I know. 

20210530, 20:36  #7 
Aug 2004
New Zealand
2·5·23 Posts 
A lot of popular projects have numbers which can be handled with SNFS including Cunningham and related, cyclotomic, Cullen, Woodall, Fibonacci and Lucas and related, x^y+y^x. In addition to what has already been mentioned, factordb can sometimes give you a ready made SNFS polynomials (but be aware it is not always right or useful in what it suggests for the polynomial).
As xilman indicates, if you can express your number (or some multiple of your number) as a small degree homogeneous polynomial, then SNFS is probably applicable, although it will not always be the best choice. 
20210531, 03:09  #8  
"Curtis"
Feb 2005
Riverside, CA
3×5×7×53 Posts 
Quote:
10% is not a small difference. Thanks for the teaching moment! 

20210531, 06:44  #9 
Aug 2020
79*6581e4;3*2539e3
601_{10} Posts 
Thanks for all the information, I'll be back with some questions probably...

20210531, 18:02  #10  
Aug 2020
79*6581e4;3*2539e3
601 Posts 
To see if I understood it correctly (that example helped a lot), if I want to factor with SNFS, I follow EdH's guide, with the following modifications:
1) Using selfcreated poly, in the example case: , so c5 = 1281979, c0 = 4, y1 = 1, y0 = 2^105 (negative)? 2) Don't copy lambda0 and lambda1 values to params. So I just leave it out or do I use the ones from the original CADO params file? 3) Calculate rels_wanted using your formula. Quote:


20210531, 19:23  #11  
Apr 2020
5^{3}·7 Posts 
Quote:
EdH's guide relies on using YAFU to generate the parameter file, so you'll need a version of YAFU that doesn't have the SNFS poly selection bug that I mentioned. Alternatively you can use CADO sieving parameters  Curtis's params.c120 in this case  but with tasks.sieve.sqside = 0 for rationalside sieving (I think this will be a little faster than algebraic side?) and the algebraic and rational side parameters swapped (lim0 and lim1 etc). You can keep the lambdas in this case. Neither of these options will give optimal parameters, but at this size it really won't matter too much. For larger numbers you would want to testsieve different choices of parameters, although there are often good theoretical reasons to expect certain parameter choices to be better than others. Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A new tool to identify aliquot sequence margins and acquisitions  garambois  Aliquot Sequences  27  20221108 17:55 
Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic)  EdH  EdH  14  20200420 16:21 
new candidates for M...46 and M48  cochet  Miscellaneous Math  4  20081024 14:33 
Please identify!  BrianE  Lounge  24  20080801 14:13 
Easily identify composites using multiplication  Nightgamer360  Miscellaneous Math  9  20070709 17:38 