finding a discrete log analogous for tetration in finite fields

50 Views Asked by At

Tetration is defined as \begin{align} T(a, n) &= \underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_{n\space times} \\ T(a, 0) &= 1 \end{align}

Now, I was wondering if there is an efficient way to solve for n in $T(a,n)=b \mod p$ for given $a,b,p$. This problem is analogous to discrete logarithm, but for tetrations. My observations are as follows(please correct me if I am wrong).

In a finite field, tetration will either converge to a fixed number after certain iterations (case 1), or it will loop onto itself giving us a subset of the field elements (case 2). So, there will either be infinite solutions or no solution.

For case 2, By Fermat's little theorem, $a^a = a^{(a\mod phi(p))} \mod p$, where I take phi as the carmichael function, because of its tighter bound than Euler's totient. Similarly, the second exponentiation will be done modulo $phi(phi(p))$ and so on. Now, $phi(phi(\cdots(p))$ will eventually reach $1$, at which point, we would've encountered all possible outputs.

Now, is there any mathematical way to find such $n$? Currently, the only way I know is to repeatedly exponentiate till I get the number, or find a repeating output to get no solution.

(I would be thankful if somebody could also provide some literature on this topic)