# Computing modular exponent given order

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$.

• I don't think so, but of course you never know... – Yuval Filmus Jan 23 '15 at 18:42

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.

• I don't understand this part "We first reduce $mn$ modulo the order of $a$," why are we doing this? – nullgraph Jan 23 '15 at 23:49
• @nullgraph, because exponentiation is faster when the exponent is smaller. If the order of $a$ is $\ell$ (say), and if $mn>\ell$, then it's faster to compute $a^{mn \bmod \ell} \bmod n^2$ than to compute $a^{mn} \bmod n^2$: thus reducing $mn$ modulo the order of $a$ can help speed things up, if the order of $a$ is smaller than $mn$. – D.W. Jan 24 '15 at 1:24