TOPICS
Search

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

 f(x)=g(x)h(x)

(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

 L_q(n)=1/nsum_(d|n)mu(n/d)q^d,

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.

nirreducible polynomials
11+x, x
21+x+x^2
31+x+x^3, 1+x^2+x^3
41+x+x^4, 1+x+x^2+x^3+x^4, 1+x^3+x^4
51+x^2+x^5, 1+x+x^2+x^3+x^5, 1+x^3+x^5, 1+x+x^3+x^4+x^5, 1+x^2+x^3+x^4+x^5, 1+x+x^2+x^4+x^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

Eisenstein's Irreducibility Criterion, Field, Finite Field, Lyndon Word, Necklace, Polynomial, Primitive Polynomial

Explore with Wolfram|Alpha

References

Marsh, R. Tables of Irreducible Polynomials of GF(2) through Degree 19. Washington, DC: U. S. Dept. Commerce, 1957.Nagell, T. "Irreducibility of the Cyclotomic Polynomial." §47 in Introduction to Number Theory. New York: Wiley, pp. 160-164, 1951.Ruskey, F. "Information on Primitive and Irreducible Polynomials." http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html.Sloane, N. J. A. Sequences A001037/M0116 and A059912 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0564 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Referenced on Wolfram|Alpha

Irreducible Polynomial

Cite this as:

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

Subject classifications