8
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Extremely sorry for the typo, I was confusing with $\mathbb{F}_p$ $\endgroup$
    – Pritam Majumder
    Aug 26, 2012 at 16:35

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ @quid: thanks for the edit, was doing this on iPad... $\endgroup$
    – Igor Rivin
    Aug 26, 2012 at 18:16
  • $\begingroup$ @Igor Rivin: Thanks for the link, I was more interested in the second question. $\endgroup$
    – Pritam Majumder
    Aug 30, 2012 at 6:03
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2012 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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