proving that an element g is primitive

Question

How do I go about proving that an element g is primitive? If I let p be a prime. Is it then the same as proving that every non-zero element in $Z_p$ can be written as a power of g?

Answer 1

If you can factorize $p-1$, then it is enough to show that for all prime divisors $q$ of $p-1$, $g^{(p-1)/q}$ is not equal to $1$ mod $p$. This can be checked efficiently for $p$ in the thousands of digits.