cf_map_ext.h
Go to the documentation of this file.
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$.
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$.
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$
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$.
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
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
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
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:170
factory's class for variables
Definition: variable.h:32
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
factory's main class
Definition: canonicalform.h:75
CanonicalForm mapUp(const CanonicalForm &F, const Variable &alpha, const Variable &beta, const CanonicalForm &prim_elem, const CanonicalForm &im_prim_elem, CFList &source, CFList &dest)
map F from to . We assume .
Definition: cf_map_ext.cc:366
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm mapPrimElem(const CanonicalForm &prim_elem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
Variable beta
Definition: facAbsFact.cc:99
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:243
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
Definition: cf_map_ext.cc:400
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to ...
Definition: cf_map_ext.cc:310
CanonicalForm mapDown(const CanonicalForm &F, const CanonicalForm &prim_elem, const CanonicalForm &im_prim_elem, const Variable &alpha, CFList &source, CFList &dest)
map F from to . We assume and F in .
Definition: cf_map_ext.cc:358
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
Definition: cf_map_ext.cc:434