Primality of a Number is NP problem

Primality testing of a number is the method of finding out whether a number is prime or not. I have known this is a non-polynomial problem. In fact most of the recent cryptographic techniques rely on this and the factoring problem of numbers to create secure systems.

But it was never clear to me why. So when this question was put forward to me by Sukanta, I kept thinking. Of course I knew the answer, but did not know the reason for this problem to be NP. Sukanta explained that:

For a number N, the usual prime number testing strategies, iterate for N/2 times, which can be further optimized to N^0.5. So the number of division operations required was a polynomial function of N. At this point, it is very easy to say that this is polynomial solvable.

But the thing that I missed here, is that N was the number itself, not the size of the input set on which the complexity of a program is computed. So if we take the input size as the number of digits of N, then the size of input set is log N. So the complexity of the program is exponential, and not polynomial, as I mistook in last step.

Well, there is never any shortage of new things to learn. I thank Sukanta, who explained it in such a nice way. However, what astonished me was that I had believed the result without even asking for the explanation of the same. So I made a mental note to watch out for similar pitfalls in future.