View Single Post
Old 2020-09-16, 07:41   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·5,197 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