# Algorithms to find irreducible polynomials of a given degree

I need to know what are the efficient algorithms to find all the irreducible polynomials of a given degree, say $d$ over a given finite field, say $\mathbb{F}_{p^n}.$

One way is to factorize the polynomial $x^{p^{dn}}-x$, which is the product of all irreducible polynomials whose degree divides $d$, using factorization algorithms and collect all the degree $d$ factors. But I guess we are doing some extra job here. Are there better algorithms to find all irreducible polynomials of degree $d$ ?

I also want to know about the algorithms to find one irreducible polynomial of a given degree over a given finite field.

-
Extremely sorry for the typo, I was confusing with $\mathbb{F}_p$ –  pritam Aug 26 '12 at 16:35

The last word on the second question is this paper of Couveignes and Lercier. The question is highly nontrivial.

-
@quid: thanks for the edit, was doing this on iPad... –  Igor Rivin Aug 26 '12 at 18:16
@Igor Rivin: Thanks for the link, I was more interested in the second question. –  pritam Aug 30 '12 at 6:03
If you want to work over $\mathbb{F}_{p^n}$ then what you wrote is not quite right. What you want is the polynomial $x^{p^{dn}}-x$, which is divisible by all irreducible polynomials of degree $d$ over $\mathbb{F}_{p^n}$.
You can first use inclusion-exclusion to extract from $x^{p^{dn}}-x$ the factor which is the product of all irreducible polynomials of degree $n$ and then factor that. I don't think there is a better way of finding all irreducible polynomials of degree $n$.
If you only need to find one polynomial, then the best thing is to write down a random polynomial of degree $n$ and test for irreducibility. Repeat as necessary.
This polynomial will be the product of the elementary cyclotomic polynomials $\phi_k(x)$ for $k|p^{dn}-1$ but $k\not | p^{en}-1$ for $e<d$. This is true because each $x^{p^{en}}-x$ factors into a product of elementary cyclotomic polynomials so a polynomial computed from them by inclusion-exclusion does as well, and the elementary cyclotomic polynomials involved, since $p$ does not divide the order of their roots, are still relatively prime mod $p$, so we can easily check which ones are included in the product of ell irreducible polynomilas of degree $d$. –  Will Sawin Aug 26 '12 at 16:22