Algorithm for finding the nth primative root of unity in a field

Question

We recently learned in our algorithm course about the FFT. One can do FFT over a finite field, but it's not clear to me how to find the nth primative root efficiently. Can somebody provide me with an algorithm or literature

Answer 1

There is generally no efficient algorithm known for finding primitive roots. A brute force approach, simply trying out all elements, is clearly computationally costly. There are a few tricks to slightly improve on the brute force approach (see http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots) but this is generally, as far as is known today, a very computationally difficult problem.