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.

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|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.