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