-1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.