Best way to calculate unit roots of GF(n)

Question

What's the best and most simple way to calculate unit roots of $GF(n)$.

$n$ could be any integer.

Please make a distinction between primes and non-primes.

Example:

• Show that $GF(29)$ has 7th units roots.
• How much 7th unit roots does $GF(29)$ have?

Answer 1

Here is the clue: whether the order of the field is prime or not makes no difference. It just depends on $n-1$, the order of the multiplicative group (which is cyclic). So you can think of this group being generated by some element $\alpha$, for which $\alpha^{n-1} = 1$. Now try to use this to determine what other types of roots there might be.

Answer 2

You can always do the following.

• All the non-zero elements $z\in GF(29)$ satisfy the equation $z^{28}=1$.
• So if $z\in GF(29), z\neq0$, then $w=z^4$ satistifies the equation $w^7=1$ because $w^7=(z^4)^7=z^{28}=1$.

This suggest an algorithm for finding a seventh root of unity:

1. Pick an arbitrary element $z\in GF(29),z\neq0$.
2. Calculate $w=z^4$. If $w\neq1$, then $w$ is a primitive seventh root of unity (primitivity depends on seven being a prime number - in a more general setting you need to do more tests).
3. Once you find a primitive seventh root of unity $w$, its powers will also be seventh roots of unity (primitive unless equal to $1$).

The method generalizes to the problem of finding $d$th root of unity in the field $GF(q)$, where $d\mid q-1$. If $d$ is not a prime, you need those extra tests.