MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Extremely sorry for the typo, I was confusing with $\mathbb{F}_p$ – Pritam Majumder Aug 26 '12 at 16:35
up vote 3 down vote accepted

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

share|cite|improve this answer
@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 Majumder 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.

share|cite|improve this answer
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

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.