of irreducible polynomials over finite fields.
Israel Journal of Mathematics, pages 1-29, May 2012..
We present a randomized algorithm that on input a finite
field K with q elements and a positive integer d
outputs a degree d irreducible polynomial in K[x]. The
running time is d1+ε(d) ×(log
q)5+ε(q) elementary operations. The function
ε in this expression is a real positive function
belonging to the class o(1), especially, the complexity is
quasi-linear in the degree d. Once given such an
irreducible polynomial of degree d, we can compute random
irreducible polynomials of degree d at the expense of
elementary operations only.
[ bib |