 |
My Project
UNKNOWN_GIT_VERSION
|
This file implements functions to map between extensions of finite fields.
More...
#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "canonicalform.h"
#include "cf_util.h"
#include "imm.h"
#include "cf_iter.h"
#include "NTLconvert.h"
#include "cf_cyclo.h"
#include "cf_map_ext.h"
Go to the source code of this file.
|
int | findItem (const CFList &list, const CanonicalForm &item) |
| helper function More...
|
|
CanonicalForm | getItem (const CFList &list, const int &pos) |
| helper function More...
|
|
static CanonicalForm | mapUp (const Variable &alpha, const Variable &beta) |
| and is a primitive element, returns the image of More...
|
|
static CanonicalForm | mapDown (const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest) |
| the CanonicalForm G is the output of map_up, returns F considered as an element over , WARNING: make sure coefficients of F are really elements of a subfield of which is isomorphic to More...
|
|
static CanonicalForm | GF2FalphaHelper (const CanonicalForm &F, const Variable &alpha) |
| helper function More...
|
|
CanonicalForm | GF2FalphaRep (const CanonicalForm &F, const Variable &alpha) |
| changes representation by primitive element to representation by residue classes modulo a Conway polynomial More...
|
|
CanonicalForm | Falpha2GFRep (const CanonicalForm &F) |
| change representation by residue classes modulo a Conway polynomial to representation by primitive element More...
|
|
static CanonicalForm | GFPowUp (const CanonicalForm &F, int k) |
| GF_map_up helper. More...
|
|
CanonicalForm | GFMapUp (const CanonicalForm &F, int k) |
| maps a polynomial over to a polynomial over , d needs to be a multiple of k More...
|
|
static CanonicalForm | GFPowDown (const CanonicalForm &F, int k) |
| GFMapDown helper. More...
|
|
CanonicalForm | GFMapDown (const CanonicalForm &F, int k) |
| maps a polynomial over to a polynomial over , d needs to be a multiple of k More...
|
|
static CanonicalForm | mapUp (const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, const CanonicalForm &H, CFList &source, CFList &dest) |
| map F in which is generated by G into some which is generated by H More...
|
|
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 More...
|
|
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 . More...
|
|
CanonicalForm | mapUp (const CanonicalForm &F, const Variable &alpha, const Variable &, const CanonicalForm &prim_elem, const CanonicalForm &im_prim_elem, CFList &source, CFList &dest) |
| map F from to . We assume . More...
|
|
CanonicalForm | mapPrimElem (const CanonicalForm &primElem, const Variable &alpha, const Variable &beta) |
| compute the image of a primitive element of in . We assume . More...
|
|
CanonicalForm | map (const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta) |
| map from to such that is mapped onto More...
|
|
CanonicalForm | findMinPoly (const CanonicalForm &F, const Variable &alpha) |
| compute minimal polynomial of via NTL More...
|
|
This file implements functions to map between extensions of finite fields.
- Copyright:
- (c) by The SINGULAR Team, see LICENSE file
- Author
- Martin Lee
- Date
- 16.11.2009
Definition in file cf_map_ext.cc.
◆ Falpha2GFRep()
change representation by residue classes modulo a Conway polynomial to representation by primitive element
- Parameters
-
[in] | F | some poly over F_p(alpha) where alpha is a root of a Conway poly |
Definition at line 170 of file cf_map_ext.cc.
◆ findItem()
helper function
Definition at line 37 of file cf_map_ext.cc.
42 if (
i.getItem() == item)
◆ findMinPoly()
compute minimal polynomial of
via NTL
- Returns
- findMinPoly computes the minimal polynomial of F
- Parameters
-
[in] | F | an element of |
[in] | alpha | algebraic variable |
Definition at line 434 of file cf_map_ext.cc.
447 zz_pE::init (NTLMipo);
449 pows.SetLength (2*d);
453 zz_pE NTLFE= to_zz_pE (NTLF);
455 for (
int i= 0;
i < 2*d;
i++)
458 buf.rep.SetLength (d);
459 pows [
i]=
buf.rep[0];
464 MinPolySeq (NTLMinPoly, pows, d);
◆ getItem()
◆ GF2FalphaHelper()
◆ GF2FalphaRep()
changes representation by primitive element to representation by residue classes modulo a Conway polynomial
- Parameters
-
[in] | F | some poly over GF |
[in] | alpha | root of a Conway poly |
Definition at line 162 of file cf_map_ext.cc.
◆ GFMapDown()
maps a polynomial over
to a polynomial over
, d needs to be a multiple of k
Definition at line 243 of file cf_map_ext.cc.
246 ASSERT (d %
k == 0,
"multiple of GF degree expected");
248 int ext_field_size=
ipower (
p, d);
250 int diff= (ext_field_size - 1)/(field_size - 1);
◆ GFMapUp()
maps a polynomial over
to a polynomial over
, d needs to be a multiple of k
Definition at line 207 of file cf_map_ext.cc.
210 ASSERT (d%
k == 0,
"multiple of GF degree expected");
212 int ext_field_size=
ipower (
p, d);
214 int diff= (ext_field_size - 1)/(field_size - 1);
◆ GFPowDown()
◆ GFPowUp()
◆ map()
map from
to
such that
is mapped onto
- Returns
- map returns the image of primElem such that the above described properties hold
- Parameters
-
[in] | primElem | primitive element of |
[in] | alpha | algebraic variable |
[in] | F | an element of , whose minimal polynomial defines a field extension of of degree |
[in] | beta | algebraic variable, root of F's minimal polynomial |
Definition at line 400 of file cf_map_ext.cc.
417 zz_pE::init (NTL_mipo);
420 vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
422 for (
long i= 0;
i < roots.length();
i++)
424 if (
power (roots [
i], order)== NTLBeta)
◆ mapDown() [1/2]
◆ mapDown() [2/2]
the CanonicalForm G is the output of map_up, returns F considered as an element over
, WARNING: make sure coefficients of F are really elements of a subfield of
which is isomorphic to
Definition at line 90 of file cf_map_ext.cc.
102 if (
degree(F) == 0)
return F;
118 ASSERT (counter >=
bound,
"alpha is not primitive");
122 dest.
append (alpha_power);
125 alpha_power=
getItem (dest, pos);
◆ mapPrimElem()
compute the image of a primitive element of
in
. We assume
.
- Parameters
-
[in] | primElem | primitive element |
[in] | alpha | algebraic variable |
[in] | beta | algebraic variable |
Definition at line 377 of file cf_map_ext.cc.
380 if (primElem ==
alpha)
392 zz_pE::init (NTLMipo);
394 zz_pE root= FindRoot (NTLPrimElemMipo);
◆ mapUp() [1/3]
map F in
which is generated by G into some
which is generated by H
Definition at line 257 of file cf_map_ext.cc.
270 if (
degree(F) <= 0)
return F;
286 ASSERT (counter <=
bound,
"alpha is not primitive");
◆ mapUp() [2/3]
map F from
to
. We assume
.
- Parameters
-
[in] | F | poly over |
[in] | alpha | alg. variable |
[in] | prim_elem | primitive element of |
[in] | im_prim_elem | image of prim_elem in |
[in,out] | source | look up lists |
[in,out] | dest | look up lists |
Definition at line 366 of file cf_map_ext.cc.
370 if (prim_elem ==
alpha)
371 return F (im_prim_elem,
alpha);
372 return mapUp (F, prim_elem,
alpha, im_prim_elem, source, dest);
◆ mapUp() [3/3]
and
is a primitive element, returns the image of
Definition at line 67 of file cf_map_ext.cc.
76 zz_pE::init (NTL_mipo);
78 zz_pE root= FindRoot (NTL_alpha_mipo);
◆ primitiveElement()
determine a primitive element of
,
is a primitive element of a field which is isomorphic to
- Parameters
-
[in] | alpha | some algebraic variable |
[in,out] | beta | s.a. |
[in,out] | fail | failure due to integer factorization failure? |
Definition at line 310 of file cf_map_ext.cc.
312 bool primitive=
false;
334 bool initialized=
false;
337 BuildIrred (NTL_mipo, d);
350 zz_pE::init (alpha_mipo);
351 zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
352 zz_pE root= FindRoot (NTL_beta_mipo);
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
class to iterate through CanonicalForm's
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
virtual class for internal CanonicalForm's
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
#define ASSERT(expression, message)
int status int void * buf
bool isPrimitive(const Variable &alpha, bool &fail)
checks if alpha is a primitive element, alpha is assumed to be an algebraic variable over some finite...
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
void prune(Variable &alpha)
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
int ipower(int b, int m)
int ipower ( int b, int m )
gmp_float exp(const gmp_float &a)
static long imm2int(const InternalCF *const imm)
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
int findItem(const CFList &list, const CanonicalForm &item)
helper function
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
InternalCF * int2imm_gf(long i)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function