5
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ I don't understand this part "We first reduce $mn$ modulo the order of $a$," why are we doing this? $\endgroup$ – nullgraph Jan 23 '15 at 23:49
  • $\begingroup$ @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$. $\endgroup$ – D.W. Jan 24 '15 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.