# Hyperexponentiation modulo a prime

Let $a\uparrow^{n} b$ denote the indexed version of Knuth's up-arrow notation ($a \uparrow\uparrow \dots \uparrow b$ with $n$ arrows), with $a, b, n$ positive integers.

Is there a generalized algorithm to compute $a\uparrow^{n} b$ modulo a prime efficiently? How does the complexity of such an algorithm depend on $n$? What if we restrict $a$ and $b$ to also be prime, or if we remove the requirement for $p$ to be prime?

Consider the problem of calculating $a^{a^b} \bmod p$. What we do here is calculate $x = a^b \bmod (p-1)$, which is the exponent we need to do $a^x \bmod p$, which is our answer. This is due to Fermat's Little Theorem, which states that for prime $p$:
$a^{p-1} \equiv 1 \bmod p$