0
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Feb 12 '17 at 9:40
0
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ By "efficient" I mean computationally efficient. $\endgroup$ – Maczinga Feb 12 '17 at 9:19
  • $\begingroup$ AKS is an efficient algorithm for testing primality. $\endgroup$ – mathma Feb 12 '17 at 9:20
  • $\begingroup$ Yes but what about factorisation of large Mersenne numbers? $\endgroup$ – Maczinga Feb 12 '17 at 9:21
  • $\begingroup$ Thanks all. Basically shouldn't we have to do brute force search? $\endgroup$ – mallea Feb 12 '17 at 9:22
  • $\begingroup$ As far I know yes $\endgroup$ – Maczinga Feb 12 '17 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.