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
    Commented 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
    Commented Aug 26, 2012 at 18:16
  • $\begingroup$ @Igor Rivin: Thanks for the link, I was more interested in the second question. $\endgroup$
    – Pritam Majumder
    Commented 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
    Commented Aug 26, 2012 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .