1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
.. _fq-zech-embed:
**fq_zech_embed.h** -- Computing isomorphisms and embeddings of finite fields
-------------------------------------------------------------------------------
.. function:: 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`` 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``.
.. function:: 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`` 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``.
.. function:: 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`` 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_zech_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.
.. function:: 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`` 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` ``basis``:sup:`t` `\times`
``embed_mono_to_dual_matrix(_, sup_ctx)}``.
**Note:** if
`m=n`, ``basis`` represents a Frobenius, and the result is its
inverse matrix.
.. function:: 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}`.
.. function:: 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 to
``trunc`` columns.
.. function:: 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}`.
.. function:: 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.
.. function:: 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.
.. function:: 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})`.
.. function:: 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 of ``ctx``
as an element of ``ctx``, and its inverse ``m_prime_inv``.
|
