3

In a group of permutations of $n$ elements, there are two permutations $P_1$ and $P_2$ such that $P_2=P_1^e$. $P_1$ and $P_2$ have the same order $o$: $P_1^o = P_2^o$. How can I find $e$?

$n$, $P_1, P_2$ and $o$ are known, $e$ is not known. Problem is to find $e$.

  • How big are n and o? If n is pretty small (<30, say), you can brute force it by just trying out all possible e's less than Landau's function g(n). This is absolute overkill of course, but I'm still thinking of doing something slightly more clever with the cycle decomposition and orbits etcetera. – yatima2975 Feb 09 '11 at 12:33

1 Answers1

3

Knowing the cycle decomposition of $P_1$ is useful :

For a $k$-cycle $(a_0, a_2, \ldots a_{k-1})$ of $P_1$, $P_2(a_0)$ will be an element of that cycle, $a_p$ for some $p \in \{0 \ldots k-1\}$. Since $P_1^e(a_0) = a_{e \mod k}$, this information is equivalent to $e \mod k = p$.

Gather those congruences from enough cycles of $P_1$ (so that the least common multiple of the cycle lengths is $o$), and the system you obtain will give you the unique solution of $e \mod o$.

mercio
  • 50,180
  • I will try this. Is it possible to find a homomorphism from group of permutations, to, for example, integers modulo $o$, so that the problem is reduced to discrete log. in integer field? –  Feb 09 '11 at 14:42
  • @hnn : I guess that by considering the cycle decomposition, you get homomorphisms from the cyclic subgroup generated by p1 to Z modulo the length of each cycle. You don't need discrete log, the Chinese Remainder Theorem suffices. – yatima2975 Feb 09 '11 at 15:29
  • By "Z modulo the length of each cycle" you mean product (Z modulo c1)x(...)x(Z modulo cn) ? –  Feb 09 '11 at 15:48