Irreducible Polynomial

An irreducible polynomial over a field is a polynomial of positive polynomial degree that cannot be factored into two polynomials of positive polynomial degree over that field.

For example, in the polynomial ring of polynomials with rational coefficients, a nonconstant polynomial is irreducible if there do not exist two nonconstant polynomials and with rational coefficients such that

(Nagell 1951, p. 160). Similarly, over the finite field GF(2), is irreducible, but is not, since (mod 2).

Irreducible polynomial checking is implemented in the Wolfram Language as IrreduciblePolynomialQ[poly].

For a positive integer and a prime power , the number of irreducible monic polynomials of polynomial degree over the finite field GF() is

where is the Möbius function.

The number of irreducible polynomials of polynomial degree over the finite field GF(2) equals the number of aperiodic -bead necklaces of two colors, counted up to rotation, and the number of binary Lyndon words of length . The first few counts for , 2, ... are 2, 1, 2, 3, 6, 9, 18, ... (OEIS A001037). The following table lists the irreducible polynomials over the finite field GF(2) of polynomial degree 1 through 5.

	irreducible polynomials
1	,
2
3	,
4	, ,
5	, , , , ,

The possible polynomial orders of irreducible polynomials of polynomial degree over the finite field GF(2) with nonzero constant coefficient, listed in ascending order for , 2, ..., are 1; 3; 7; 5, 15; 31; 9, 21, 63; 127; 17, 51, 85, 255; 73, 511; ... (OEIS A059912).