Arithmetic in finite fields

A finite field with q = p^d elements is unique up to isomorphism, but computing in it requires a concrete model. FLINT, like most systems, uses the model \mathbb{F}_q = \mathbb{F}_p[x]/(f) for an irreducible polynomial f of degree d, the defining polynomial, and stores elements either as polynomials of degree less than d or, for small fields, as discrete logarithms with respect to a root of f. The standard references for the mathematics are Lidl and Niederreiter [LN1997] and, for the algorithms, von zur Gathen and Gerhard [GG2003] and Shoup [Sho2009].

The representations#

The three extension field modules fq_zech, fq_nmod and fq share their interface: their headers and most of their code are generated from the same templates (fq_templates.h, fq_poly_templates.h and so on), and the vector, matrix, polynomial, factorisation and embedding modules exist for each of them. fq_default wraps all five representations behind one interface and chooses the representation when a field is created (Getting started with finite fields):

• Zech logarithms if d > 1 and \operatorname{bits}(p) \cdot d \le 16, so that q < 2^{16} and the tables of 2q + p words fit in about a megabyte, in the cache of current processors;
• fq_nmod for other extension fields with p < 2^{\mathtt{FLINT\_BITS}};
• fq for extension fields with larger p;
• nmod and fmpz_mod for prime fields.

The Zech representation needs a primitive defining polynomial, one whose root generates the cyclic group \mathbb{F}_q^\times; when a non-primitive polynomial is given, fq_default falls back to fq_nmod.

Costs#

In the polynomial representations a product costs a product of two polynomials of degree less than d over \mathbb{F}_p (or over \mathbb{Z}, for fq) and a reduction modulo f, that is O(M(d)) operations in \mathbb{F}_p, where M(d) is the cost of polynomial multiplication; for the small d that are common in practice this is O(d^2) word operations plus the allocation and normalisation overhead of the polynomial types. An inverse costs an extended Euclidean algorithm in \mathbb{F}_p[x], O(d^2) operations. In the Zech representation a product, quotient, inverse or power costs one or two word operations, and a sum one table lookup, but building the tables costs q products when the context is created.

The following table shows timings measured with the installed library on the x86-64 machine used to build this documentation, through the fq_default interface: one multiplication and one addition of field elements, and the product of two polynomials of length 1000 over the field.

Zech logarithms are faster by more than an order of magnitude for element arithmetic in small fields, but lose their advantage when the tables no longer fit in the cache (q \approx 10^6 in the last rows), and for long polynomials, whose products are computed by converting the coefficients to the polynomial representation and using fast multiplication over \mathbb{Z}/p\mathbb{Z} in all three modules (Multiplying polynomials over finite fields).

Algorithms#

Polynomials, matrices and power series over \mathbb{F}_q mostly use the generic algorithms of gr_poly and gr_mat, with the multiplication of the respective module: division and power series by Newton iteration (Newton iteration for power series and division), GCDs by the half-GCD algorithm (Half-GCD), modular composition by the Brent–Kung algorithm (Composition and modular composition), and linear algebra by Gaussian elimination (Gaussian elimination and LU decomposition).

@misc{flint-doc-algorithms-finite-fields-overview,
  author       = {{The FLINT team}},
  title        = {{Arithmetic in finite fields}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/finite-fields/overview.html},
  note         = {Generated 2026-10-20}
}