Let's say $N$ is prime and I want to find the ${\rm ord}\_N(a)$ for some $a \in \Bbb Z^\*\_N$.

I read that there is Shank's baby step giant step (BSGS) algorithm that can serve this purpose in $\sqrt{N}$ time.

But I was thinking if we can take advantage of the fact that $N$ is prime (so the order of $\Bbb Z^\*\_N$ is simply $N - 1$), and come up with an even faster algorithm than BSGS.

My first thought was to find out the factors of $N - 1$, and check for each factor whether $a^N \equiv 1\pmod{N} $ and thereby deduce the order of $a$ (since the order of $a$ divides the order of the group). But I thought that might be as good as BSGS at best.

Does anyone have any insight into this, into how we can take advantage of the fact that $N$ is prime to compute the order of an element?

P.S.: This is my first time doing any project in number theory.