How can I test if an element g is a generator of a group G with a known number of elements, N? Let's say $G$ has $1000$ elements. Without looping through each $g^m$, how can I show that $g$ is a generator? I've deduced that I must prove that the order of $g = N$, or in this case $1000$, but I'm not sure how to go about that. Any help is appreciated. Thanks!
 A: If the prime factors of $|G| = N$ are known, then one can test $g^m \neq e$ (where $e$ means the identity element of the group $G$) for a relatively small subset of the possible exponents.  Namely, one want to show that $g^m \neq e$ for each $m = N/p$ where $p$ runs through the prime divisors of $N$.
Note that we automatically know $g^N = e$.  So the goal is to prove that no proper divisor $D$ of $N$ will also serve to achieve $g^D = e$.  This conclusion follows from what we would show above, for if $D$ were a proper divisor of $N$, then some prime divisor of $N$ has more repeated factors in $N$ than in $D$.  Let $p$ be such a prime divisor of $N$.  According to the above criterion, $D$ divides $N/p$.  But if $g^{N/p} \neq e$, it cannot be the case that $g^D = e$ (because $D$ divides $N/p$).
A: The general theory has been given in another answer but IMHO this is one of those results where a specific example makes the theory very much easier to understand.
So, suppose you have an element $g$ of a group $G$, where $|G|=1000$.  You want to know whether or not $g$ has order $1000$.
First of all, you know that the order of $g$ is a factor of $|G|$, and so the possible values for the order are
$$1000,\,500,\,250,\,200,\,125,\,100,\,50,\,40,\,25,\,20,\,10,\,8,\,5,\,4,\,2,\,1\,.$$
We want to rule out the possibilities
$$500,\,250,\,200,\,125,\,100,\,50,\,40,\,25,\,20,\,10,\,8,\,5,\,4,\,2,\,1\,.$$
So, suppose that we have checked that $500$ doesn't work, that is, we have checked $g^{500}\ne e$.  (We can think later about how to do this efficiently, for now let's just say we've done it.)  The point is that we now do not need to check that $g^{250}\ne e$; for if $g^{250}$ were to equal $e$ then we would have $g^{500}=e^2=e$; and we have already checked that this is not true.  In the same way, we don't need to check $125,100,50,25,20,10,5,4,2,1$ which leaves us with
$$200,\,40,\,8\,.$$
So, check that $g^{200}\ne e$; then for the same reasons as above, we don't need to check $40$ or $8$.
So what it comes down to is: $g$ is a generator of $G$ if and only if
$$g^{500}\ne e\quad\hbox{and}\quad g^{200}\ne e\ .$$
If you think carefully you should see how this gives the general rule as stated in other answers: $g$ is a generator of a group of $n$ elements if for every prime factor $p$ of $n$ we have $g^{n/p}\ne e$.
Doing the problem the "obvious" way, we would have $999$ things to check: as it is, only two!
You can do the necessary computations by repeated squaring and related techniques: in this case you could successively compute
$$\eqalign{g^2&=(g)(g)\cr
  g^4&=(g^2)^2\cr
  g^5&=(g^4)g\cr
  g^{10}&=(g^5)^2\cr
  g^{20}&=(g^{10})^2\cr
  g^{40}&=(g^{20})^2\cr
  g^{50}&=(g^{40})g^{10}\cr
  g^{100}&=(g^{50})^2\cr
  g^{200}&=(g^{100})^2\cr
  g^{400}&=(g^{200})^2\cr
  g^{500}&=(g^{400})g^{100}\ ,\cr}$$
a total of just $11$ calculations to show that $g$ is a generator.
