The naive algorithm for factoring a semi-prime $n$ runs $\mathcal{O}(\sqrt{n})$. Let's consider the bit-wise complexity of division to be $\mathcal{O}(b^2)$. That means the bitwise complexity of naive factoring is $\mathcal{O}(b^2\sqrt{n}) \in \mathcal{O}(\sqrt{n}^2\sqrt{n}) = \mathcal{O}(n^{1.5})$.
At first glance, this still seems pretty good. I understand that when $n$ is on the order of $2^{1000}$, even this under-quadratic complexity becomes unfeasible but then no matter what the runtime, you can always find an unfeasible $n$, e.g., if the runtime was $\mathcal{O}(\log_2(n))$, we could let $n = 2^{2^{1000}}$ and just like that even log time becomes unfeasible.
Could someone explain why then we often hear that factoring is an "exponentially" hard problem? Is that true? I mean, obviously it has been hard and things like RSA depend on it but is it really exponential? Or, is the matter really of picking the big enough number $n$?
If it is exponential how can I drive that in terms of big-Oh?
Edit: I understand that $f(b)=2^b$ is exponential thus when we increase the bits, $n=2^b$ grows exponentially. However, I am finding it hard to connect the dots between value versus length based complexity analysis. When we say factoring is $\mathcal{O}(\sqrt{n})$ we have assumed that the time complexity of division is constant therefore,
$$ \sum_{i=1}^{\sqrt{n}}\mathcal{O}(1) = \mathcal{O}(1)_1 + \mathcal{O}(1)_2 + ... + \mathcal{O}(1)_{\sqrt{n}} = \mathcal{O}(\sqrt{n}). $$
Now I understand if we let go of the assumption that division is constant and plug the true complexity in the above set-up, we should get an exponential runtime. Say we take the Schoolbook long division then for "two b-digit numbers", division is $\mathcal{O}(b^2)$
$$ \sum_{i=1}^{\sqrt{n}}\mathcal{O}(b^2) = \mathcal{O}(b^2)_1 + \mathcal{O}(b^2)_2 + ... + \mathcal{O}(b^2)_{\sqrt{n}} = \mathcal{O}(b^2\sqrt{n}). $$
Since $\mathcal{O}(\log_2(n)) = \mathcal{O}(b) \in \mathcal{O}(\sqrt{n})$, we can write this as $\mathcal{O}(n\sqrt{n}) = \mathcal{O}({n^{1.5}})$.
The answers say that since $n=2^b$, $\mathcal{O}(2^{1.5b})$ is exponential and when I think about it like that, it makes sense. However, the way we write $n$ in big-Oh shouldn't really matter because we have already accounted for the non-constant division cost so,
$$ n=2^b \Rightarrow \mathcal{O}(n^{1.5}) = \mathcal{O}(2^{1.5b}) $$
This feels somewhat rigging because if you give someone $g(x)=x$ and they say oh but I'll input $2^b, 2^{b+1}, 2^{b+3}, ...$ so your function $g$ is exponential! Well, what makes the function exponential is not really the growth of the function but the input given to function is being grown exponentially!
Trial division is an exponential-time algorithm because runtime is measured as a function of the length of the input and not the value of the input bit-string. Because of this, you need $\mathcal O(2^{b/2})$ divisions to factor with trial division on a semi-prime of length $b$ bit. Clearly, this is an exponential-time algorithm. If you're still skeptical, compare this runtime to that of regular multiplication which runs in time $\mathcal O(b^2)$.
Technically, no, because you have sub-exponential time factoring algorithms like the General Number Field Sieve. However, they are still sufficiently slow that a moderate increase in keysize keeps the required effort to be infeasibly high.
Yes, that would work, but then you'd run into the situation where you need so absurdly large numbers that factoring the semiprime is faster than actually encrypting or decrypting data. Even if you picked a worse algorithm like $\mathcal O(\log_2^5(n))$, you still get into a situation where you need to pick keys that are like 1GB which is ... rather unpractical for most applications. In fact, quantum computers can factor in this kind of time and pqRSA (paper, slides) has done the math how large keys would need to be to offer reasonable security and they did arrive at about 1GB of key data.