# How to quickly find a root of unity in a ring?

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?

• 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)$. – FlagCapper May 2 '14 at 9:41
• good point. i edited the quesiton – Wuschelbeutel Kartoffelhuhn May 2 '14 at 9:42
• If you find a primitive root it's easy. But do you know how to find it? – Jack Yoon May 2 '14 at 9:44