View Single Post
Old 2020-09-16, 06:54   #3
frmky's Avatar
Jul 2003
So Cal

22·33·19 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.
frmky is offline   Reply With Quote