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

Question

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$

Answer 1

I'm afraid that the answer is negative. If you would have such an algorithm then you'd have an efficient algorithm for factorizing large Mersenne's numbers...