If we are working in a finite field of integers adjoined with $z$ values, we have $\mathbb{F}_{p^z}$, assuming that we constructed the field correctly. How quickly can we find a value, $\omega$, that is a $p^z - 1$ primitive root of unity?
AN APPROACH
@ACL's approach, taken from this MathOverflow answer is essentially as follows:
(1) Factor $p^z - 1$, as a product of primes to powers.
(2) For each prime power $q^r$, find a value $v$ whose power $v^{(p-1) / q}$ is not equivalent to $1$.
(3) Multiply all values $v^{(p-1) / q}$ together, for each prime power.
This should give an element $\omega$ with the desired properties.
There is also another approach, by Derek Holt, found here. The difference is that in this question, we are working with a specific ring, namely a finite field.
A QUESTION
Knowing that we're working in the specialized setting of a finite field with $p^z$ elements, can we find a primitive $p^z - 1$ root of unity faster?