Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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
    
@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 9 '11 at 15:29
    
By "Z modulo the length of each cycle" you mean product (Z modulo c1)x(...)x(Z modulo cn) ? –  user6823 Feb 9 '11 at 15:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.