3
$\begingroup$

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

  • 0
    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](http://mathworld.wolfram.com/LandausFunction.html) 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.2011-02-09

1 Answers 1

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

  • 0
    By "Z modulo the length of each cycle" you mean product (Z modulo c1)x(...)x(Z modulo cn) ?2011-02-09