How hard is recognizing a permutation that is a square for the shift product?
It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&amp;2&amp;\ldots&amp;n\\ (k+1)\bmod n&amp;(k+2)\bmod n&amp;\ldots&amp;(k+n)\bmod n\end{matrix}  \right)$$ be the shift permutation. Then the shift of $\tau$ is just $\sigma = \tau \circ \rho_k$, and the shift product of $\tau$ is $\tau \circ \rho_k \circ \tau$. But $$\pi = \tau \circ \rho_k \circ \tau \iff \rho_k \circ \pi = (\rho_k \circ \tau)^2$$

Given $\pi$ you can find $\rho_k \circ \pi$ in linear time, and then you just need to see whether it has a square root, which can also be done in linear time.