fq_zech_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_zech_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_zech_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_zech_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_zech_embed_dual_to_mono_matrix for $k$ and $M_K$ = fq_zech_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_zech_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.