4

I'm asking this question with regards to when a polynomial $m(t)$ can be the minimal polynomial of an algebraic element $\alpha$ of a field extension $F(\alpha):F$, when $F$ is a finite field.

For example, if we have a polynomial like $t^{37}+1$, we know the polynomial has an obvious root in $\mathbb{F}_p$, namely we can use $(p-1)^{37}+1=0$. That means we can factorise the polynomial into $t^{37}+1=(t-(p-1))\cdot(t^{36}+\ldots+(p-1))$. What about general monic polynomials over finite fields? Is there something analogous to Eisenstein's criterion that we can use to check for irreducibility?

anegligibleperson
  • 2,509
  • 2
    You might be interested in http://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields – azimut Aug 29 '13 at 10:02
  • Yes. Eisenstein Crierion applies for integral domains in general...but it isn't as useful as with the rationals, since finite integral domains = fields. – DonAntonio Aug 29 '13 at 10:04
  • Finite fields are not fields of fractions of anything simpler, so divisibility questions between coefficients are meaningless => nothing like Eisenstein's criterion exists. – Jyrki Lahtonen Aug 29 '13 at 10:06
  • 1
    I often approach irreducibility of these polynomials from a different angle: non-zero elements of finite fields are always roots of unity. Characteristic zero theory tells that the minimal polynomials of roots of unity are the cyclotomic polynomials, so the question can, in a way, be rephrased as: how do the cyclotomic polynomials factor, when reduced modulo a prime? The easy part is that a field of $p^n$ elements has a root of unity of $\alpha$ order $k$ (coprime to $p$), iff $k\mid p^n-1$. The degree of the minimal polynomial of $\alpha$ is then the smallest exponent $n$ with that property. – Jyrki Lahtonen Aug 29 '13 at 10:15
  • (cont'd) The hard part of actually finding the minimal polynomial takes more. See azimut's link. Your example polynomial is a case in point, as it is a factor of $t^{74}-1$, so its zeros are roots of unity of order that is a factor of $74$. Of course, in general that is not the case, and again more general methods are needed. – Jyrki Lahtonen Aug 29 '13 at 10:17
  • 2
    one useful thing: the map $\alpha\mapsto\alpha^p$ (Frobenius automorphism) gives you a permutation of the roots of your polynomial $f$ (they are in some extension of $\mathbb F_p$). The permutation splits to cycles, and that determines the factorization of $f$ to irreducible factors. (This method works nicely for $f=t^n-1$, when it's easy to find the permutation explicitly). – user8268 Aug 29 '13 at 11:04
  • "Is there something analogous to Eisenstein's criterion that we can use to check for irreducibility?" I trust you are aware that Eisenstein's criterion (over, say, the integers) hardly ever applies; that is, most irreducible polynomials do not satisfy the Eisenstein conditions. – Gerry Myerson Aug 29 '13 at 13:13

1 Answers1

2

If the polynomial is reducible in $\mathbb{Z}[x]$, then it is reducible over $\mathbb{F}_p[x]$ for every prime. The converse unfortunately is not true, e.g., $x^4+1$ is irreducible in $\mathbb{Z}[x]$, but reducible over any finite field. On the other hand, if we have a given polynomial in $\mathbb{F}_q[x]$, we can use several algorithms, e.g., the Berlekamp algorithm, to obtain a factorisation into powers of irreducible polynomials. For example, $$ x^{37} + 37x + 37 $$ is irreducible over a finite field with $103$ elements, but reducible over a field with $101$ elements, namely $$ x^{37} + 37x + 37=(x+17)(x^2+9x+99)(x^{34}+ \cdots +91). $$

Dietrich Burde
  • 130,978