fq_embed.h

Given contexts for fields k = sub_ctx of degree m and K = sup_ctx of degree n with m \mid n, computes a generator gen_sub of k over \mathbb{F}_p, its minimal polynomial minpoly, and a root gen_sup of minpoly in K. These data define the embedding k \to K that maps gen_sub to gen_sup.

Computes the data of fq_embed_gens as follows: gen_sub is the generator x of sub_ctx, minpoly is the defining polynomial of sub_ctx, and gen_sup is a root of it in sup_ctx, found with fq_poly_factor_split_single, that is, by root finding for a polynomial of degree m over K. Requires m > 1 to divide n.

Given the output of fq_embed_gens for fields k = sub_ctx and K = sup_ctx of degrees m \mid n, computes the n \times m matrix embed of the embedding \varphi: k \to K that maps gen_sub to gen_sup, and an m \times n matrix project of a k-linear projection \pi: K \to k with \pi \circ \varphi = \mathrm{id}, so that \mathit{project} \cdot \mathit{embed} is the m \times m identity. The matrices act on column vectors of coordinates in the monomial bases.

Given contexts for k = sub_ctx and K = sup_ctx of degrees m \mid n and the n \times m matrix basis of an embedding \varphi: k \to K, sets res to the m \times n matrix of the map y \mapsto \varphi^{-1}(\operatorname{Tr}_{K/\varphi(k)}(y)). It is computed as D_k \cdot \mathit{basis}^T \cdot M_K, with D_k = fq_embed_dual_to_mono_matrix for k and M_K = fq_embed_mono_to_dual_matrix for K. For m = n the result is the inverse of basis.

Set matrix to the composition matrix of the element a = gen of a field of degree d: the d \times d matrix whose columns are the coordinates of a^0, a^1, \ldots, a^{d-1}, which maps the coordinates of a polynomial g of degree less than d to those of g(a). The _sub version computes only the first trunc \le d columns, into a d \times \mathit{trunc} matrix.

Sets the d \times d matrix matrix to the matrix of multiplication by a = gen, whose columns are the coordinates of a, ax, \ldots, ax^{d-1}. The defining polynomial need not be monic.

Sets the d \times d matrix res to the change of basis from the monomial basis 1, x, \ldots, x^{d-1} to its dual basis with respect to the trace form (u, v) \mapsto \operatorname{Tr}(uv): the Hankel matrix with entries \operatorname{Tr}(x^{i+j}), computed from the power series expansion of \operatorname{rev}(f')/\operatorname{rev}(f) (Newton's identities). Mapping a coordinate vector of y by this matrix gives the traces \operatorname{Tr}(y x^i).

Sets the d \times d matrix res to the inverse of fq_embed_mono_to_dual_matrix. By Euler's formula the dual basis of 1, x, \ldots, x^{d-1} is b_0 / f'(x), \ldots, b_{d-1} / f'(x), where f(X)/(X - x) = \sum b_j X^j, so the matrix is the product of the multiplication matrix of 1/f'(x) and the Hankel matrix of the coefficients of f.

Sets res to the inverse of the reversal of the defining polynomial, as a power series modulo x^{\mathit{trunc}}.

Sets m_prime to f'(x), the derivative of the defining polynomial evaluated at the generator, and m_prime_inv to its inverse. f'(x) \ne 0 because f is irreducible, hence separable.