# How difficult is finding $i$ in tetration $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$ for $v\in[1,P-1]$

EDIT: I messed up something (see comments at answer). This question contains some false statements EditEnd.

For tetration modulo prime $$P$$ $$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$$ with suitable $$g,P$$ so that $$|\{^jg \mod P\}| = P-1 \text{ }\text{ , or }\text{ } v\in[1,P-1]$$

Given $$P,g,v$$, how difficult is finding the related $$i$$?
Harder than DLP? (finding $$i$$ for $$g^i \equiv v \mod P$$)
I'm interested at the number of steps ($$O$$ notation ).
To compare it with the normal DLP problem we assume one step - so $$g^c$$ and $$g\cdot c$$ with constant $$c$$ does need the same time.

To get all values $$v$$ the variables $$g,P$$ need some special property: $$^{P-1}g \equiv 1 \mod P$$ $$\forall j \in [1,N-2]: \text{ }^{j}g \not\equiv 1 \mod P$$ We also assume $$g,P$$ are picked as safe as possible (like $$P = 2q+1$$, with $$q$$ prime (also better here?))

toy example:

With $$P=5, g=3$$ the sequence would be $$\begin{split} &[3, 3^3, 3^{3^3}, 3^{3^{3^3}}] \mod 5 \\ \equiv&[3, 3^3\equiv 2, 3^{2} \equiv 4, 3^{4} \equiv 1] \mod 5 \\ \equiv&[3, 2, 4, 1] \mod 5 \end{split}$$

Or $$P=23, g=20$$ or $$P=59, g=39$$

main-question:

• How many steps needed to compute $$i$$ out of given $$v,g,P$$?

side-questions:

• How many steps needed to compute the result $$v$$ for given $$i,g,P$$? Faster than $$O(i)$$?

• If a value $$v_i$$ for a certain $$i$$ is known the next value $$v_{i+1}$$ can be computed with $$^{i+1}g \equiv g^{v_{i}} \equiv v_{i+1} \mod P$$ Is it also possible to compute $$v_{i-1}$$ out of $$v_{i}$$ ? Or is it similar to the DLP?

• Is there even an efficient way to compute it in the forward direction, meaning compute the map $i \mapsto {}^ig$? This is not clear to me, and is a desirable part of (standard) exponentiation.
– Mark
Feb 25, 2022 at 4:16
• @Mark I don't know either. I meant this with the first 'side-question' if i understood you correctly. However I'm looking for something which is locally ($i \pm 1$) easy to compute but hard for a certain index $i$. It could serve as random permutation. If $i \mapsto ^ig$ is easy to compute ($O(1)$) it would only take $O(\sqrt{P})$ steps to find $i$ for given $v$ (like for DLP) or even less. I would like a $P$ as small as possible with same security. Feb 25, 2022 at 5:59

For a given $$g\in\mathbb N$$ there will be at most $$O(\log P)$$ distinct titrations modulo $$P$$. Thus there are only a small number of examples where $$|\{{}^jg\mod P\}|=P-1$$. In other cases, if the tetration modulo $$P$$ can be effectively computed, then the problem is easy to solve by exhaustion.

To understand the small size of $$|\{{}^jg\mod P\}|$$, note that for if $$P$$ does not divide $$g$$ then for $$i\ge 1$$ by Euler's theorem $${}^ig\equiv g^{{}^{i-1}g}\equiv g^{{}^{i-1}g\mod{\phi(P)}}\pmod P.$$ We now note that $${}^{i-1}g\mod{\phi(P)}$$ takes on at most $$\phi(\phi(P))$$ different values and the these cycle with period at most $$\phi(\phi(P))$$. It follows that for $$i\ge 1$$, $${}^ig\mod P$$ takes on a most $$\phi(\phi(P))$$ values. Iterating the argument write $$\phi_k(x)$$ for the $$k$$-iterated totient function $$\phi_1(x)=\phi(x)$$, $$\phi_k(x)=\phi(\phi_{k-1}(x))$$. We then see that for $$i\ge k$$, $${}^{i-k}g\mod{\phi_k(P)}$$ takes on at most $$\phi_{k+1}(P)$$ different values and hence for $$i\ge k$$, $${}^ig\mod P$$ takes on a most $$\phi_{k+1}(P)$$ values. Theres some elision of here about details when $$g$$ has a factor in common with $$\phi_k(P)$$.

Now, we note that for all $$n>2$$ we have $$2|\phi(n)$$ and that for all $$m$$ we have $$\phi(2m)\le m/2$$. It follows that $$\phi_k(P)\le P/2^{k-1}$$. Also because $$\phi_k(P)$$ is an integer, for $$k>\lceil\log_2P\rceil+1$$ we have $$\phi_k(P)=1$$. Thus if we write $$L=\lceil\log_2P\rceil+1$$ we have for $$i,j>L$$ $${}^ig\equiv{}^jg\pmod P$$.

Computing the tetrations can be done by square-and-multiply methods provided that one can compute all of the $$\phi_k(P)$$.

• Sorry I forgot some mod operator (changed it): I meant $|\{^jg \mod P\}| = P-1$. So $g$ and $P$ are picked in that way that we get $P-1$ different values ($\in \{1,..,P-1\}$) for $j \in [1,P-1]$ Feb 25, 2022 at 6:11
• I understand this and by the argument above this restricts $P$ to be 2, 3 or 5. Feb 25, 2022 at 6:17
• Why $P$ can only be $2,3,5$? E.g. the values $P=23$ with $g=20$ do work fine. They can produce all values from $1$ to $22$. The related values would be: $[20,18,2,9,5,10,8,6,16,13,14,4,12,3,19,17,7,21,15,11,22,1]$ \ \ Also why is it $g^{^{i-1}g \mod \phi(P)}$ and not $g^{^{i-1}g \mod P}$? Feb 25, 2022 at 6:55
• Ah I see. You're not computing ${}^ig\mod P$, but the $i$th iteration of the map $x\mapsto g^x\mod P$ with starting value $g$. These are not the same thing (e.g. $3^{3^3}=3^{27}\equiv 2\pmod 5$). Feb 25, 2022 at 7:08
• Oh, thank you for that hint! I thought they are equal. It worked out for the tested example. So I'm actually looking for an answer of that $i$th iteration. Feb 25, 2022 at 7:28