Defining polynomials

A field $\mathbb{F}_{p^d}$ is constructed as $\mathbb{F}_p[x]/(f)$ for an irreducible $f$ of degree $d$. Any such $f$ gives an isomorphic field, but the choice matters in practice:

• a sparse $f$, with few nonzero terms, makes the reduction after each multiplication cheap (Reduction modulo the defining polynomial);
• a primitive $f$, whose roots generate $\mathbb{F}_q^\times$, is required by the Zech logarithm representation and gives a known generator of the multiplicative group (used, for example, as the non-square in fq_sqrt);
• a standard $f$ makes results reproducible across systems and allows compatible embeddings between fields of different degrees.

Counting irreducible and primitive polynomials#

The number of monic irreducible polynomials of degree $d$ over $\mathbb{F}_p$ is $\frac{1}{d} \sum_{e \mid d} \mu(d/e) p^e$, which lies between $p^d/d - 2p^{d/2}/d$ and $p^d/d$ [LN1997]; so a random monic polynomial of degree $d$ is irreducible with probability about $1/d$, and random search with an irreducibility test (Irreducibility testing over finite fields) needs about $d$ attempts. Of the $p^d - 1$ nonzero elements, $\varphi(p^d - 1)$ are primitive, and each primitive polynomial has $d$ primitive roots, so there are $\varphi(p^d - 1)/d$ primitive polynomials, roughly a fraction $\varphi(p^d - 1)/(p^d - 1)$ of the irreducible ones, which is at least $c/\log\log(p^d)$ for a constant $c > 0$. Testing primitivity requires the factorisation of $p^d - 1$ (fq_multiplicative_order).

Conway polynomials#

The ordering is lexicographic on the sequence $(-f_{d-1}, f_{d-2}, -f_{d-3}, \ldots, (-1)^d f_0)$ of coefficients with alternating signs, each reduced to an integer in $[0, p)$. The compatibility condition says that if $\alpha_d$ is a root of $C_{p,d}$ and $m \mid d$, then $\alpha_d^{(p^d - 1)/(p^m - 1)}$ is a root of $C_{p,m}$; so the roots of the Conway polynomials of all degrees form a compatible system, and the field $\mathbb{F}_p[x]/(C_{p,m})$ embeds into $\mathbb{F}_p[x]/(C_{p,d})$ by $x \mapsto x^{(p^d-1)/(p^m-1)}$. Conway polynomials were defined by Parker for the computation of modular character tables and named after J. H. Conway; they are used by GAP, Magma, Sage and other systems as the standard defining polynomials. Computing them is expensive, since the definition requires a search through primitive polynomials (with the factorisation of $p^d - 1$) and compatibility tests; Heath and Loehr give algorithms [HeaLoe2004], and Lübeck maintains the reference tables [Lüb2004].

FLINT stores a compressed copy of Lübeck's table in nmod_poly (_nmod_poly_conway), for all primes $p < 109988$ and the degrees for which a Conway polynomial is known: degrees up to 409 for $p = 2$, up to about 200 for $p < 20$, and fewer for larger primes (up to 12 for $p < 300$, 9 for $p < 3371$, 6 for $p < 11000$ and 4 above), in each case with gaps. Since Conway polynomials are primitive, they are always suitable for the Zech representation, but they are not sparse in general.

Sparse and minimal-weight polynomials#

When no Conway polynomial is available, the modules choose sparse polynomials, which minimise the cost of reduction.

Binomials. By a classical theorem [LN1997], $x^d - a$ is irreducible over $\mathbb{F}_p$ if and only if every prime divisor of $d$ divides the order $e$ of $a$ but not $(p - 1)/e$, and $p \equiv 1 \pmod 4$ if $4 \mid d$. In particular an irreducible binomial of degree $d$ exists only if every prime factor of $d$ divides $p - 1$.

Trinomials $x^d + a x^k + b$ exist for most but not all $(p, d)$: by Swan's theorem there is no irreducible trinomial of degree $d \equiv 0 \pmod 8$ over $\mathbb{F}_2$ [Swa1962], and other obstructions are known. It is conjectured that an irreducible tetranomial ($p > 2$) or pentanomial ($p = 2$) always exists.

nmod_poly_minimal_irreducible returns a monic irreducible polynomial with the least possible number of terms, trying binomials, trinomials, tetranomials and pentanomials in this order and returning the first one in a fixed ordering, after sieving out candidates with small factors; it is deterministic. fmpz_mod_poly_randtest_sparse_irreducible draws random irreducible trinomials, then pentanomials, then random sparse polynomials, for multiprecision $p$.

Choices in FLINT#

In all modules a polynomial can also be given explicitly (fq_ctx_init_modulus and its analogues); it must be irreducible, and primitive for fq_zech. The choices for fq and fq_zech without a Conway polynomial are reproducible for a given FLINT version, but are not standardised; programs that exchange elements with other software should give the defining polynomial explicitly.

Use in FLINT#

• _nmod_poly_conway (table lookup) is used by _fq_nmod_ctx_init_conway_ui, _fq_ctx_init_conway_ui and _fq_zech_ctx_init_conway_ui, and through them by all default context constructors.
• fq_nmod_ctx_init_minimal_weight_ui uses nmod_poly_minimal_irreducible; fq_ctx_init uses fmpz_mod_poly_randtest_sparse_irreducible; fq_zech_ctx_init_random_ui uses nmod_poly_randtest_monic_primitive.
• fq_poly_randtest_irreducible constructs random irreducible polynomials over $\mathbb{F}_q$ itself by random search with a distinct-degree test.

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