FLINT3.7.0-dev
/
Overview

Finite fields

This section describes how the modules fq_default, fq, fq_nmod and fq_zech and their vector, matrix, polynomial and embedding modules compute in finite fields \mathbb{F}_{p^d}. The overview compares the representations and lists the methods used for each task; the other pages state the algorithms and prove them correct. Polynomials and matrices over finite fields mostly use the generic algorithms of the polynomial and linear algebra groups, and their factorisation is described in Factoring polynomials over finite fields.

In this section#

OverviewArithmetic in finite fieldsFLINT represents \mathbb{F}_{p^d} by Zech logarithms, by polynomials over a word-size or a multiprecision prime field, or, for d = 1, by residues; this page compares the representations, says how fq_default chooses among them, and lists the algorithms for reduction, inversion, powering, Frobenius, norm, trace, embeddings and defining polynomials.AlgorithmReduction modulo the defining polynomialElements of \mathbb{F}_p[x]/(f) are reduced after each product either by eliminating the high coefficients with the few nonzero terms of a sparse f, or by Newton division with a precomputed inverse of the reversal of f; sums of products are reduced only once.AlgorithmZech logarithmsIn a small field \mathbb{F}_q with a primitive element g, storing each element as its discrete logarithm turns multiplication into an addition modulo q - 1, and a table of the Zech logarithms Z(k) with 1 + g^k = g^{Z(k)} turns addition into one lookup; the table is built in O(q) operations, which also tests whether g is primitive.AlgorithmFrobenius map, norm, trace and rootsHow FLINT applies the Frobenius automorphism a \mapsto a^{p^e}, computes the trace from power sums given by Newton's identities and the norm as a resultant, and computes p-th roots, square roots (Tonelli–Shanks) and multiplicative orders in \mathbb{F}_{p^d}.AlgorithmEmbeddings of finite fieldsTo embed \mathbb{F}_{p^m} into \mathbb{F}_{p^n} given by unrelated defining polynomials, FLINT finds a root of the smaller field's polynomial in the larger field and expresses the embedding, and a left inverse built from the trace and the dual basis, as matrices over \mathbb{F}_p.AlgorithmDefining polynomialsWhich irreducible polynomial defines \mathbb{F}_{p^d} in FLINT: Conway polynomials from Lübeck's tables when available, otherwise polynomials with as few terms as possible (fq_nmod), random sparse irreducible polynomials (fq) or random primitive polynomials (fq_zech); with the facts about their existence that these choices rely on.
Cite this page

The FLINT team, “Finite fields,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/finite-fields/index.html (generated 2026-10-20).