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?