# How difficult is finding $i$ for sequence $s_{i} = g^{s_{i-1}} \mod P$ with $s_0 = g$ for given value $v\in [1,P-1]$

Assuming we found a constant $$g$$ and a prime $$P$$ which is able to produce all values from $$1$$ to $$P-1$$ with it's sequence $$s_{i} = g^{s_{i-1}} \mod P$$ $$s_0 = g$$

How many steps are needed to compute $$i$$ for a given value $$v$$ ($$=s_i$$) with known $$g,P$$?
Can it be faster than $$i$$ steps?

toy example:

With $$P=5, g=3$$ the sequence would be $$\begin{split} &[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 for $$P=23, g=20$$ the 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]$$ or $$P=59, g=39$$

side-questions:

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

• Is it also possible to compute $$s_{i-1}$$ out of $$s_{i}$$ ? Or is it similar to the DLP?

• Has this kind of sequence already some name?

This sequence is the sequence of states of the Blum-Micali algorithm with seed $$g$$.
The question of whether $$s_i$$ can be computed in fewer than $$i$$ steps is a question as to whether the generator can be "giant stepped". To my knowledge we do not know of a way to do this.
Computing $$s_{i-1}$$ from $$s_i$$ is precisely equivalent to the discrete logarithm problem and is used to demonstrate the forward security of the generator.