What is a general way to calculate something like $2147089412^{1147068432^{647017654}}\pmod m$? It looks like modular exponentiation, but how do you reduce the highest part properly?
Note: $m$ is prime
Result:
Case 1: Where $\text{left}\equiv 0\pmod m$, the result is either $1$ ($\text{mid}=0, \text{right} > 0$) or $0$
Case 2: otherwise result is modular power(left, modular power(mid, right, $m-1$), $m$)
Thank you, Derek
Euler's generalization of Fermat's Little Theorem tells us that:
$$ a^b \equiv a^c \mod m $$
when $a$ coprime to $m$ when $b \equiv c \mod \phi(m)$, where $\phi(m)$ counts the number of residues $1 \le k \le m$ that are coprime to $m$ (aka Euler's phi function).
So you would begin by reducing the exponent modulo $\phi(m)$, before moving on to the reduction of the "outer" problem modulo $m$. Using binary exponentiation can help, of course.