Embeddings of finite fields

Let $k = \mathbb{F}_p[y]/(f_m)$ and $K = \mathbb{F}_p[x]/(f_n)$ be fields of degrees $m \mid n$. Then $K$ has a unique subfield of order $p^m$, isomorphic to $k$, but an isomorphism has to be computed: it is determined by the image of the generator $y$, which must be a root of $f_m$ in $K$, and there are $m$ such roots, giving the $m$ embeddings $k \to K$, which differ by powers of the Frobenius map. Lenstra showed that isomorphisms of finite fields can be found in deterministic polynomial time [Len1991]; practical algorithms either find a root of $f_m$ in $K$, as FLINT does, or use Kummer theory and Gauss periods to construct compatible generators without factoring [All2002] [DFRR2019]. Systems such as Magma maintain a lattice of compatible embeddings between all fields created [BCS1997b]; FLINT computes embeddings on demand and leaves compatibility to the user (Conway polynomials, Defining polynomials, provide compatible generators by construction, but fq_embed does not use this).

Finding the embedding#

fq_embed_gens returns the generator $y$ of $k$, its minimal polynomial $f_m$, and a root $\beta$ of $f_m$ in $K$. The root is found by fq_poly_factor_split_single, that is, by the root finding of gr_poly_roots_finite_field applied to $f_m$ viewed as a polynomial over $K$ (Roots of polynomials over finite fields), which splits $f_m$ (a product of $m$ distinct linear factors over $K$) by random equal-degree splitting; its cost is dominated by modular exponentiations of polynomials of degree less than $m$ over $K$ to exponents of size about $p^n$. The embedding is $\varphi(\sum c_i y^i) = \sum c_i \beta^i$.

The embedding matrix#

With respect to the bases $1, y, \ldots, y^{m-1}$ of $k$ and $1, x, \ldots, x^{n-1}$ of $K$, $\varphi$ is the $n \times m$ matrix whose columns are the coordinates of $\beta^0, \ldots, \beta^{m-1}$, the first $m$ columns of the composition matrix of $\beta$ (fq_embed_composition_matrix_sub). More generally, fq_embed_matrices accepts any generator $\gamma$ of $k$ with minimal polynomial $g$ and a root $\gamma'$ of $g$ in $K$; it then composes the matrix of $\mathbb{F}_p[z]/(g) \to K$, $z \mapsto \gamma'$, with the inverse of the matrix of $\mathbb{F}_p[z]/(g) \to k$, $z \mapsto \gamma$.

Projecting back with the trace#

A map in the other direction, $\pi: K \to k$ with $\pi \circ \varphi = \mathrm{id}$, is needed to test whether an element of $K$ lies in the image and to compute its preimage. FLINT obtains it from the relative trace $\operatorname{Tr}_{K/k'}$, where $k' = \varphi(k)$, which is $k'$-linear and surjective.

The matrix $T$ is fq_embed_mono_to_dual_matrix, computed from the power sums $\operatorname{Tr}(x^i)$ of Frobenius map, norm, trace and roots; its inverse, fq_embed_dual_to_mono_matrix, is the product of the multiplication matrix of $1/f'(x)$ (fq_embed_mul_matrix) and the Hankel matrix of the coefficients of $f$, by the second part of the lemma.

This is fq_embed_trace_matrix. Since $\operatorname{Tr}_{K/k'}$ is the multiplication by $n/m$ on $k'$, the projection is $\pi(u) = \varphi^{-1}(\operatorname{Tr}_{K/k'}(\theta u))$ for any $\theta \in K$ with $\operatorname{Tr}_{K/k'}(\theta) = 1$: $\theta = (n/m)^{-1}$ if $p \nmid n/m$, and otherwise $\theta = x^i / \operatorname{Tr}_{K/k'}(x^i)$ for a power of the generator with nonzero relative trace, which fq_embed_matrices finds by looking for a nonzero entry in the first row of the trace matrix. Then $\pi(\varphi(c)) = \varphi^{-1}(\varphi(c) \operatorname{Tr}_{K/k'}(\theta)) = c$. Using duality in this way, rather than solving a linear system for each element, follows Shoup's approach to computations with linear forms in extensions of finite fields [Sho1994] [Sho1999].

Use in FLINT#

• fq_embed_gens, _fq_embed_gens_naive: the generators.
• fq_embed_matrices: the embedding and projection matrices, from fq_embed_composition_matrix_sub, fq_embed_trace_matrix, fq_embed_mono_to_dual_matrix, fq_embed_dual_to_mono_matrix, fq_embed_mul_matrix, fq_modulus_pow_series_inv and fq_modulus_derivative_inv.
• The same functions exist for fq_nmod and fq_zech (with nmod_mat matrices); the fq_zech versions convert elements to the fq_nmod representation.

@misc{flint-doc-algorithms-finite-fields-embeddings,
  author       = {{The FLINT team}},
  title        = {{Embeddings of 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/embeddings.html},
  note         = {Generated 2026-11-02}
}