Time Complexity of RSA Trial Division

Question

I'm having trouble understanding how time complexity of trial division is exponential.

If it takes $\sqrt n$ tries to factor $n$ in the worst case scenario then time complexity is $\mathcal{O}(\sqrt n)$, which I thought would mean that the number of operations grows slower than the increase in the number of inputs. So how would that be inefficient if polynomial time is considered efficient?

It makes sense that trial division would be inefficient but I can't seem to wrap my head around it in terms of time complexity. I also saw somewhere that the time complexity is actually $\mathcal{O}({e^n \over 2})$ but I'm not sure how they arrived at that.

Answer 1

Time complexity is measured as the time taken in function of the size of the input. The reason for this is that it can be used to describe the complexity of any algorithm, not just algorithms operating on numbers, and the input size is always well defined for any type of input.

A key of size $n$ bits can be a number up to $2^n$, so $\sqrt{2^n} = (\sqrt{2})^n$ divisions are required, an exponential function in $n$.