Modular Exponentiation by Squaring and large exponents

Question

I have been thinking about the exponentiation by squaring algorithm. The algorithm obviously takes $\mathcal{O}({\log(n) \cdot \log^2(m)})$ time for the computation of some $x^n \pmod m$.

The Handbook of Applied Cryptography assumes for the exponent $n$ that $n < m$ to give a runtime of $\mathcal{O}(\log^3(m))$.

So how can we handle exponents bigger than $m$? We could use the base version of the first paragraph and get $\mathcal{O}({\log(n) \cdot \log^2(m)})$ runtime.

But would it be an option to first reduce the exponent $n$ by replacing it with the residue of $\frac{n}{m-1}?$ This is possible due to elementary group theory and should take $\mathcal{O}(\log(\lfloor \frac{n}{m-1} \rfloor) \cdot \log(m-1))$ bit operations. So in total this would mean a runtime of $\mathcal{O}(\log(\lfloor\frac{n}{m-1}\rfloor) \cdot \log(m-1)) + \mathcal{O}(\log^3(m)) = \mathcal{O}(\log(\lfloor\frac{n}{m-1}\rfloor) \cdot \log(m-1) + \log^3(m))$.

Can this runtime be seen as an improvement ?

Answer 1

Exponents bigger than $m$ do not occur in practice, as $x^n$ is cylic with period $\phi(m) < m$. Moreover, in crypto (like RSA or DH) we always assured of $n < m$ when working mod $m$, just by how the systems work. So your concern for runtimes when $n>m$ is unnecessary.

Answer 2

You can only do this if you know that $m$ is prime (which is not the case if, for instance, $m$ is the exponent in a public RSA key). In general, you have to reduce $n$ modulo $\varphi(m)$, which is equal to $m-1$ only if $m$ is prime.