How to efficiently find a prime number $x$ raised to the power $x$ $k$ times modulo $m$?

Question

How to efficiently find a prime number $x$ raised to the power $x$ $k$ times modulo $m$?

In other words, how to find $ \underbrace{x^{x^{...^{x}}}}_k \mod m$, where $x$ is prime?

Answer 1

The operation you are applying is tetration, sometimes written ${}^kx$.

Assuming that you know the value of $m$, you can reduce the work of computing this value by successively reducing the modulus of higher exponent levels by correspondingly deeper nesting of the Carmichael function $\lambda$ (which is a tighter bound on exponential order than Euler's totient $\phi$) applied to the modulus $m$. There will be a value $L$ - often relatively small - where for any $k>L$ the value is the same.

$${}^kx \bmod m \equiv x^{\large (^{k-1}x \bmod \lambda(m))}\bmod m \\ \equiv x^{\large x^{\large (^{k-2}x \bmod \lambda(\lambda(m)))} \bmod \lambda(m)}\bmod m \quad \text{etc.}$$

To find a general value for $L$ for given $m$ across all $x$ we can look at the iterated Carmichael function value. For example for $m=4567$:

$m=4567$
$\lambda(m) = 4566$ since $m$ is prime.
$\lambda^2(m) = \lambda(4566) = {\rm lcm}(\lambda(2), \lambda(3), \lambda(761)) ={\rm lcm}(1,2,760) = 760$
$\lambda^3(m) = \lambda(760) = {\rm lcm}(\lambda(8), \lambda(5), \lambda(19)) ={\rm lcm}(2,4,18) = 36$
$\lambda^4(m) = \lambda(36) = {\rm lcm}(\lambda(4), \lambda(9)) ={\rm lcm}(2,6) = 6$
$\lambda^5(m) = \lambda(6) = {\rm lcm}(\lambda(2), \lambda(3)) ={\rm lcm}(1,2) = 2$
$\lambda^6(m) = \lambda(2) = 1$

The last step says it doesn't matter what the exponent is (exponentiation does not affect parity) - $x^\text{any} \equiv x \bmod 2$. Thus we find $L=6$ for $m=4567$

Let's see how this works to evaluate $^{123}89\bmod 4567$.

$$\begin{align} \bmod 4567:\qquad {}^{123}89 &\equiv 89^{\large^{122}89 \bmod 4566} \\ \bmod 4566:\qquad {}^{122}89 &\equiv 89^{\large^{121}89 \bmod 760} \\ \bmod 760:\qquad {}^{121}89 &\equiv 89^{\large^{120}89 \bmod 36} \\ \bmod 36:\qquad {}^{120}89 &\equiv 89^{\large^{119}89 \bmod 6} \\ \bmod 6:\qquad {}^{119}89 &\equiv 89^{\large^{118}89 \bmod 2} \\ \bmod 2:\qquad {}^{118}89 &\equiv 89^{\text{anything}} \equiv 89\equiv 1\\ \bmod 6:\qquad {}^{119}89 &\equiv 89^{1} \equiv 5\\ \bmod 36:\qquad {}^{120}89 &\equiv 89^{5} \equiv 17^{5} \equiv 17\\ \bmod 760:\qquad {}^{121}89 &\equiv 89^{17} \equiv 649 \qquad \text{(exponentiation by squaring ...}\\ \bmod 4566:\qquad {}^{122}89 &\equiv 89^{649} \equiv 3707\qquad \text{... used for these ...}\\ \bmod 4567:\qquad {}^{123}89 &\equiv 89^{3707} \equiv 889 \qquad \text{... last three results)}\\\ \end{align}$$

Answer 2

There is a solution $\mathcal{O}(k \log{n})$. Use exponentiation by squaring to compute $a = x^x \pmod m$. Then you are left with expression $\underbrace{x^{x^{...^{a}}}}_{k-1}$. Repeat the process until you get to single number.