Finding order of an element in a group denoted by a prime number 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.
 A: Your method is on the right track. Yes, having the prime factors of $N-1$, if $N$ is prime, does allow one to compute the order of $a$ much more quickly than BSGS. Specifically it takes $O(\log^3 N)$ time (whereas BSGS takes $O(\sqrt{N})$):
Assume that $N-1=\prod_{i} p_i^{b_i}$ is the factorization of $N-1$ into distinct prime powers. Then note that $\operatorname{ord}_N(a)|N-1$, so we need to figure out which $p_i$ (and to what power) divide $N-1$. Luckily for us:
$a^{\frac{N-1}{p_i}}\not\equiv 1\mod N\Leftrightarrow p_i^{b_i}|\operatorname{ord}_N(a)$.
Note that it is important for this biconditionality for us to use the exponent $\frac{N-1}{p_i}$, not just $p_i$. If $a^{\frac{N-1}{p_i}}\equiv 1\mod N$, then (inclusively) until $n=b_i$ we can successively calculate:
$a^{\frac{N-1}{p_i^n}}\not\equiv 1\mod N, \text{ and } a^{\frac{N-1}{p_i^{n-1}}}\equiv 1\mod N \Leftrightarrow p_i^{b_i-n+1}|\operatorname{ord}_N(a)$.
Since there are at most $O(\log N)$ (number of prime factors of $N-1$) checks, and each check is a modular (and binary) exponentiation in $\mathbb{Z}/N\mathbb{Z}$ ($O(\log^2 N)$ time), the total complexity is $O(\log^3 N)$.
Warning: Actually factoring $N-1$ however is time complexity $O(e^{(1+o(1))\sqrt{\ln(N)\ln\ln(N)}})$, which is still better than $O(\sqrt{N})$, but much worse than $O(\log ^3 N)$ making $O(e^{(1+o(1))\sqrt{\ln(N)\ln\ln(N)}})$ be the total runtime. However, if you already know the factorization of $N-1$, then it runs in $O(\log^3 N)$ time.

Edit: to directly address your other question, we are taking advantage of $N$ being prime precisely via something you already mentioned: we know the group order is $N-1$, which serves as the starting point for finding the order of $a$, as seen above. If we already know the factorization of $N-1$, we don't have to waste time factoring $N$ to find the group order.
Edit 2 for fun: Shor's quantum period-finding algorithm can find the order of any element (regardless of known factorization of $N-1$) in $O(\log^3 N)$ steps on a quantum computer
A: I think it's called the strong form, but by little Fermat,  $a^p\equiv a\pmod p$, so we are not, since $N=p$, going to have $a^N\equiv 1\pmod N$, unless $a=1$.
Maybe just a typo on your part,  you could have meant $a^{\color{blue}{m}}\equiv 1\pmod N$ for each $m$ such that $m\mid N-1$.
Remember your talking about the elements' order in $\Bbb Z_p^*$.
