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.
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
1
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.
