3

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

Kenta S
  • 16,151
  • 15
  • 26
  • 53
Derek Illchuk
  • 133

1 Answers1

3

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.

hardmath
  • 37,015
  • 3
    In the non-coprime case, additionally use the Chinese Remainder Thorem, and usually the exponent of any commmon prime factor of $a$ and $m$ will occur in $a^b$ in trivially much higher power than in $m$. – Hagen von Eitzen Nov 21 '14 at 14:33
  • 1
    @HagenvonEitzen: Excellent point. Since we don't know $m$, I didn't think to press the analysis further. However $\phi(m)$ will certainly be even (in any nontrivial calculation), so reducing the nested exponent mod $\phi(m)$ will necessarily involve separating out the GCD$(1147068432,\phi(m))$ as you outline (and quite possibly $m$ will likewise have common factors with the base $2147089412$). – hardmath Nov 21 '14 at 14:45