I'm currently working on the discrete logarithm problem and the relevant attacks. I'm fine on the mathematical side of things, but when it comes to estimation of running times I run into problems. More specifically: if we take a generic square algorithm like Baby Step Giant Step for a cyclic group of size $n$, we usually arrive at $O(\sqrt{n})$ necessary operations to find a discrete logarithm. With the argument that the input of the algorithm is measured in bits, we arrive at a running time of $O(2^{b/2})$ where $b$ is the bitlength of $n$. So far so good.
But this argument does not work for say, matrix multiplication. Let's take $A,B \in Mat(n \times n, \mathbb{Z})$, so computing $A \cdot B$ obviously takes $n^2$ operations in $\mathbb{Z}$. This is, in contrast to the above, considered efficient. So why can't I argue as above and say that matrix multiplication takes exponential time as well?
On a more general level, I often encounter the argument that some algorithm requires $O(p(n)$ (p(n) being some polynomial) operations that themselves can be computed efficiently and thus the whole algorithm is considered efficient. This runs counter to my intuition I gained from looking at Pollard's Rho etc.
I know I'm probably making a stupid mistake somewhere, but I'm not seeing it at the moment.
Thanks for any help!