TITLE: Find primitive-$n$-th roots of unity over finite field $\mathbb{F}_a$??
QUESTION [0 upvotes]: 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$

REPLY [0 votes]: 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...
{"set_name": "stack_exchange", "score": 0, "question_id": 2140557}