# Equation on permutations

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 9 '11 at 12:33

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$.
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? – user6823 Feb 9 '11 at 14:42