mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-09-16, 02:01   #1
StrongestStrike
 
Sep 2020

78 Posts
Default 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?
StrongestStrike is offline   Reply With Quote
Old 2020-09-16, 03:16   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3×7×11×19 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2020-09-16, 06:54   #3
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

32×227 Posts
Default

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.
frmky is offline   Reply With Quote
Old 2020-09-16, 07:41   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×32×281 Posts
Default

Quote:
Originally Posted by frmky View Post
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.
xilman is offline   Reply With Quote
Old 2020-09-16, 14:34   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

23·3·13·19 Posts
Default

Quote:
Originally Posted by xilman View Post
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 is offline   Reply With Quote
Old 2020-09-16, 20:02   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131448 Posts
Default

Are there any good examples of snfs with nonlinear polynomials? As far as I know only gnfs has been done with nonlinear.
henryzz is offline   Reply With Quote
Old 2020-09-16, 22:40   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·32·281 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
xilman is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 01:50.

Fri Oct 23 01:50:14 UTC 2020 up 42 days, 23:01, 0 users, load averages: 1.40, 1.42, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.