Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.