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

Question

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?

Answer 1

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)$.