Return to Question

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?

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.

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?

PS

ChatGPT said the following when I asked:

Me: Is factoring in quasi-polynomial time?

ChatGPT: Yes, factoring is believed to be solvable in quasi-polynomial time. In 2019, a team of researchers led by Martin R. Albrecht proposed a new algorithm called the “Number Field Sieve in Quasi Polynomial Time” (NFQPT) for factoring integers. The algorithm has a time complexity of $\exp(O(\log(N)^{1/3}\log(\log(N))^{2/3}))$. This means that the algorithm runs in time that is quasi-polynomial in the number of digits of $N$, which is much faster than the current best-known algorithm for factoring, the General Number Field Sieve, which has a time complexity of $\exp(O(\log(N)^{1/2}\log(\log(N))^{1/2}))$ and is considered to be sub-exponential. However, it should be noted that NFQPT has not been implemented or tested extensively and is still in the research phase.

I couldn’t find the mentioned research result. Can you?

PPS

Today ChatGPT is in another mood and says the following:

Me: Is factoring in quasi-polynomial time?

ChatGPT: Recent research has shown that factoring is not in quasi-polynomial time unless the polynomial hierarchy collapses. In 2019, researchers published a paper that showed that factoring integers cannot be solved in quasi-polynomial time unless the polynomial hierarchy collapses to its third level. This result implies that factoring is unlikely to be solvable in quasi-polynomial time, unless major breakthroughs are made in complexity theory.

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?

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?

PS

ChatGPT said the following when I asked:

Is factoring in quasi-polynomial time?

Yes, factoring is believed to be solvable in quasi-polynomial time. In 2019, a team of researchers led by Martin R. Albrecht proposed a new algorithm called the “Number Field Sieve in Quasi Polynomial Time” (NFQPT) for factoring integers. The algorithm has a time complexity of $\exp(O(\log(N)^{1/3}\log(\log(N))^{2/3}))$. This means that the algorithm runs in time that is quasi-polynomial in the number of digits of $N$, which is much faster than the current best-known algorithm for factoring, the General Number Field Sieve, which has a time complexity of $\exp(O(\log(N)^{1/2}\log(\log(N))^{1/2}))$ and is considered to be sub-exponential. However, it should be noted that NFQPT has not been implemented or tested extensively and is still in the research phase.

I couldn’t find the mentioned research result. Can you?

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?

PS

ChatGPT said the following when I asked:

Me: Is factoring in quasi-polynomial time?

ChatGPT: Yes, factoring is believed to be solvable in quasi-polynomial time. In 2019, a team of researchers led by Martin R. Albrecht proposed a new algorithm called the “Number Field Sieve in Quasi Polynomial Time” (NFQPT) for factoring integers. The algorithm has a time complexity of $\exp(O(\log(N)^{1/3}\log(\log(N))^{2/3}))$. This means that the algorithm runs in time that is quasi-polynomial in the number of digits of $N$, which is much faster than the current best-known algorithm for factoring, the General Number Field Sieve, which has a time complexity of $\exp(O(\log(N)^{1/2}\log(\log(N))^{1/2}))$ and is considered to be sub-exponential. However, it should be noted that NFQPT has not been implemented or tested extensively and is still in the research phase.

I couldn’t find the mentioned research result. Can you?

PPS

Today ChatGPT is in another mood and says the following:

Me: Is factoring in quasi-polynomial time?

ChatGPT: Recent research has shown that factoring is not in quasi-polynomial time unless the polynomial hierarchy collapses. In 2019, researchers published a paper that showed that factoring integers cannot be solved in quasi-polynomial time unless the polynomial hierarchy collapses to its third level. This result implies that factoring is unlikely to be solvable in quasi-polynomial time, unless major breakthroughs are made in complexity theory.