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.