# Is GNFS quasi-polynomial-time?

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

The same site also mentions that 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, in other words, $$n=\log N$$.

Now my question is whether GNFS is quasi-polynomial-time. It appears not, because of the existence of the $$(\log 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 the intersection requires.

So the running time is exponential. Am I right?

Update

In the table of contents of the book Prime Numbers: A Computational Perspective, NFS and Quadratic Sieve (QS) are both listed in Chapter 6 Subexponential Factoring Algorithms.

• I encourage you to edit your post to avoid using the same variable $n$ for two different things.
– D.W.
Oct 25, 2022 at 8:39

Using the same variable $$n$$ to mean two different things in two places is confusing. In the context of your question, I think it is better to describe the running time of GNFS as $$\exp\left( (c+o(1)) \, n^{\frac{1}{3}}(\log n)^{\frac{2}{3}}\right),$$ where $$n$$ is the number of bits in the number being factored, and $$c$$ is a constant.
With this formulation, it is clear that it is not in QP ($$n^{1/3}$$ is not in $$O(\log^c n)$$ for any $$c$$), and not in SUBEXP ($$n^{1/3}$$ is not in $$O(n^{\varepsilon})$$ when $$0<\varepsilon<1/3$$). Yet as Wikipedia explains, there are multiple different definitions of sub-exponential; by some of them, GNFS runs in sub-exponential time, and by others, it does not. See also Are there subexponential-time algorithms for NP-complete problems?.