1
$\begingroup$

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.

  • 0
    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.2011-11-09

0 Answers 0