Everyone keeps claiming that integer factoring is in $NP$ but I just don't get it... Even with the simplest algorithm (division with all integers up to $\sqrt{n}$) the complexity should be $\sqrt{n}\log(n)$... How is that not in $P$? Is there something I'm missing?

  • 1
    $\begingroup$ $n$ is not a number to be factored, it's it's length. So, the complexity would be $\sqrt{2^n}n$. $\endgroup$ – rus9384 Aug 2 '17 at 3:58
  • $\begingroup$ $O(\sqrt{n} \log n)$ is exponential in the size of $n$, the size being $\log_2 n$. It would be $O(\sqrt{2^{\log_2 n}} \log n)$. $\endgroup$ – ryan Aug 2 '17 at 4:00
  • $\begingroup$ cs.stackexchange.com/q/6588/755 $\endgroup$ – D.W. Aug 2 '17 at 5:35
  • $\begingroup$ @D.W. That is not somehow connected to question, since any problem in P can be reduced to NPC problem. $\endgroup$ – rus9384 Aug 2 '17 at 5:51
  • $\begingroup$ Read the definition. P is about the running time function in input length, not the encoded number. $\endgroup$ – Raphael Aug 2 '17 at 5:53

One of the things to remember when dealing with natural numbers (and others, but naturals are the central things here) is the encoding, and that the definitions of $P$ and $NP$ reference the length of the encoding of the input on a Turing Machine (or something closely equivalent).

So the input to integer factoring, as a decision problem, is typically two numbers $n$ and $k$ in $\mathbb{N}$, and the question is whether $n$ has a factor $d \leq k$.

So the magnitude of $n$ is $n$, but the size of its encoding may be only $O(\log n)$ (for example, in binary). This is exponentially smaller than $n$ (i.e. if we take $n' = \log_{2} n$, then $n = 2^{n'}$).

So then the $\sqrt{n}\log n$ "obvious" algorithm runs in time $2^{\frac{n'}{2}}\cdot n'$, which is exponential in the input size.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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