Difficulty of SNFS polynomials

StrongestStrike · 2020-09-16, 02:01

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?

VBCurtis · 2020-09-16, 03:16

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.

frmky · 2020-09-16, 06:54

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$ .

xilman · 2020-09-16, 07:41

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.

CRGreathouse · 2020-09-16, 14:34

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.

henryzz · 2020-09-16, 20:02

Are there any good examples of snfs with nonlinear polynomials? As far as I know only gnfs has been done with nonlinear.

xilman · 2020-09-16, 22:40

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.

2020-09-16, 02:01	#1
StrongestStrike 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Lucas and Fibonacci SNFS polynomials.	chris2be8	Factoring	26	2019-01-03 16:49
SNFS polynomials via lindep	fivemack	YAFU	22	2012-03-12 18:48
SNFS polynomials.	chris2be8	FactorDB	1	2012-03-10 16:49
SNFS polynomials for k*b^n+-1	mdettweiler	Factoring	15	2010-01-14 21:13
Better measures of SNFS difficulty	fivemack	Factoring	4	2007-06-30 09:20

2020-09-16, 03:16	#2
VBCurtis "Curtis" Feb 2005 Riverside, CA 3·29·53 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 2055₁₀ 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, 20:02	#6
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2×2,897 Posts	Are there any good examples of snfs with nonlinear polynomials? As far as I know only gnfs has been done with nonlinear.