3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your paragraph "Clearly, this cycle defines the exponential permutation, where in position i you can find gimodp. But this is a cycle yet. Represent is a one-line permutation and fint it's cycle:" and the equations following it are unclear and have missing symbols $\endgroup$ – kodlu Jun 25 at 21:22
  • $\begingroup$ Because your post is unclear I can hazard just a guess, but you may be looking for a generic algorithm. There are some known results about them, including a lower bound on their complexity. My understanding of going from $G$ to Sym(G) as you are doing is that this usually results in trying to find a function from a cyclif group into the group of units. But I'm not entirely confident of that. $\endgroup$ – theREALyumdub Jul 20 at 3:02
  • $\begingroup$ @kodlu: I've corrected the fact that $1$ should be the last entry on the one-line permutation of $\sigma_g$, which was the first element, and that was my mistake. Now it should be more clear, but still, note that the self-power map can have more than one cycle (moreover, I do a remark in my post about this). Excuse me, but I find overwhelming to put a complete description of the topic in this Q&A site, since the bigger the post the less reads I'd receive and that tends to make things unclear. $\endgroup$ – kub0x Jul 22 at 12:29
  • $\begingroup$ @theREALyumdub: The use of the morphism $G \to Sym(G)$ is motivated by the fact that a generator of $G$ defines a cycle generator on $Sym(G)$, so DLOG can be reduced to cycle finding. I'm interested on the complexity of cycling back to the congruence/residue we are interested on. As I say on my post there are multiple ways to do this, but all depend on cycling and I'd like to know what's the expectancy when dealing with crypto's standard numbers for a prime $p$ which are quite big. $\endgroup$ – kub0x Jul 22 at 12:33
  • $\begingroup$ @kub0x Is this part of a graduate study or did you come up with it on your own? Maybe if you provided some context I could better answer the question. $\endgroup$ – theREALyumdub Jul 22 at 20:29
1
$\begingroup$

Well this answer is a bit of a fishing game, but I have a few leads after some thought and maybe they will help.

The binary operation $$ a*b = \underbrace{a^{a^{a^{\dots}}}} $$ where the chain is repeated b times, has been studied before. If this is what you mean by "Self-Power Map," then Tetration (and the associated hyperoperations) have been studied for a while, at least around the dawn of computers as machines.

This paper has a lemma in chapter 4 that seems to concern what you are doing in the middle of your answer. Maybe it would help you to study that paper carefully, it was a top Google hit for "tetration and the discrete logarithm". Additionally, it talks about several reductions and analyzes their time complexity, so that may help you with what you are doing, and certainly answers the question of if this sort of thing has been studied before.

In my limited study of the subject, I think there's probably something interesting involved with tetration and the discrete logarithm, since exponentiation to tetration works a bit like addition to multiplication does, in that they satisfy something like Ring laws I believe. But I'm not confident or studied enough in that to say anything substantial.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.