1 | // -*- c++ -*- |
---|
2 | //***************************************************************************** |
---|
3 | /** @file cf_map_ext.h |
---|
4 | * |
---|
5 | * This file implements functions to map between extensions of finite fields |
---|
6 | * |
---|
7 | * @par Copyright: |
---|
8 | * (c) by The SINGULAR Team, see LICENSE file |
---|
9 | * |
---|
10 | * @author Martin Lee |
---|
11 | * @date 16.11.2009 |
---|
12 | **/ |
---|
13 | //***************************************************************************** |
---|
14 | |
---|
15 | #ifndef CF_MAP_EXT_H |
---|
16 | #define CF_MAP_EXT_H |
---|
17 | |
---|
18 | // #include "config.h" |
---|
19 | |
---|
20 | int findItem (const CFList& list, const CanonicalForm& item); |
---|
21 | |
---|
22 | CanonicalForm getItem (const CFList& list, const int& pos); |
---|
23 | |
---|
24 | /// maps a polynomial over \f$ GF(p^{k}) \f$ to a polynomial over |
---|
25 | /// \f$ GF(p^{d}) \f$ , d needs to be a multiple of k |
---|
26 | CanonicalForm GFMapUp (const CanonicalForm & F, int k); |
---|
27 | |
---|
28 | /// maps a polynomial over \f$ GF(p^{d}) \f$ to a polynomial over |
---|
29 | /// \f$ GF(p^{k})\f$ , d needs to be a multiple of k |
---|
30 | CanonicalForm GFMapDown (const CanonicalForm & F, int k); |
---|
31 | |
---|
32 | /// map F from \f$ F_{p} (\alpha ) \f$ to \f$ F_{p}(\beta ) \f$. |
---|
33 | /// We assume \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$. |
---|
34 | CanonicalForm |
---|
35 | mapUp (const CanonicalForm& F, ///<[in] poly over \f$ F_{p} (\alpha ) \f$ |
---|
36 | const Variable& alpha, ///<[in] alg. variable |
---|
37 | const Variable& beta, ///<[in] alg. variable |
---|
38 | const CanonicalForm& prim_elem, ///<[in] primitive element of \f$ F_{p} (\alpha ) \f$ |
---|
39 | const CanonicalForm& im_prim_elem,///<[in] image of prim_elem in \f$ F_{p} (\beta ) \f$ |
---|
40 | CFList& source, ///<[in,out] look up lists |
---|
41 | CFList& dest ///<[in,out] look up lists |
---|
42 | ); |
---|
43 | |
---|
44 | /// map F from \f$ F_{p} (\beta ) \f$ to \f$ F_{p}(\alpha ) \f$. |
---|
45 | /// We assume \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and F in |
---|
46 | /// \f$ F_{p}(\alpha ) \f$. |
---|
47 | CanonicalForm |
---|
48 | mapDown (const CanonicalForm& F, ///<[in] poly over \f$ F_{p} (\beta ) \f$ |
---|
49 | const CanonicalForm& prim_elem, ///<[in] primitive element of \f$ F_{p} (\alpha ) \f$ |
---|
50 | const CanonicalForm& im_prim_elem,///<[in] image of prim_elem in \f$ F_{p} (\beta ) \f$ |
---|
51 | const Variable& alpha, ///<[in] alg. variable |
---|
52 | CFList& source, ///<[in,out] look up lists |
---|
53 | CFList& dest ///<[in,out] look up lists |
---|
54 | ); |
---|
55 | |
---|
56 | /// determine a primitive element of \f$ F_{p} (\alpha ) \f$, |
---|
57 | /// \f$ \beta \f$ is a primitive element of a field which is isomorphic to |
---|
58 | /// \f$ F_{p}(\alpha ) \f$ |
---|
59 | CanonicalForm |
---|
60 | primitiveElement (const Variable& alpha, ///< [in] some algebraic variable |
---|
61 | Variable& beta, ///< [in,out] s.a. |
---|
62 | bool& fail ///< [in,out] failure due to integer |
---|
63 | ///< factorization failure? |
---|
64 | ); |
---|
65 | |
---|
66 | /// compute the image of a primitive element of \f$ F_{p} (\alpha ) \f$ |
---|
67 | /// in \f$ F_{p}(\beta ) \f$. |
---|
68 | /// We assume \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$. |
---|
69 | CanonicalForm |
---|
70 | mapPrimElem (const CanonicalForm& prim_elem, ///< [in] primitive element |
---|
71 | const Variable& alpha, ///< [in] algebraic variable |
---|
72 | const Variable& beta ///< [in] algebraic variable |
---|
73 | ); |
---|
74 | |
---|
75 | /// changes representation by primitive element to representation by residue |
---|
76 | /// classes modulo a Conway polynomial |
---|
77 | CanonicalForm GF2FalphaRep (const CanonicalForm& F, ///< [in] some poly over GF |
---|
78 | const Variable& alpha ///< [in] root of a Conway |
---|
79 | ///< poly |
---|
80 | ); |
---|
81 | |
---|
82 | /// change representation by residue classes modulo a Conway polynomial |
---|
83 | /// to representation by primitive element |
---|
84 | CanonicalForm Falpha2GFRep (const CanonicalForm& F ///<[in] some poly over |
---|
85 | ///< F_p(alpha) where alpha |
---|
86 | ///< is a root of a Conway |
---|
87 | ///< poly |
---|
88 | ); |
---|
89 | |
---|
90 | /// map from \f$ F_p(\alpha) \f$ to \f$ F_p(\beta) \f$ such that |
---|
91 | /// \f$ F\in F_p(\alpha) \f$ is mapped onto \f$ \beta \f$ |
---|
92 | /// |
---|
93 | /// @return @a map returns the image of @a primElem such that the above |
---|
94 | /// described properties hold |
---|
95 | CanonicalForm |
---|
96 | map (const CanonicalForm& primElem,///< [in] primitive element of |
---|
97 | ///< \f$ F_p (\alpha) \f$ |
---|
98 | const Variable& alpha, ///< [in] algebraic variable |
---|
99 | const CanonicalForm& F, ///< [in] an element of \f$ F_p (\alpha) \f$, |
---|
100 | ///< whose minimal polynomial defines a field |
---|
101 | ///< extension of \f$ F_p \f$ of degree |
---|
102 | ///< \f$ F_p (\alpha):F_p \f$ |
---|
103 | const Variable& beta ///< [in] algebraic variable, root of \a F's |
---|
104 | ///< minimal polynomial |
---|
105 | ); |
---|
106 | |
---|
107 | /// compute minimal polynomial of \f$ F\in F_p(\alpha)\backslash F_p \f$ via NTL |
---|
108 | /// |
---|
109 | /// @return @a findMinPoly computes the minimal polynomial of F |
---|
110 | CanonicalForm |
---|
111 | findMinPoly (const CanonicalForm& F, ///< [in] an element of |
---|
112 | ///< \f$ F_p(\alpha)\backslash F_p \f$ |
---|
113 | const Variable& alpha ///< [in] algebraic variable |
---|
114 | ); |
---|
115 | |
---|
116 | #endif |
---|