I can see that Integer factorization problem is in NP. I am looking for a simple intuition behind this. For example if we take the problem of sorting the complexity is $n\log n$ for merge/quick sort where $n$ is the number of objects to be sorted. Along that line if take $n$ as the number to be factorized, then factorization algorithm can be run in polynomial time (checking from 2 to $\sqrt{n}$). I understand this is not the case. Please give how to look it this problem compared to that of sorting problem.


The flaw in your reasoning is in considering $n$ as the size of the input.
The input is a number $n$ and its size in memory is $\lfloor \log_2(n) + 1 )\rfloor$ bits.

Thus, $O(\sqrt n)$ is not polynomial in the size of the input.

In order to be polynomial, you would need an algorithm with time complexity $O(\log^k n)$ which would correspond to a polynomial algorithm of order $k$ w.r.t. the size of the input.

| cite | improve this answer | |
  • $\begingroup$ How you reach the complexity $O(log^kn)$ $\endgroup$ – user5507 Oct 22 '18 at 14:55

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