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.

  • $\begingroup$ Extremely sorry for the typo, I was confusing with $\mathbb{F}_p$ $\endgroup$ – Pritam Majumder 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.

  • $\begingroup$ @quid: thanks for the edit, was doing this on iPad... $\endgroup$ – Igor Rivin Aug 26 '12 at 18:16
  • $\begingroup$ @Igor Rivin: Thanks for the link, I was more interested in the second question. $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – Will Sawin Aug 26 '12 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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