How does one find the primitive roots of a non-prime number?

Question

Several algorithms exist to find the primitive roots of prime numbers. How does one find the primitive roots of a non-prime number?

Answer 1

Apart from $1$, $2$, and $4$, the only numbers with primitive roots are the numbers of the shape $p^k$ or $2p^k$, where $p$ is an odd prime.

Once we have a primitive root $g$ for the odd prime $p$, finding primitive roots for $p^k$ and $2p^k$ is relatively cheap.

For $p^k$, we use the fact that if $g$ is a primitive root of $p$, then $g$ or $g+p$ is a primitive root of $p^k$ for all $k$.

So once we have found a primitive root $g$ of $p$, we test whether $g$ is a primitive root of $p^2$. If it is, we are finished. And if it is not, then we know $g+p$ is a primitive root of $p^k$ for all $k$.

As for $2p^k$, if $r$ is a primitive root of $p^k$ and $r$ is odd, then $r$ is a primitive root of $2p^k$. And if $r$ is even then $r+p^k$ is a primitive root of $2p^k$.