Suppose there are $2$ permutations given by $p$ and $q$.
I need to check whether $p$ belongs to the group generated by $q$, and if so, it's representation in a power of $q$.
In other words, I've been given $p$ and $q$, I need to check whether $\exists i \in \{ 0,...,|q|-1 \} \text{ such that } p = q^i$
I know that if $m = \gcd(i, |q|)$, then $|q^i| = \frac{|q|}{m}$.
Now, say that such an $i$ exists. Then,
$$ |p| = \frac{|q|}{\gcd(i, |q|)} \Rightarrow \gcd(i, |q|) = \frac{|q|}{|p|} $$
Thus, a necessary condition for such an $i$ to exist is: $|p|$ divides $|q|$
Say that this holds, and $\frac{|q|}{|p|} = r$, where r is an integer.
Then we just have to solve $\gcd(i, |q|) = r$ for $ i \in \{ 0,...,|q|-1 \}$.
Can this be done? If not manually, then by some efficient algorithm?
(Note: Just looping over all values of $i$ is not efficient as $i$ may be very large)
Edit:
Another way I can think of solving this is by writing both $p$ and $q$ as product of disjoint cycles:
$$ p = c_1c_2\ldots c_k \text{ and } q = d_1d_2\ldots d_l $$
And thus, as disjoint cycles commute:
$$ p^i = c_1^ic_2^i\ldots c_k^i $$
How to proceed after this?
As you suggest, start by decomposing the permutations into cycles $p=c_1\ldots c_k$, $q=d_1\ldots d_l$.
If $p$ is a power of $q$, then the points in each cycle $c_i$ must be unions of points in a subset of the cycles of $q$, all of the same length. You can check that in time $O(n)$, and also make a record of which cycles of $p$ are involved in each $d_i$.
So now we have $p = e_1 \ldots e_l$, where each $e_i$ is a union of some of the cycles of $p$ of the same length, and the points in $e_i$ are the same as those in $d_i$.
Now, for each $d_i$ in turn, check whether $e_i$ is a power $d_i^{m_i}$ of $d_i$, where we can take $0 \le m_i < |d_i|$. You can quickly identify $m_i$ (assuming it exists) by looking at the image under $e_i$ of any point in $d_i$ and then locating the corresponding point in $d_i$.
For example, if $d_i = (3,5,11,4,9,8,12,6)$ and $e_i$ maps $3$ to $8$, then $m_i = 5$. Now check whether we really do have $e_i = d_i^{m_1}$. In the example, we check that $e_i$ maps 5 to 12, 11 to 6, 4 to 3, etc.
All of this for all of the cycles can be done in time $O(n)$.
If any of the tests so far have failed then $p$ is not a power of $q$. Otherwise, we have found $m_i$ with $0 \le m_i < |d_i|$ such that $e_i = d_i^{m_1}$ for each $i$.
Now, finally we have to solve the system of congruences $m \equiv m_i \bmod |d_i|$ for $1 \le i \le l$. If there is a solution $m$, then $q^m = p$, and otherwise $p$ is not a power of $q$. This can be done using the Chinese Remainder Theorem.
I should know the complexity of solving congruence equations, but I cannot remember it. I think it is low degree polynomial in $\log {\rm lcm}(|d_1|,\ldots,|d_k|)$ and, as was mentioned earler, this least common multiple is $O(e^{\sqrt{n}})$. So it will be low degree polynomial in $n$.