Engineering / Mathematics — Fields, Series and Factorisation
Irreducible Polynomials
Recognising irreducible polynomials, the standard criteria, and counting them over a finite field.
Executive summary
Irreducibility is the polynomial analogue of primality, and like primality it has cheap necessary conditions and more expensive definitive tests.
Over a finite field the count of irreducibles of each degree follows from Mobius inversion, which is what justifies finding one by random search.
Learning objectives
- Apply the standard irreducibility criteria.
- Count irreducible polynomials over a finite field.
- Justify random search for an irreducible of given degree.
01Criteria
| Criterion | Applies to | Conclusion |
|---|---|---|
| Degree 1 | Any field | Always irreducible |
| Degree 2 or 3, no root | Any field | Irreducible |
| Root test | Degree ≥ 2 | A root gives a linear factor, hence reducible |
| Eisenstein | Z[X], prime p | Irreducible over Q if p divides all but the leading coefficient and p² does not divide the constant |
| Reduction mod p | Z[X] | Irreducible mod p of the same degree implies irreducible over Q |
Reduction modulo a prime is one-directional. Irreducibility modulo p proves irreducibility over the rationals, but a polynomial irreducible over the rationals may factor modulo every prime.
02Counting over a finite field
Count of monic irreducibles
The number of monic irreducible polynomials of degree n over F_q is
N_q(n) = (1/n) Σ_{d | n} μ(d) q^{n/d}.
The derivation is a clean application of Mobius inversion. Every element of F_{q^n} has a minimal polynomial whose degree divides n, and counting elements by the degree of their minimal polynomial gives q^n = Σ_{d|n} d · N_q(d). Inverting recovers the formula.
N_q(n) ≈ q^n / n, so the proportion of monic degree-n polynomials that are irreducible is about 1/n03Finding an irreducible
Random search for an irreducible of degree n
field F_q, degree na monic irreducible polynomial of degree n- Repeat:
- Draw a monic polynomial of degree n with uniform random coefficients from F_q.
- Test irreducibility.
- If irreducible, return it.
- Until a cap is reached.
expected n candidates, each tested in O(n² log q) operationsThe expected number of candidates is about n by the density estimate, and the irreducibility test is a small number of gcd and exponentiation steps in the quotient algebra.
This is how finite fields are constructed in practice: search for an irreducible of the required degree, then form the quotient algebra. The count formula guarantees the search terminates quickly, and no deterministic method of comparable speed is known.
04Frequently asked questions
Is there a deterministic method for finding an irreducible?
Deterministic algorithms exist but are substantially slower, and unconditional polynomial-time methods for all parameters are not known. Random search with a fast test is what implementations use.
How is irreducibility tested over a finite field?
By checking that X^{q^n} ≡ X modulo f, and that gcd(X^{q^{n/r}} − X, f) = 1 for each prime r dividing n. This is a handful of exponentiations and gcds in the quotient algebra.
Does Eisenstein's criterion apply over finite fields?
Not usefully, since it requires a prime of the base ring and finite fields have none. It is a criterion for polynomials over Z or over a UFD, not over a field.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 366-371.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.