1
2Computing isomorphisms and embeddings of finite fields
3--------------------------------------------------------------------------------
4
5
6.. function:: void fq_nmod_embed_gens(fq_nmod_t gen_sub, fq_nmod_t gen_sup, nmod_poly_t minpoly, const fq_nmod_ctx_t sub_ctx, const fq_nmod_ctx_t sup_ctx)
7
8    Given two contexts ``sub_ctx`` and ``sup_ctx``, such that
9    ``degree(sub_ctx)`` divides ``degree(sup_ctx)``, compute:
10
11    * an element ``gen_sub`` in ``sub_ctx`` such that
12      ``gen_sub`` generates the finite field defined by
13      ``sub_ctx``,
14    * its minimal polynomial ``minpoly``,
15    * a root ``gen_sup`` of ``minpoly`` inside the field
16      defined by ``sup_ctx``.
17
18    These data uniquely define an embedding of ``sub_ctx`` into
19    ``sup_ctx``.
20
21
22.. function:: void _fq_nmod_embed_gens_naive(fq_nmod_t gen_sub, fq_nmod_t gen_sup, nmod_poly_t minpoly, const fq_nmod_ctx_t sub_ctx, const fq_nmod_ctx_t sup_ctx)
23
24    Given two contexts ``sub_ctx`` and ``sup_ctx``, such that
25    ``degree(sub_ctx)`` divides ``degree(sup_ctx)``, compute an
26    embedding of ``sub_ctx`` into ``sup_ctx`` defined as follows:
27
28    * ``gen_sub`` is the canonical generator of ``sup_ctx``
29      (i.e., the class of `X`),
30    * ``minpoly`` is the defining polynomial of ``sub_ctx``,
31    * ``gen_sup`` is a root of ``minpoly`` inside the field
32      defined by ``sup_ctx``.
33
34.. function:: void fq_nmod_embed_matrices(nmod_mat_t embed, nmod_mat_t project, const fq_nmod_t gen_sub, const fq_nmod_ctx_t sub_ctx, const fq_nmod_t gen_sup, const fq_nmod_ctx_t sup_ctx, const nmod_poly_t gen_minpoly)
35
36    Given:
37
38    * two contexts ``sub_ctx`` and ``sup_ctx``, of
39      respective degrees `m` and `n`, such that `m` divides `n`;
40    * a generator ``gen_sub`` of ``sub_ctx``, its minimal
41      polynomial ``gen_minpoly``, and a root ``gen_sup`` of
42      ``gen_minpoly`` in ``sup_ctx``, as returned by
43      ``fq_nmod_embed_gens``;
44
45    Compute:
46
47    * the `n\times m` matrix ``embed`` mapping ``gen_sub``
48      to ``gen_sup``, and all their powers accordingly;
49    * an `m\times n` matrix ``project`` such that
50      ``project`` `\times` ``embed`` is the `m\times m` identity
51      matrix.
52
53.. function:: void fq_nmod_embed_trace_matrix(nmod_mat_t res, const nmod_mat_t basis, const fq_nmod_ctx_t sub_ctx, const fq_nmod_ctx_t sup_ctx)
54
55    Given:
56
57    * two contexts ``sub_ctx`` and ``sup_ctx``, of degrees
58      `m` and `n`, such that `m` divides `n`;
59    * an `n\times m` matrix ``basis`` that maps ``sub_ctx``
60      to an isomorphic subfield in ``sup_ctx``;
61
62    Compute the `m\times n` matrix of the trace from ``sup_ctx`` to
63    ``sub_ctx``.
64
65    This matrix is computed as
66
67    ``embed_dual_to_mono_matrix(_, sub_ctx)``
68    `\times` ``basis``:sup:`t` `\times`
69    ``embed_mono_to_dual_matrix(_, sup_ctx)}``.
70
71    **Note:** if
72    `m=n`, ``basis`` represents a Frobenius, and the result is its
73    inverse matrix.
74
75.. function:: void fq_nmod_embed_composition_matrix(nmod_mat_t matrix, const fq_nmod_t gen, const fq_nmod_ctx_t ctx)
76
77    Compute the *composition matrix* of ``gen``.
78
79    For an element `a\in\mathbf{F}_{p^n}`, its composition matrix is the
80    matrix whose columns are `a^0, a^1, \ldots, a^{n-1}`.
81
82.. function:: void fq_nmod_embed_composition_matrix_sub(nmod_mat_t matrix, const fq_nmod_t gen, const fq_nmod_ctx_t ctx, slong trunc)
83
84    Compute the *composition matrix* of ``gen``, truncated to
85    ``trunc`` columns.
86
87.. function:: void fq_nmod_embed_mul_matrix(nmod_mat_t matrix, const fq_nmod_t gen, const fq_nmod_ctx_t ctx)
88
89    Compute the *multiplication matrix* of ``gen``.
90
91    For an element `a` in `\mathbf{F}_{p^n}=\mathbf{F}_p[x]`, its
92    multiplication matrix is the matrix whose columns are `a, ax,
93    \dots, ax^{n-1}`.
94
95.. function:: void fq_nmod_embed_mono_to_dual_matrix(nmod_mat_t res, const fq_nmod_ctx_t ctx)
96
97    Compute the change of basis matrix from the monomial basis of
98    ``ctx`` to its dual basis.
99
100.. function:: void fq_nmod_embed_dual_to_mono_matrix(nmod_mat_t res, const fq_nmod_ctx_t ctx)
101
102    Compute the change of basis matrix from the dual basis of
103    ``ctx`` to its monomial basis.
104
105.. function:: void fq_nmod_modulus_pow_series_inv(nmod_poly_t res, const fq_nmod_ctx_t ctx, slong trunc)
106
107    Compute the power series inverse of the reverse of the modulus of
108    ``ctx`` up to `O(x^\texttt{trunc})`.
109
110.. function:: void fq_nmod_modulus_derivative_inv(fq_nmod_t m_prime, fq_nmod_t m_prime_inv, const fq_nmod_ctx_t ctx)
111
112    Compute the derivative ``m_prime`` of the modulus of ``ctx``
113    as an element of ``ctx``, and its inverse ``m_prime_inv``.
114