How to check if two sequences of setoid members are mutual rotations?
It might depend on $n$. If $n$ is prime then the following algorithm works in linear time. Compare $a_1$ to all elements in $a$ and to all elements in $b$. The resulting $a_1$ patterns must be congruent, and if they are, then they are congruent uniquely. Once you know the shift, it is easy to check whether the original sequences are congruent.

When $n$ is composite then you might run into trouble since there are several shifts possible. Still, it seems possible but messy to get a linear or quasilinear time algorithm.