Lets say we're in a field where multiplication and addition are modded against some prime number P (so it's defined for {0,....,P-1}

Lets fix a number N < P, such that a root of unity can be found.

How do I find the Nth root of unity=w quickly (i.e., the Nth power of w is 1 and all lesser powers are not equal to 1)? Is there a better way than trial-and-error/brute-force though all values 0,...,P-1?

  • $\begingroup$ You won't be able to find a suitable value for every $N$. This is because $a^{p - 1} \equiv 1$ for all $a$, from which you can show that $N|(p - 1)$. $\endgroup$ – FlagCapper May 2 '14 at 9:41
  • $\begingroup$ good point. i edited the quesiton $\endgroup$ – Wuschelbeutel Kartoffelhuhn May 2 '14 at 9:42
  • $\begingroup$ If you find a primitive root it's easy. But do you know how to find it? $\endgroup$ – Jack Yoon May 2 '14 at 9:44

Your Answer

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

Browse other questions tagged or ask your own question.