Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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 but this is generally, as far as is known today, a very computationally difficult problem.

share|cite|improve this answer

Your Answer


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.