# What can be said about the self-power map on groups based on DLP?

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.

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

To represent the permutation in cycle notation, the following notation can be useful:

$$\sigma_g = (1,\phi_g(1),\cdots,\phi_g(1)^{p-1}) = (g^0, \cdots, g^{p-1})$$

Clearly, this cycle defines the exponential permutation, where in position $$i$$ you can find $$g^i \mod p$$. But this is a cycle yet. Represent is a one-line permutation and fint it's cycle:

$$\sigma_g^* = 1,\cdots, \phi_g(1)^{p-1} = (1,\phi_g(1)^g,\phi_g(\phi_g(1)^g)^g\cdots) = (g^0,g^1,g^g,g^{g^g}\cdots ...)$$

(NOTE: There's a strong symmetry between units and exponents when you view the inverse of $$\sigma_g^*$$ as a 2-line matrix representation).

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.

What are other limitations and advantages of using the self power map of distinct generators for solving DLP in $$Z_p^*$$.