# Computing isomorphisms and embeddings of finite fields¶

void fq_embed_gens(fq_t gen_sub, fq_t gen_sup, fmpz_mod_poly_t minpoly, const fq_ctx_t sub_ctx, const fq_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.

void _fq_embed_gens_naive(fq_t gen_sub, fq_t gen_sup, fmpz_mod_poly_t minpoly, const fq_ctx_t sub_ctx, const fq_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.
void fq_embed_matrices(fmpz_mod_mat_t embed, fmpz_mod_mat_t project, const fq_t gen_sub, const fq_ctx_t sub_ctx, const fq_t gen_sup, const fq_ctx_t sup_ctx, const fmpz_mod_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_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.
void fq_embed_trace_matrix(fmpz_mod_mat_t res, const fmpz_mod_mat_t basis, const fq_ctx_t sub_ctx, const fq_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$$ basist $$\times$$ embed_mono_to_dual_matrix(_, sup_ctx).

Note: if $$m=n$$, basis represents a Frobenius, and the result is its inverse matrix.

void fq_embed_composition_matrix(fmpz_mod_mat_t matrix, const fq_t gen, const fq_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}$$.

void fq_embed_composition_matrix_sub(fmpz_mod_mat_t matrix, const fq_t gen, const fq_ctx_t ctx, slong trunc)

Compute the composition matrix of gen, truncated to trunc columns.

void fq_embed_mul_matrix(fmpz_mod_mat_t matrix, const fq_t gen, const fq_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}$$.

void fq_embed_mono_to_dual_matrix(fmpz_mod_mat_t res, const fq_ctx_t ctx)

Compute the change of basis matrix from the monomial basis of ctx to its dual basis.

void fq_embed_dual_to_mono_matrix(fmpz_mod_mat_t res, const fq_ctx_t ctx)

Compute the change of basis matrix from the dual basis of ctx to its monomial basis.

void fq_modulus_pow_series_inv(fmpz_mod_poly_t res, const fq_ctx_t ctx, slong trunc)

Compute the power series inverse of the reverse of the modulus of ctx up to $$O(x^\texttt{trunc})$$.

void fq_modulus_derivative_inv(fq_t m_prime, fq_t m_prime_inv, const fq_ctx_t ctx)

Compute the derivative m_prime of the modulus of ctx as an element of ctx, and its inverse m_prime_inv.