mersenneforum.org Difficulty of SNFS polynomials
 Register FAQ Search Today's Posts Mark Forums Read

 2020-09-16, 02:01 #1 StrongestStrike   Sep 2020 78 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?
 2020-09-16, 03:16 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5·1,013 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.
 2020-09-16, 06:54 #3 frmky     Jul 2003 So Cal 42578 Posts SNFS requires two polynomials, a degree-$d$ polynomial $f(x)$, and a linear polynomial, $g(x)=ax-b$, which share a common root modulo the number you are factoring. The difficulty is given by the size of $a^d f(b/a)$. In the example above, $f(x)=2x^6-1$ and $g(x)=x-2^{150}$. $d=6$, $a=1$, and $b=2^{150}$. So the difficulty is given by the size of $a^d f(b/a)=1^6 f(2^{150}/1) = 2*2^{900}-1 = 2^{901}-1$, the number being factored. Difficulty is usually expressed as the common log of the number, $\log_{2}(2^{901}-1)\approx 901\ \log_{10}(2) = 271.2$.
2020-09-16, 07:41   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

73·151 Posts

Quote:
 Originally Posted by frmky SNFS requires two polynomials, a degree-$d$ polynomial $f(x)$, and a linear polynomial, $g(x)=ax-b$, which share a common root modulo the number you are factoring. The difficulty is given by the size of $a^d f(b/a)$.
Strictly speaking it does not require that one of the polynomials be linear. Any two polynomials which share a common root mod N will work.

A linear polynomial is almost always used (but not exclusively) because of the difficulty of finding good polynomials when neither are linear.

2020-09-16, 14:34   #5
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by xilman Strictly speaking it does not require that one of the polynomials be linear. Any two polynomials which share a common root mod N will work. A linear polynomial is almost always used (but not exclusively) because of the difficulty of finding good polynomials when neither are linear.

 2020-09-16, 20:02 #6 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 173116 Posts Are there any good examples of snfs with nonlinear polynomials? As far as I know only gnfs has been done with nonlinear.
2020-09-16, 22:40   #7
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

73·151 Posts

Quote:
 Originally Posted by henryzz Are there any good examples of snfs with nonlinear polynomials? As far as I know only gnfs has been done with nonlinear.
Good question. I will try to try to find out.

Nonetheless, the general point remains true.

2021-07-09, 11:24   #8
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

3·1,979 Posts

Quote:
 Originally Posted by xilman Good question. I will try to try to find out. Nonetheless, the general point remains true.
I assume you didn't find anything?

2021-07-10, 05:52   #9
bur

Aug 2020
79*6581e-4;3*2539e-3

2·11·19 Posts

Quote:
 Originally Posted by VBCurtis 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).
Does that mean the SNFS job is actually better done on the original composite? I always did it on the co-factor with the poly tailored to the original composite.

 2021-07-10, 10:19 #10 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5×1,013 Posts Bur- You've been doing it correctly.
2021-07-10, 20:18   #11
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

73×151 Posts

Quote:
 Originally Posted by henryzz I assume you didn't find anything?
You assume correctly, but only because I have not yet tried.

Suffering from a bad cold is one reason, but the major one is because I have run out of round tuits.

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Factoring 26 2019-01-03 16:49 fivemack YAFU 22 2012-03-12 18:48 chris2be8 FactorDB 1 2012-03-10 16:49 mdettweiler Factoring 15 2010-01-14 21:13 fivemack Factoring 4 2007-06-30 09:20

All times are UTC. The time now is 09:31.

Sun Nov 28 09:31:34 UTC 2021 up 128 days, 4 hrs, 0 users, load averages: 0.90, 0.99, 0.96