View Single Post
Old 2020-09-16, 07:41   #4
xilman's Avatar
May 2003
Down not across

2·5,197 Posts

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