# 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.

## marked as duplicate by Yuval Filmus complexity-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 21 '18 at 18:17

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