Find primitive-$n$-th roots of unity over finite field $\mathbb{F}_a$??

Is there efficient methods to find primitive-$n$-th roots of unities over $\mathbb{F}_a$??

In other word, find $\zeta$ such that,

$\zeta^n \equiv 1$

where $\zeta \in \mathbb{F}_a$

Also, is there efficient methods to find primitive-$n$-th roots of unities over $\mathbb{Z}_a$??

In other word, find $\zeta$ such that,

$\zeta^n \equiv 1 \mod a$

where $\zeta \in \mathbb{Z}_a$

• This depends on the size of the parameters. How is the field given to you? Often enough $\Bbb{F}_a$ is given as $\Bbb{F}_p[x]/(p(x))$, where $p(x)$ is a primitive polynomial. In that case an $n$th primitive root is given by the recipe $x^{(a-1)/n}+(p(x))$. Even with some black box description of $\Bbb{F}_a$ you can take the non-deterministic approach of raising random elements of the field to power $(a-1)/n$ (which is fast by square-and-multiply). Of course, quick testing of whether such a candidate actually is of order $n$ requires you to know a factorization of $n$. – Jyrki Lahtonen Feb 12 '17 at 9:40