If you are given the values of m, $2^a$ mod m, and $2^b$ mod m, is there a way to find the value of $2^{ab}$ mod m? If you are given the values of m, $2^a$ mod m, and $2^b$ mod m, is there a way to find the value of $2^{ab}$ mod m?
 A: Yes.
Let us first assume that $n$ is odd. If you know $2^a \pmod n$, $2^b \pmod n$, and $n$ [but not the integers $a$ and $b$], then let $a'$ and $b'$ be any two integers that satisfy the equations $2^{a'} \pmod n =2^{a} \pmod n$ and $2^{b'} \pmod n = 2^b \pmod n$. [Now, finding such integers $a'$ and $b'$, can be done even if it means checking $2^{f}\pmod n$ for $\varphi(n)$ values of $f$. That suffices for here if I am understanding correctly; I'm not sure if there is a much faster way.] Then once $a'$ and $b'$ are found, then the integers $a$ and $b$, whatever they may be, must satisfy $a'=a + c$ and $b'=b+d$, for some integers $c$ and $d$ where $c$ and $d$ satisfy $2^c \pmod n =2^d \pmod n =1$.
Then $$2^{a'b'} \pmod n = 2^{(a+c)(b+d)}\pmod n$$
$$= 2^{ab}(2^c)^{b+d}(2^d)^{a} \pmod n= 2^{ab} \pmod n.$$
So find integers $a'$, $b'$ such that $2^{a'}\pmod n = 2^a \pmod n$, and $2^{b'}\pmod n = 2^b \pmod n$, any such $a'$, $b'$ will do. Then $2^{ab}\pmod n$ must be $2^{a'b'}\pmod n$.
For $n$ even write $n=2^gm$ where $m$ is odd and $g$ is integral.
Then given $2^a \pmod n$ and $2^b \pmod n$ one has $2^a \pmod {2^g}$ and $2^b \pmod {2^g}$; if either $2^a \pmod {2^g}$ or $2^b \pmod {2^g}$ is $1$ then either $a$ or $b$ must be $0$ so $ab$ must be $0$, so $2^{ab}\pmod{2^g}$ must also be $0$.
Otherwise $a$ and $b$ must both be positive integers [since here $2^a \pmod {2^g} \not =1$ and $2^b \pmod {2^g} \not =1$]. So if either $2^a \pmod {2^g}$ or $2^b \pmod {2^g}$ is $0$ then either $a$ or $b$ is at least $g$. And so as both $a$ and $b$ are positive integers, it follows that $ab \ge \max\{a,b\}$ and so $2^{ab} \pmod {2^g}$ must also be $0$. Otherwise the one remaining case is both $2^a \pmod {2^g}$, $2^b \pmod {2^g}$ $\not \in \{0,1\}$; from this we can recover $a$ and $b$ directly to get $ab$ and thus $2^{ab}\pmod {2^g}$.
Given $2^a \pmod n$ and $2^b \pmod n$ we can recover $2^a \pmod m$ and $2^b \pmod m$. As $m$ is odd, from the case when $n$ is odd, we can recover $2^{ab}\pmod m$.
Given $2^{ab}\pmod {2^g}$ and $2^{ab}\pmod m$ we get $2^{ab}\pmod n$ by the Chinese Remainder Thm.
