Editing Finite field (section)

== Polynomial factorization ==
{{main|Factorization of polynomials over finite fields}}
If {{math|''F''}} is a finite field, a non-constant [[monic polynomial]] with coefficients in {{math|''F''}} is [[irreducible polynomial|irreducible]] over {{math|''F''}}, if it is not the product of two non-constant monic polynomials, with coefficients in {{math|''F''}}.

As every [[polynomial ring]] over a field is a [[unique factorization domain]], every monic polynomial over a finite field may be factored in a unique way (up to the order of the factors) into a product of irreducible monic polynomials.

There are efficient algorithms for testing polynomial irreducibility and factoring polynomials over finite fields. They are a key step for factoring polynomials over the integers or the [[rational numbers]]. At least for this reason, every [[computer algebra system]] has functions for factoring polynomials over finite fields, or, at least, over finite prime fields.

=== Irreducible polynomials of a given degree ===
The polynomial
<math display="block">X^q-X</math> 
factors into linear factors over a field of order {{math|''q''}}. More precisely, this polynomial is the product of all monic polynomials of degree one over a field of order {{math|''q''}}.

This implies that, if {{math|1=''q'' = ''p<sup>n</sup>''}} then {{math|''X<sup>q</sup>'' − ''X''}} is the product of all monic irreducible polynomials over {{math|GF(''p'')}}, whose degree divides {{math|''n''}}. In fact, if {{math|''P''}} is an irreducible factor over {{math|GF(''p'')}} of {{math|''X<sup>q</sup>'' − ''X''}}, its degree divides {{math|''n''}}, as its [[splitting field]] is contained in {{math|GF(''p''<sup>''n''</sup>)}}. Conversely, if {{math|''P''}} is an irreducible monic polynomial over {{math|GF(''p'')}} of degree {{math|''d''}} dividing {{math|''n''}}, it defines a field extension of degree {{math|''d''}}, which is contained in {{math|GF(''p''<sup>''n''</sup>)}}, and all roots of {{math|''P''}} belong to {{math|GF(''p''<sup>''n''</sup>)}}, and are roots of {{math|''X<sup>q</sup>'' − ''X''}}; thus {{math|''P''}} divides {{math|''X<sup>q</sup>'' − ''X''}}. As {{math|''X<sup>q</sup>'' − ''X''}} does not have any multiple factor, it is thus the product of all the irreducible monic polynomials that divide it.

This property is used to compute the product of the irreducible factors of each degree of polynomials over {{math|GF(''p'')}}; see ''[[Distinct degree factorization]]''.

=== Number of monic irreducible polynomials of a given degree over a finite field ===
The number {{math|''N''(''q'', ''n'')}} of monic irreducible polynomials of degree {{math|''n''}} over 
{{math|GF(''q'')}} is given by<ref>{{harvnb|Jacobson|2009|loc=§4.13}}</ref>
<math display="block">N(q,n)=\frac{1}{n}\sum_{d\mid n} \mu(d)q^{n/d},</math>
where {{math|''μ''}} is the [[Möbius function]]. This formula is an immediate consequence of the property of {{math|''X''<sup>''q''</sup> − ''X''}} above and the [[Möbius inversion formula]].

By the above formula, the number of irreducible (not necessarily monic) polynomials of degree {{math|''n''}} over {{math|GF(''q'')}} is {{math|(''q'' − 1)''N''(''q'', ''n'')}}.

The exact formula implies the inequality
<math display="block">N(q,n)\geq\frac{1}{n} \left(q^n-\sum_{\ell\mid n, \ \ell \text{ prime}} q^{n/\ell}\right);</math>
this is sharp if and only if {{math|''n''}} is a power of some prime.
For every {{math|''q''}} and every {{math|''n''}}, the right hand side is positive, so there is at least one irreducible polynomial of degree {{math|''n''}} over {{math|GF(''q'')}}.