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 ![Q[x]](/images/equations/IrreduciblePolynomial/Inline1.svg)
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).
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.
