Flint2-0.1.0.5: Haskell bindings for the flint library for number theory

Data.Number.Flint.Fq.NMod.Embed

Description

Synopsis

# Computing isomorphisms and embeddings of finite fields

fq_nmod_embed_gens gen_sub gen_sup minpoly sub_ctx 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.

_fq_nmod_embed_gens_naive gen_sub gen_sup minpoly sub_ctx 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.

fq_nmod_embed_matrices embed project gen_sub sub_ctx gen_sup sup_ctx 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_nmod_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.

fq_nmod_embed_trace_matrix res basis sub_ctx 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.

fq_nmod_embed_composition_matrix matrix gen 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}$$.

fq_nmod_embed_composition_matrix_sub matrix gen ctx trunc

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

fq_nmod_embed_mul_matrix matrix gen 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}).

fq_nmod_embed_mono_to_dual_matrix res ctx

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

fq_nmod_embed_dual_to_mono_matrix res ctx

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

fq_nmod_modulus_pow_series_inv res ctx trunc

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

fq_nmod_modulus_derivative_inv m_prime m_prime_inv ctx

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