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
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
.- an element
-
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
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_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
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_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.
- two contexts
-
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
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.- two contexts
-
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 totrunc
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})\).