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.

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

Theorem: Assuming that the generalized Riemann hypothesis is true, there is a deterministic polynomial time algorithm to find an irreducible polynomial of degree $n$ over $\mathbb{F_p}$ The algorithm uses $O(n^6(\log p+\log n)^4(\log p)^2)$ bit operations.

My question : What is the most efficient algorithm for constructing an irreducible polynomial ?

I have found this document very informative, but it is about probabilistic algorithms.

share|cite|improve this question
Did you notice Victor Shoup's reference to his 1990 Math. Comp. paper on deterministic algorithms for this problem? In particular in the Conclusions section of the paper of his you link above, he says that the techniques there can improve the deterministic algorithm to $O^~(n^3)$ complexity. It seems unlikely that "the most efficient algorithm" can be crowned at this time. – hardmath Nov 9 '11 at 14:14

Your Answer


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

Browse other questions tagged or ask your own question.