Reynald Lercier

J.-M. Couveignes and R. Lercier. Fast construction 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 d^1+ε(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 d^1+ε(d) ×(logq)^1+ε(q) elementary operations only.

[ bib | preprint | publication ] Back