nmod_poly_minimal_irreducible

An irreducible binomial of degree $n$ exists if and only if every prime factor of $n$ divides $p - 1$, and $4 \mid p - 1$ if $4 \mid n$. Among the polynomials with the least number of terms the function returns the first in the following order. A trinomial $x^n + a x^k + b$ comes before its monic reversal $x^n + a' x^{n-k} + b'$ if $k < n - k$. Writing $f = x^n + a_1 x^{k_1} + \cdots + a_t x^{k_t}$ with $n > k_1 > \cdots > k_t$, the tuples $(a_1, \ldots, a_t, k_1, \ldots, k_t)$ are ordered lexicographically, which favours small coefficients (all 1 if possible) and then small degrees of the middle terms. Sparse moduli make reduction cheap, see _nmod_poly_divrem_newton_n_preinv. The choice of defining polynomials for finite fields is discussed in Defining polynomials.