# Understanding integer factorization is NP [duplicate]

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.
• How you reach the complexity $O(log^kn)$ – user5507 Oct 22 '18 at 14:55