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