Complexity of factoring integers by trial division

Question

Ok, I have a real problem with understand the complexity of this algorithm: set k=n; while k!=1{ while True{ d=k/i; if type(d)=integer{ i is a factor; break; } } } So we go through the internal while loop a maximum of root n times, we go through the outer loop a times where a is the number of primes dividing n. I am using n formed of a product of two times so surely this has root(n) operations? That seems ridiculous because I thought this was an NP hard problem!

Answer 1

The value of $n$ considered in this problem when evaluating its time complexity is not the number itself, but rather the number of bits (equivalently, digits) the number has. When measured in that metric, the algorithm takes exponential time.