Skip to main content
2 of 16
Big N and small n
Zirui Wang
  • 1k
  • 5
  • 13

Is GNFS quasi-polynomial time?

Wikipedia states the time complexity of the General Number Field Sieve is $$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln N)^{\frac{1}{3}}(\ln \ln N)^{\frac{2}{3}}\right),$$ where $N$ is the number to be factored, not the length of the input.

The same site also mentions quasi-polynomial time is $$\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME} \left(2^{\log^c n}\right),$$ where $n$ is the length of the input.

Now my question is whether the General Number Field Sieve is quasi-polynomial time. It appears not, because of the $(\ln n)^{1/3}$ exponent.

How about sub-exponential? Wikipedia says $$\text{SUBEXP}=\bigcap_{\varepsilon>0} \text{DTIME}\left(2^{n^\varepsilon}\right).$$ I think the answer is still negative because $\varepsilon=1/3$ in this case and it can’t be smaller as in the intersection.

So the running time is exponential. Am I right?

Zirui Wang
  • 1k
  • 5
  • 13