Complexity of multiplication of two numbers If I am multiplying two numbers $m$ and $n$, where $n$ has $k$ digits and $m$ has at most $n/2$ digits, will it be considered polynomial time or exponential time in terms of $k$?
Addition (by proxy of mod): This multiplication's time will be exponential in $k$ (answering the above), yet polynomial in size of $m$. Will it be called an efficient result or not?
The maximum size of $m$ is $n/2$, and the maximum value of $n$ is $10^k-1$. It follows that the size of $m$ is exponential in $k$. Since (when $n&gt;0$) the multiplication algorithm must read the whole of $m$, and that takes time at least proportional to the size of $m$, it follows that the complexity is at least exponential in $k$.
From a theoretical standpoint, the multiplication is thus not efficient for security parameter $k$, since efficient is defined as time bounded by a polynomial of the security parameter.
If the security parameter was $n$, the algorithm could be efficient (and we could prove that by exhibiting a multiplication algorithm with cost bounded by a polynomial in $n$, which is easy: the schoolbook algorithm turns out to be enough; this is left as an exercise to the reader).
In a crypto context, we want the security parameter to be such that it makes the normal user's cost at most polynomial (i.e. efficient), but the attacker's (conjectured) cost at least super-polynomial (hopefully exponential). Thus if our algorithm is to be considered interesting, then

if that multiplication is to be performed by the user, it must be efficient and thus our parameter can't be $k$.
if that multiplication is to be performed by an attacker in an attack, but not by the legitimate user, our parameter can be $k$, and probably should be. The multiplication then can be efficient (and is, unless the multiplication algorithm is abysmally inefficient).