Introduction
I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the symmetric group. The set of symbols is composed by the elements of $G$. In my case, $X=U$, where $U$ are the units of $Z_p^*$, so $\vert G \vert = \vert U \vert = p-1$.
First, if we analyze the group action induced by multiplication of elements $a,b\in G$ we observe that every $a$ has a $b$ that reaches $c$, so it's transitive.
Second, there does not exist an $a$ that fixes $b$. It's only acceptable when $a$ is the identity element: $ab= b \iff a= e_G$. Satisfies the Free or Fixed Point action, thus it's also faithful.
Self-power map explained
Then define $\phi : G \to Sym(G)$ as the map that sends elements from $G$ (units) to elements (permutations) in the permutation group $P$ which is isomorphic to $G$.
If we finally select $G=Z_p^*$, let $g$ be a generator in $G$ that we want to represent as permutation $\sigma_g \in P$. Then we must construct the permutation by multiplying $g$ to all the units in $G$.
$\forall 1\leq x \leq p-1 \quad \sigma_g = \phi_g(x) = g\cdot x \pmod p$
As $g$ is a generator $\sigma_g$ will have an unique cycle comprised of $p-1$ elements. To represent $\sigma_g$ in cycle notation, the following expression can be useful:
$\sigma_g = (1,\phi_g(1),\phi_g(\phi_g(1)),\cdots,\phi_g(1)^{p-1}) = (g^0,g^1,g^2, \cdots, g^{p-1})$
Clearly, this cycle defines the exponential permutation, where in position $i$ you can find $g^i \mod p$. The self power map $\sigma_g^*$ is given finding the cycle of the representation of $\sigma_g$ as a one-line permutation where $g^0=g^{p-1}=1$ is the last element in the one line permutation.
$\sigma_g^* = g^1,g^2,\cdots, g^{p-1} = g,g^2,\cdots,1 = (1,g,g^g,g^{g^{\cdots{g}}},\cdots)$
We can construct $\sigma_g^*$ directly if we define $\alpha_g : G \to Sym(G)$ where $\alpha_g(x) = g^x \pmod p$, so the self-power map of $g$ that's $\sigma_g^*$ is defined as follows:
$\sigma_g^* = (1, \alpha_g(1), \alpha_g(\alpha_g(1)), \cdots) = (1,g^1, g^g \pmod p, g^{g^g \pmod p}\pmod p, \cdots)$
The cycle notation of the self-power map $\sigma_g^*$ of a generator $<g> = G$ normally has more than one cycle, being fixed points and transpositions interesting topics that I've found, specially when dealing with safe primes. It is important to remark that every exponent on i.e $g^{g^{g}}$ is reduced modulo $p$ as shown in the cycle construction of $\sigma_g^*$.
(NOTE: There's a strong symmetry between units and exponents when you view the inverse of $\sigma_g^*$ as a 2-line matrix representation).
Conclusion
We have found the self-power map of $g$, however, the last definition is very vague, as $\sigma_g^*$ can have more than one cycle.. In my study, I made multiple C++ programs to measure which cycle types are encountered. Also my record was solving Dlog with a 60 bit random prime.
To implement such a solver, I used the fact that every generator is generated by other generator if the exponent is coprime to the group's order, so if we can't find $x$ in the self-power map of $g$ then we can try to find $x$ in the self-power map of other generator $h$.
There is also another method, relying on the multiplicative inverse of the exponent $x$. Let $g^x\equiv h\pmod p$, then if we cannot find $g$ in the self power map of $h$, if $x$ is originally coprime, $h$ is a generator, so select a new generator $s$, which is $h^y \equiv g^{xy} \pmod p$. Try to cycle until recover $g$ from the sequence, this yields an $w$ s.t $yxw \equiv 1 \pmod{p-1}$ so $s^w \equiv g^{yxw} \equiv g \pmod p$. These methods are easily translated to multi-threading environments, select a limit so the program stop the cycling and selects a new generator.
But since the self power map is a cyclic structure, that tells me that the average cycle length of the cycle where $x$ or $w$ lies is big enough when selecting the self power map of a new generator. And the average cycle length of a cycle escalates rapidly when the group's order is bigger.
Question: Has the self power map been studied for estimating the average complexity for solving a DLOG instance?
