Irreducibility testing over finite fields

Testing whether $f \in \mathbb{F}_q[x]$ of degree $n$ is irreducible is cheaper than factoring it, and is the inner loop of the construction of irreducible polynomials, which define the extension fields $\mathbb{F}_{q^n}$. All tests are based on Theorem 1 of Factoring polynomials over finite fields: $x^{q^d} - x$ is the product of the monic irreducible polynomials whose degree divides $d$. As in the factorisation algorithms, the powers $h_d = x^{q^d} \bmod f$ are computed from $h_1 = x^q \bmod f$ either by exponentiation by $q$ or by modular composition, $h_{i + j} = h_i(h_j) \bmod f$ (Lemma 3 of Factoring polynomials over finite fields). $M(n)$ and $C(n)$ denote the costs of multiplication and of modular composition.

Rabin's test#

The test needs $h_n$ and $h_{n/r}$ for the $\omega(n)$ prime divisors $r$ of $n$. gr_poly_is_irreducible_rabin computes the ladder $L_i = x^{q^{2^i}} \bmod f = L_{i-1}(L_{i-1}) \bmod f$ for $2^i \le n$, and then each $h_e$ as a composition of the $L_i$ along the binary expansion of $e$. This takes $O(\log n)$ compositions for the ladder and for each of the $1 + \omega(n)$ powers, independently of $q$ apart from the first step $L_0 = h_1$, which costs $O(M(n) \log q)$. The test does the same amount of work whether or not $f$ is irreducible.

nmod_poly_is_irreducible_rabin is an older implementation of the same test that computes each $h_e$ by $e$ exponentiations by $q$, at a cost of $O(n M(n) \log q)$.

Ben-Or's test and the distinct-degree test#

Ben-Or's test computes $h_1, h_2, \ldots$ one after the other and stops at the first nontrivial gcd. Its worst case, reached for irreducible $f$, is $n/2$ steps; but a random polynomial has a factor of small degree with high probability: by an analogue of Mertens' theorem, the probability that a random monic polynomial of degree $n$ has no irreducible factor of degree at most $i$ tends to about $e^{-\gamma}/i$ for large $n$ and $i$, so the expected number of steps on random input is small [GaoPan1997]. Since a random polynomial of degree $n$ is irreducible with probability about $1/n$, this early exit is what matters when searching for irreducible polynomials, and Gao and Panario [GaoPan1997] found Ben-Or's test much faster than Rabin's in that setting. gr_poly_is_irreducible_ben_or implements it, with each step a composition with the precomputed matrix of powers of $h_1$ when $q$ is large, and an exponentiation by $q$ otherwise.

The distinct-degree test gr_poly_is_irreducible_ddf runs the coarse phase of the baby-step giant-step distinct-degree factorisation (Algorithm 2 of Factoring polynomials over finite fields): it computes $\ell \approx \sqrt{n/2}$ baby steps and then, for each interval $(\ell j, \ell(j+1)]$ of degrees, one giant step and the gcd of $f$ with the interval polynomial, stopping at the first nontrivial gcd. It is Ben-Or's test with the degrees grouped into intervals, so it costs $O(\sqrt{n}\, C(n) + n M(n))$ for irreducible inputs and also exits early for most reducible ones, though only after the $\ell$ baby steps.

Both tests first check squarefreeness with one gcd ($\gcd(f, f') = 1$), which is cheap and rejects some inputs immediately.

FLINT's strategy#

gr_poly_is_irreducible, which nmod_poly_is_irreducible, fmpz_mod_poly_is_irreducible and the fq_*_poly_is_irreducible functions wrap, proceeds as follows for $f$ of degree $n \ge 2$:

1. Over a prime field $\mathbb{F}_p$ with $p \le \max(200, 2(n + 1))$, evaluate $f$ at all $p$ elements and return false if there is a root. For small $p$ this rejects a large fraction of random inputs at a cost of $O(np)$.
2. If $n < 600$, return the result of the distinct-degree test.
3. Otherwise check squarefreeness, then compute $\gcd(f, x^{q^i} - x)$ for $i \le 4$ (with exponentiations) and return false if one is nontrivial, and finally return the result of Rabin's test.

For large irreducible inputs Rabin's test with the Frobenius ladder needs $O(\log n)$ compositions against $O(\sqrt{n})$ for the distinct-degree test, so the crossover is at a moderate degree; the filter in step 3 keeps the early exit for random inputs, whose smallest factor usually has small degree. The generic functions return T_UNKNOWN when they cannot decide (for example over a context that is not known to be a finite field); the type-specific wrappers throw an exception in that case, and, unlike the generic functions, consider constants irreducible.

Constructing irreducible polynomials#

An irreducible polynomial of degree $n$ over $\mathbb{F}_q$ is found by testing random monic polynomials: there are about $q^n / n$ of them among the $q^n$ monic polynomials, so about $n$ trials are needed on average (nmod_poly_randtest_irreducible, fmpz_mod_poly_randtest_irreducible). For finite field arithmetic sparse polynomials are preferable, because reduction modulo a trinomial or pentanomial is cheap; nmod_poly_minimal_irreducible searches binomials, trinomials, tetranomials and pentanomials in a fixed order with nmod_poly_is_irreducible_ddf. Conway polynomials, which make the embeddings between different extension fields compatible, cannot be computed efficiently in general and are taken from a table ([Lüb2004]; _nmod_poly_conway). The finite field contexts such as fq_nmod_ctx_init_ui use the Conway polynomial when the table contains it and the sparse polynomial of nmod_poly_minimal_irreducible otherwise. The choice of defining polynomials for the finite field types is discussed in Defining polynomials.

@misc{flint-doc-algorithms-polynomials-irreducibility,
  author       = {{The FLINT team}},
  title        = {{Irreducibility testing over finite fields}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/polynomials/irreducibility.html},
  note         = {Generated 2026-11-02}
}