fq_zech_embed.h – Computing isomorphisms and embeddings of finite fields¶
-
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
andsup_ctx
, such thatdegree(sub_ctx)
dividesdegree(sup_ctx)
, compute:an element
gen_sub
insub_ctx
such thatgen_sub
generates the finite field defined bysub_ctx
,its minimal polynomial
minpoly
,a root
gen_sup
ofminpoly
inside the field defined bysup_ctx
.
These data uniquely define an embedding of
sub_ctx
intosup_ctx
.
-
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
andsup_ctx
, such thatdegree(sub_ctx)
dividesdegree(sup_ctx)
, compute an embedding ofsub_ctx
intosup_ctx
defined as follows:gen_sub
is the canonical generator ofsup_ctx
(i.e., the class of \(X\)),minpoly
is the defining polynomial ofsub_ctx
,gen_sup
is a root ofminpoly
inside the field defined bysup_ctx
.
-
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
andsup_ctx
, of respective degrees \(m\) and \(n\), such that \(m\) divides \(n\);a generator
gen_sub
ofsub_ctx
, its minimal polynomialgen_minpoly
, and a rootgen_sup
ofgen_minpoly
insup_ctx
, as returned byfq_zech_embed_gens
;
Compute:
the \(n\times m\) matrix
embed
mappinggen_sub
togen_sup
, and all their powers accordingly;an \(m\times n\) matrix
project
such thatproject
\(\times\)embed
is the \(m\times m\) identity matrix.
-
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
andsup_ctx
, of degrees \(m\) and \(n\), such that \(m\) divides \(n\);an \(n\times m\) matrix
basis
that mapssub_ctx
to an isomorphic subfield insup_ctx
;
Compute the \(m\times n\) matrix of the trace from
sup_ctx
tosub_ctx
.This matrix is computed as
embed_dual_to_mono_matrix(_, sub_ctx)
\(\times\)basis
t \(\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_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}\).
-
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 totrunc
columns.
-
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}\).
-
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.
-
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.
-
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})\).
-
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 ofctx
as an element ofctx
, and its inversem_prime_inv
.