FLINT3.7.0-dev
/
Algorithm

Embeddings of finite fields

Cost
One root finding of a degree-m polynomial over \mathbb{F}_{p^n}, plus O(n^3) operations in \mathbb{F}_p for the matrices.

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.

Lemma 1. Let L = \mathbb{F}_p[x]/(f) with \deg f = d, and let T be the d \times d matrix with entries T_{ij} = \operatorname{Tr}(x^{i+j}). Then T is invertible, and for u \in L with coordinate vector \mathbf{u}, T\mathbf{u} = (\operatorname{Tr}(u x^i))_{i < d}. Moreover, if f(X)/(X - x) = \sum_{j < d} b_j X^j in L[X], then the basis dual to 1, x, \ldots, x^{d-1} for the trace form is b_0/f'(x), \ldots, b_{d-1}/f'(x).

Proof. The trace form (u, v) \mapsto \operatorname{Tr}(uv) is nondegenerate because L/\mathbb{F}_p is separable, so its Gram matrix T in the monomial basis is invertible, and (T\mathbf{u})_i = \sum_j \operatorname{Tr}(x^{i+j}) u_j = \operatorname{Tr}(x^i u). The second statement is Euler's formula for the dual basis [LN1997] (a consequence of Lagrange interpolation at the conjugates of x).

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.

Proposition 2. Let B be the n \times m matrix of an embedding \varphi: k \to K, T_K the matrix of the trace form of K and D_k the inverse of that of k. Then D_k B^T T_K is the matrix of \varphi^{-1} \circ \operatorname{Tr}_{K/k'}.

Proof. For u \in K, T_K \mathbf{u} = (\operatorname{Tr}_{K/\mathbb{F}_p}(u x^i))_i, so B^T T_K \mathbf{u} = (\operatorname{Tr}_{K/\mathbb{F}_p}(u \varphi(y^j)))_{j < m}, because column j of B is the coordinate vector of \varphi(y^j). By transitivity of the trace and k'-linearity of \operatorname{Tr}_{K/k'}, \operatorname{Tr}_{K/\mathbb{F}_p}(u \varphi(y^j)) = \operatorname{Tr}_{k'/\mathbb{F}_p}(\varphi(y^j) \operatorname{Tr}_{K/k'}(u)) = \operatorname{Tr}_{k/\mathbb{F}_p}(y^j w) with w = \varphi^{-1}(\operatorname{Tr}_{K/k'}(u)). These are the dual coordinates of w in k, and D_k converts them to monomial coordinates by Lemma 1.

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#

Referenced from#

References#

  • [Len1991] H. W. Lenstra, Jr. Finding isomorphisms between finite fields. Mathematics of Computation 56 (1991), 329–347.
  • [All2002] B. Allombert. Explicit computation of isomorphisms between finite fields. Finite Fields and Their Applications 8:3 (2002), 332–342.
  • [DFRR2019] L. De Feo, H. Randriam and É. Rousseau. Standard lattices of compatibly embedded finite fields. Proceedings of ISSAC 2019, ACM, 122–130.
  • [BCS1997b] W. Bosma, J. Cannon and A. Steel. Lattices of compatibly embedded finite fields. Journal of Symbolic Computation 24:3–4 (1997), 351–369.
  • [LN1997] R. Lidl and H. Niederreiter. Finite Fields. Second edition, Encyclopedia of Mathematics and its Applications 20, Cambridge University Press, 1997.
  • [Sho1994] V. Shoup. Fast construction of irreducible polynomials over finite fields. Journal of Symbolic Computation 17:5 (1994), 371–391.
  • [Sho1999] V. Shoup. Efficient computation of minimal polynomials in algebraic extensions of finite fields. Proceedings of ISSAC 1999, ACM, 53–58.
Cite this page

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