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^*$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.