Irreducible Polynomial

A polynomial is said to be irreducible if it cannot be factored into nontrivial polynomials over the same field.

For example, in the field of rational polynomials Q[x] (i.e., polynomials f(x) with rational coefficients), f(x) is said to be irreducible if there do not exist two nonconstant polynomials g(x) and h(x) in x with rational coefficients such that

(Nagell 1951, p. 160). Similarly, in the finite field GF(2), x^2+x+1 is irreducible, but x^2+1 is not, since (x+1)(x+1)=x^2+2x+1=x^2+1 (mod 2).

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

In general, the number of irreducible polynomials of degree n over the finite field GF(q) is given by

where mu(n) is the Möbius function.

The number of irreducible polynomials of degree n over GF(2) is equal to the number of n-bead fixed aperiodic necklaces of two colors and the number of binary Lyndon words of length n. The first few numbers of irreducible polynomial (mod 2) for n=1, 2, ... are 2, 1, 2, 3, 6, 9, 18, ... (OEIS A001037). The following table lists the irreducible polynomials (mod 2) of degrees 1 through 5.

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

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Irreducible Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IrreduciblePolynomial.html

Subject classifications