Computing isomorphisms and embeddings of finite fields ------------------------------------------------------------------------------- .. function:: void fq_zech_embed_gens(fq_zech_t gen_sub, fq_zech_t gen_sup, nmod_poly_t minpoly, const fq_zech_ctx_t sub_ctx, const fq_zech_ctx_t sup_ctx) Given two contexts sub_ctx and sup_ctx, such that degree(sub_ctx) divides degree(sup_ctx), compute: * an element gen_sub in sub_ctx such that gen_sub generates the finite field defined by sub_ctx, * its minimal polynomial minpoly, * a root gen_sup of minpoly inside the field defined by sup_ctx. These data uniquely define an embedding of sub_ctx into sup_ctx. .. function:: void _fq_zech_embed_gens_naive(fq_zech_t gen_sub, fq_zech_t gen_sup, nmod_poly_t minpoly, const fq_zech_ctx_t sub_ctx, const fq_zech_ctx_t sup_ctx) Given two contexts sub_ctx and sup_ctx, such that degree(sub_ctx) divides degree(sup_ctx), compute an embedding of sub_ctx into sup_ctx defined as follows: * gen_sub is the canonical generator of sup_ctx (i.e., the class of X), * minpoly is the defining polynomial of sub_ctx, * gen_sup is a root of minpoly inside the field defined by sup_ctx. .. function:: void fq_zech_embed_matrices(nmod_mat_t embed, nmod_mat_t project, const fq_zech_t gen_sub, const fq_zech_ctx_t sub_ctx, const fq_zech_t gen_sup, const fq_zech_ctx_t sup_ctx, const nmod_poly_t gen_minpoly) Given: * two contexts sub_ctx and sup_ctx, of respective degrees m and n, such that m divides n; * a generator gen_sub of sub_ctx, its minimal polynomial gen_minpoly, and a root gen_sup of gen_minpoly in sup_ctx, as returned by fq_zech_embed_gens; Compute: * the n\times m matrix embed mapping gen_sub to gen_sup, and all their powers accordingly; * an m\times n matrix project such that project \times embed is the m\times m identity matrix. .. function:: void fq_zech_embed_trace_matrix(nmod_mat_t res, const nmod_mat_t basis, const fq_zech_ctx_t sub_ctx, const fq_zech_ctx_t sup_ctx) Given: * two contexts sub_ctx and sup_ctx, of degrees m and n, such that m divides n; * an n\times m matrix basis that maps sub_ctx to an isomorphic subfield in sup_ctx; Compute the m\times n matrix of the trace from sup_ctx to sub_ctx. This matrix is computed as embed_dual_to_mono_matrix(_, sub_ctx) \times basis:sup:t \times embed_mono_to_dual_matrix(_, sup_ctx)}. **Note:** if m=n, basis represents a Frobenius, and the result is its inverse matrix. .. function:: void fq_zech_embed_composition_matrix(nmod_mat_t matrix, const fq_zech_t gen, const fq_zech_ctx_t ctx) Compute the *composition matrix* of gen. For an element a\in\mathbf{F}_{p^n}, its composition matrix is the matrix whose columns are a^0, a^1, \ldots, a^{n-1}. .. function:: void fq_zech_embed_composition_matrix_sub(nmod_mat_t matrix, const fq_zech_t gen, const fq_zech_ctx_t ctx, slong trunc) Compute the *composition matrix* of gen, truncated to trunc columns. .. function:: void fq_zech_embed_mul_matrix(nmod_mat_t matrix, const fq_zech_t gen, const fq_zech_ctx_t ctx) Compute the *multiplication matrix* of gen. For an element a in \mathbf{F}_{p^n}=\mathbf{F}_p[x], its multiplication matrix is the matrix whose columns are a, ax, \dots, ax^{n-1}. .. function:: void fq_zech_embed_mono_to_dual_matrix(nmod_mat_t res, const fq_zech_ctx_t ctx) Compute the change of basis matrix from the monomial basis of ctx to its dual basis. .. function:: void fq_zech_embed_dual_to_mono_matrix(nmod_mat_t res, const fq_zech_ctx_t ctx) Compute the change of basis matrix from the dual basis of ctx to its monomial basis. .. function:: void fq_zech_modulus_pow_series_inv(nmod_poly_t res, const fq_zech_ctx_t ctx, slong trunc) Compute the power series inverse of the reverse of the modulus of ctx up to O(x^\texttt{trunc}). .. function:: void fq_zech_modulus_derivative_inv(fq_zech_t m_prime, fq_zech_t m_prime_inv, const fq_zech_ctx_t ctx) Compute the derivative m_prime of the modulus of ctx as an element of ctx, and its inverse m_prime_inv.