Download Wolfram Notebook

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.

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).

The complexity of testing irreducibility depends on how the polynomial is represented. In a sparse representation, nonzero coefficients and their exponents are listed in binary, so the polynomial degree may be exponential in the input length. Cao et al. (2026) report that irreducibility for sparse univariate polynomials over is coNP-hard under deterministic polynomial-time many-one reductions. Equivalently, reducibility is NP-hard under those reductions. They also give a upper bound conditional on recent external theorems about zero-free regions of Dedekind zeta functions and effective prime-ideal estimates. Those analytic inputs require separate verification. The class allows acceptance probability only strictly greater than one half, and differs from bounded-error randomized polynomial time. Cao et al. (2026) report that interactive collaboration with AI systems contributed to the main mathematical results.

See also

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

Explore with Wolfram|Alpha

References

Cao, Y.; Gao, X.-S.; Huang, Q.-L.; and Nie, J. "Irreducibility Testing of Sparse Polynomials Over Integers Is NP-Hard and Probabilistic Polynomial Time." 27 Oct 2026. https://arxiv.org/abs/2610.37179.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." https://web.archive.org/web/20170516122408/http://theory.cs.uvic.ca/inf/neck/PolyInfo.html.Sloane, N. J. A. and Plouffe, S. Figure M0564 in The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Sloane, N. J. A. Sequences A001037/M0116 and A059912 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Irreducible Polynomial

Cite this as:

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

Subject classifications