View Single Post
2020-09-16, 07:41   #4
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

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