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?