I want to compute $g^{mn}$ mod $n^2$ where $n=pq$ and I know that $g$ has order $kn$ mod $n^2$ where $m<k$. Is there any clever way of doing it utilizing the order? I have tried other methods of computing $g^{mn}$ directly.My question stems from an implementation of the Paillier cryptosystem that I'm working on. Right now, I'm following the original paper Public-key cryptosystems based on composite degree residuosity classes, scheme 3 with the recommendation of generating $g$ using DSA. I have looked at different methods of computing modular exponentiation directly such as square and multiply, k-ary, window sliding, etc.  I want an algorithm for computing $g^{mn} \bmod n^2$ that does not rely upon knowledge of the factorization of $n$.
Computing modular exponent given order
algorithms;cryptography;modular arithmetic
There's a small chance you might be able to get a speed-up by using properties of arithmetic modulo $n^2$, depending on how $g$ was chosen.Suppose $g=a(1+bn)$.  Then note that, by the binomial theorem,$$g^x = a^x (1+bn)^x = a^x \sum_i {x \choose i} (bn)^i  = a^x (1 + bx n + n^2 \times \text{stuff})$$so we see that$$g^x = a^x (1 + bx n) \pmod{n^2}$$Thus if you can compute $a^x \bmod n^2$ efficiently, you can compute $g^x \bmod n^2$ with just a tiny bit more work.  Here you want to take $x=mn$.  The simplification is that now $g$ can always be expressed in the form $g=a(1+bn)$ where $0 \le a < n$.What can we say about $a$?  Well, for one thing we know that $g^{kn}=1 \pmod{n^2}$, so it follows that $a^{kn}=1 \pmod{n^2}$.  Thus, the order of $a$ modulo $n^2$ has to be a divisor of $kn$.If the order of $a$ is exactly $kn$, we haven't gotten anywhere.But if the order of $a$ is a strict divisor of $kn$, we can get some speedup.  We first reduce $mn$ modulo the order of $a$, then compute $a^{mn} \bmod n^2$, and finally use the relationship above to get the value of $g^{mn} \bmod n^2$.  (For instance, if you get lucky, it is possible that the order of $a$ might be $k$, and then you'll get a non-trivial speedup.)Whether this yields a speedup in practice will depend on the value of $g$ and how $g$ was chosen; since that wasn't specified in your question, it's not possible to evaluate whether this is likely to help in practice, but it might.