1
$\begingroup$

So according to the wikipedia page https://en.wikipedia.org/wiki/General_number_field_sieve the algorithm has complexity $$\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)$$ but I am not too familiar with this notation.

I understand the big-O notation for complexity if somebody could explain how this is similar and what it means for the running time it would be appreciated!!

Also I know that this is subexponential in the size of $n$ running time, but I am unsure how to show this just from this complexity.

$\endgroup$
3
  • $\begingroup$ yeah $\exp(x)=e^x$ its just when $x$ is a large function it gets clustered so I decided to leave it in this form $\endgroup$
    – Matt
    Mar 26, 2019 at 0:02
  • $\begingroup$ Err, no. I thought that was the problem. You say you understand the notation, yet that's the notation for the sub-ex type. It's just a bit slower that exponential. It's probably me, but what's the question again? $\endgroup$
    – Paul Uszak
    Mar 26, 2019 at 0:11
  • $\begingroup$ Oh sorry for the confusion! Well I understand the usual notation I've seen in the past for complexity, such as $O(n)$ and $O(n^2)$ etc. but I am unsure how this related to that notation exactly. For example, is there an $x$ such that this expression is the same as $O(x)$, and if not what does it mean by "complexity", does it mean plugging in a value of $n$ gives us the approximate time taken to run and thats all? $\endgroup$
    – Matt
    Mar 26, 2019 at 0:17

2 Answers 2

2
$\begingroup$

Since the numeric constant in the exponent is approximately $1.923 $ the expression for the average number of iterations, say time complexity $T$ given by $$T=\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)$$ is proportional to (for $n$ large enough so that $o(1)$ term is negligible) $$T\propto \exp \left(1.923 \times (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)$$ which is upper bounded as (ignoring a multiplicative constant in front) $$T\leq \exp \left(2 (\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}} \right)=T_0^2.$$

Clearly $T$ is polynomial/exponential if and only if $T_0$ is.

Now consider the more general expression $$f(\alpha,n)=\exp \left( (\ln n)^{\alpha}(\ln \ln n)^{1-\alpha} \right),\quad \alpha \in [0,1],$$ and note that when $\alpha=1,$ $f(1,n)=\exp(\ln n)=n,$ hence it is exponential in the bitsize $\log_2 n$ of the input $n.$

Also note that when $\alpha=0,$ $f(0,n)=\exp(\ln\ln n)=\ln n,$ hence it is polynomial in the bitsize $\log_2 n$ of the input $n.$

However we have $T_0=f(1/3,n)$ with $\alpha=1/3$ above so the complexity we have is a linear combination in the exponent of polynomial and exponential complexities. This is referred to as subexponential but superpolynomial complexity.

$\endgroup$
2
$\begingroup$

This is the growth curve of the expectation value of the number of steps in the algorithm to factor $n$, or asymptotic expected running time. The $o(1)$ term means a function that converges to zero as $n \to \infty$. Here a ‘step’ is the number of iterations of the loops in the algorithm; each ‘step’ corresponds to an unspecified number of (say) bit operations, and we are not considering storage or communication costs. For a more detailed area*time cost analysis, see, e.g., the batch NFS paper.

$\endgroup$

Your Answer

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

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