2
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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?.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.