The task is to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and 1 multiplication by $y$. The number $x$ is odd, $d\geq3$.

I've found the proof that $x^{2^k} \equiv 1 (\bmod 2^{k+2})$ when $x$ is odd. So we can use $(y \& (2^{d-2}-1))= y \bmod 2^{d-2}$ (the operation $\&$ is a bitwise "and") as an exponation instead of $y$. And obviosly we can use $(x \& (2^d-1))= x \bmod 2^d$ as a base instead of $x$.

The Euler's theorem doesn't help here, because it states that $x^{2^{k-1}} \equiv 1 (\bmod 2^{k})$, that is weaker than the statement mentioned above.



You must log in to answer this question.