My Project  UNKNOWN_GIT_VERSION
Functions
cf_map_ext.h File Reference

This file implements functions to map between extensions of finite fields. More...

Go to the source code of this file.

Functions

int findItem (const CFList &list, const CanonicalForm &item)
 helper function More...
 
CanonicalForm getItem (const CFList &list, const int &pos)
 helper function More...
 
CanonicalForm GFMapUp (const CanonicalForm &F, int k)
 maps a polynomial over $ GF(p^{k}) $ to a polynomial over $ GF(p^{d}) $ , d needs to be a multiple of k More...
 
CanonicalForm GFMapDown (const CanonicalForm &F, int k)
 maps a polynomial over $ GF(p^{d}) $ to a polynomial over $ GF(p^{k})$ , d needs to be a multiple of k More...
 
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 $ F_{p} (\alpha ) $ to $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $. 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 $ F_{p} (\beta ) $ to $ F_{p}(\alpha ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and F in $ F_{p}(\alpha ) $. More...
 
CanonicalForm primitiveElement (const Variable &alpha, Variable &beta, bool &fail)
 determine a primitive element of $ F_{p} (\alpha ) $, $ \beta $ is a primitive element of a field which is isomorphic to $ F_{p}(\alpha ) $ More...
 
CanonicalForm mapPrimElem (const CanonicalForm &prim_elem, const Variable &alpha, const Variable &beta)
 compute the image of a primitive element of $ F_{p} (\alpha ) $ in $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $. 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...
 
CanonicalForm map (const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
 map from $ F_p(\alpha) $ to $ F_p(\beta) $ such that $ F\in F_p(\alpha) $ is mapped onto $ \beta $ More...
 
CanonicalForm findMinPoly (const CanonicalForm &F, const Variable &alpha)
 compute minimal polynomial of $ F\in F_p(\alpha)\backslash F_p $ via NTL More...
 

Detailed Description

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.h.

Function Documentation

◆ Falpha2GFRep()

CanonicalForm Falpha2GFRep ( const CanonicalForm F)

change representation by residue classes modulo a Conway polynomial to representation by primitive element

Parameters
[in]Fsome poly over F_p(alpha) where alpha is a root of a Conway poly

Definition at line 170 of file cf_map_ext.cc.

171 {
173  InternalCF* buf;
174 
175  if (F.inCoeffDomain())
176  {
177  if (F.inBaseDomain())
178  return F.mapinto();
179  else
180  {
181  for (CFIterator i= F; i.hasTerms(); i++)
182  {
183  buf= int2imm_gf (i.exp());
184  result += i.coeff().mapinto()*CanonicalForm (buf);
185  }
186  }
187  return result;
188  }
189  for (CFIterator i= F; i.hasTerms(); i++)
190  result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
191  return result;
192 }

◆ findItem()

int findItem ( const CFList list,
const CanonicalForm item 
)

helper function

Definition at line 37 of file cf_map_ext.cc.

38 {
39  int result= 1;
40  for (CFListIterator i= list; i.hasItem(); i++, result++)
41  {
42  if (i.getItem() == item)
43  return result;
44  }
45  return 0;
46 }

◆ findMinPoly()

CanonicalForm findMinPoly ( const CanonicalForm F,
const Variable alpha 
)

compute minimal polynomial of $ F\in F_p(\alpha)\backslash F_p $ via NTL

Returns
findMinPoly computes the minimal polynomial of F
Parameters
[in]Fan element of $ F_p(\alpha)\backslash F_p $
[in]alphaalgebraic variable

Definition at line 434 of file cf_map_ext.cc.

435 {
436  ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
437 
439  {
441  zz_p::init (getCharacteristic());
442  }
443  zz_pX NTLF= convertFacCF2NTLzzpX (F);
444  int d= degree (getMipo (alpha));
445 
446  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
447  zz_pE::init (NTLMipo);
448  vec_zz_p pows;
449  pows.SetLength (2*d);
450 
451  zz_pE powNTLF;
452  set (powNTLF);
453  zz_pE NTLFE= to_zz_pE (NTLF);
454  zz_pX buf;
455  for (int i= 0; i < 2*d; i++)
456  {
457  buf= rep (powNTLF);
458  buf.rep.SetLength (d);
459  pows [i]= buf.rep[0];
460  powNTLF *= NTLFE;
461  }
462 
463  zz_pX NTLMinPoly;
464  MinPolySeq (NTLMinPoly, pows, d);
465 
466  return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
467 }

◆ getItem()

CanonicalForm getItem ( const CFList list,
const int &  pos 
)

helper function

Definition at line 49 of file cf_map_ext.cc.

50 {
51  int j= 1;
52  if ((pos > 0) && (pos <= list.length()))
53  {
54  for (CFListIterator i= list; j <= pos; i++, j++)
55  {
56  if (j == pos)
57  return i.getItem();
58  }
59  }
60  return 0;
61 }

◆ GF2FalphaRep()

CanonicalForm GF2FalphaRep ( const CanonicalForm F,
const Variable alpha 
)

changes representation by primitive element to representation by residue classes modulo a Conway polynomial

Parameters
[in]Fsome poly over GF
[in]alpharoot of a Conway poly

Definition at line 162 of file cf_map_ext.cc.

163 {
166  prune (beta);
167  return result;
168 }

◆ GFMapDown()

CanonicalForm GFMapDown ( const CanonicalForm F,
int  k 
)

maps a polynomial over $ GF(p^{d}) $ to a polynomial over $ GF(p^{k})$ , d needs to be a multiple of k

Definition at line 243 of file cf_map_ext.cc.

244 {
245  int d= getGFDegree();
246  ASSERT (d % k == 0, "multiple of GF degree expected");
247  int p= getCharacteristic();
248  int ext_field_size= ipower (p, d);
249  int field_size= ipower ( p, k);
250  int diff= (ext_field_size - 1)/(field_size - 1);
251  return GFPowDown (F, diff);
252 }

◆ GFMapUp()

CanonicalForm GFMapUp ( const CanonicalForm F,
int  k 
)

maps a polynomial over $ GF(p^{k}) $ to a polynomial over $ GF(p^{d}) $ , d needs to be a multiple of k

Definition at line 207 of file cf_map_ext.cc.

208 {
209  int d= getGFDegree();
210  ASSERT (d%k == 0, "multiple of GF degree expected");
211  int p= getCharacteristic();
212  int ext_field_size= ipower (p, d);
213  int field_size= ipower ( p, k);
214  int diff= (ext_field_size - 1)/(field_size - 1);
215  return GFPowUp (F, diff);
216 }

◆ map()

CanonicalForm map ( const CanonicalForm primElem,
const Variable alpha,
const CanonicalForm F,
const Variable beta 
)

map from $ F_p(\alpha) $ to $ F_p(\beta) $ such that $ F\in F_p(\alpha) $ is mapped onto $ \beta $

Returns
map returns the image of primElem such that the above described properties hold
Parameters
[in]primElemprimitive element of $ F_p (\alpha) $
[in]alphaalgebraic variable
[in]Fan element of $ F_p (\alpha) $, whose minimal polynomial defines a field extension of $ F_p $ of degree $ F_p (\alpha):F_p $
[in]betaalgebraic variable, root of F's minimal polynomial

Definition at line 400 of file cf_map_ext.cc.

402 {
403  CanonicalForm G= F;
404  int order= 0;
405  while (!G.isOne())
406  {
407  G /= primElem;
408  order++;
409  }
410  int p= getCharacteristic ();
411  if (fac_NTL_char != p)
412  {
413  fac_NTL_char= p;
414  zz_p::init (p);
415  }
416  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
417  zz_pE::init (NTL_mipo);
418  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
419  zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
420  vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
421  long ind=-1;
422  for (long i= 0; i < roots.length(); i++)
423  {
424  if (power (roots [i], order)== NTLBeta)
425  {
426  ind= i;
427  break;
428  }
429  }
430  return (convertNTLzzpE2CF (roots[ind], beta));
431 }

◆ mapDown()

CanonicalForm mapDown ( const CanonicalForm F,
const CanonicalForm prim_elem,
const CanonicalForm im_prim_elem,
const Variable alpha,
CFList source,
CFList dest 
)

map F from $ F_{p} (\beta ) $ to $ F_{p}(\alpha ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and F in $ F_{p}(\alpha ) $.

Parameters
[in]Fpoly over $ F_{p} (\beta ) $
[in]prim_elemprimitive element of $ F_{p} (\alpha ) $
[in]im_prim_elemimage of prim_elem in $ F_{p} (\beta ) $
[in]alphaalg. variable
[in,out]sourcelook up lists
[in,out]destlook up lists

Definition at line 358 of file cf_map_ext.cc.

361 {
362  return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
363 }

◆ mapPrimElem()

CanonicalForm mapPrimElem ( const CanonicalForm prim_elem,
const Variable alpha,
const Variable beta 
)

compute the image of a primitive element of $ F_{p} (\alpha ) $ in $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $.

Parameters
[in]prim_elemprimitive element
[in]alphaalgebraic variable
[in]betaalgebraic variable

Definition at line 377 of file cf_map_ext.cc.

379 {
380  if (primElem == alpha)
381  return mapUp (alpha, beta);
382  else
383  {
384  CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
385  int p= getCharacteristic ();
386  if (fac_NTL_char != p)
387  {
388  fac_NTL_char= p;
389  zz_p::init (p);
390  }
391  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta));
392  zz_pE::init (NTLMipo);
393  zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
394  zz_pE root= FindRoot (NTLPrimElemMipo);
395  return convertNTLzzpE2CF (root, beta);
396  }
397 }

◆ mapUp()

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 $ F_{p} (\alpha ) $ to $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $.

Parameters
[in]Fpoly over $ F_{p} (\alpha ) $
[in]alphaalg. variable
[in]betaalg. variable
[in]prim_elemprimitive element of $ F_{p} (\alpha ) $
[in]im_prim_elemimage of prim_elem in $ F_{p} (\beta ) $
[in,out]sourcelook up lists
[in,out]destlook up lists

Definition at line 366 of file cf_map_ext.cc.

369 {
370  if (prim_elem == alpha)
371  return F (im_prim_elem, alpha);
372  return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
373 }

◆ primitiveElement()

CanonicalForm primitiveElement ( const Variable alpha,
Variable beta,
bool &  fail 
)

determine a primitive element of $ F_{p} (\alpha ) $, $ \beta $ is a primitive element of a field which is isomorphic to $ F_{p}(\alpha ) $

Parameters
[in]alphasome algebraic variable
[in,out]betas.a.
[in,out]failfailure due to integer factorization failure?

Definition at line 310 of file cf_map_ext.cc.

311 {
312  bool primitive= false;
313  fail= false;
314  primitive= isPrimitive (alpha, fail);
315  if (fail)
316  return 0;
317  if (primitive)
318  {
319  beta= alpha;
320  return alpha;
321  }
323  int d= degree (mipo);
324  int p= getCharacteristic ();
325  if (fac_NTL_char != p)
326  {
327  fac_NTL_char= p;
328  zz_p::init (p);
329  }
330  zz_pX NTL_mipo;
331  CanonicalForm mipo2;
332  primitive= false;
333  fail= false;
334  bool initialized= false;
335  do
336  {
337  BuildIrred (NTL_mipo, d);
338  mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
339  if (!initialized)
340  beta= rootOf (mipo2);
341  else
342  setMipo (beta, mipo2);
343  primitive= isPrimitive (beta, fail);
344  if (primitive)
345  break;
346  if (fail)
347  return 0;
348  } while (1);
349  zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
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);
353  return convertNTLzzpE2CF (root, alpha);
354 }
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
GFPowUp
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
Definition: cf_map_ext.cc:196
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
j
int j
Definition: facHensel.cc:105
k
int k
Definition: cfEzgcd.cc:92
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
diff
static gmp_float * diff
Definition: mpr_complex.cc:46
result
return result
Definition: facAbsBiFact.cc:76
setMipo
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
gf_mipo
CanonicalForm gf_mipo
Definition: gfops.cc:56
InternalCF
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
convertNTLzzpE2CF
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition: NTLconvert.cc:794
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm
factory's main class
Definition: canonicalform.h:83
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
i
int i
Definition: cfEzgcd.cc:125
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
buf
int status int void * buf
Definition: si_signals.h:59
isPrimitive
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...
Definition: cf_cyclo.cc:136
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
findMinPoly
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
Definition: cf_map_ext.cc:434
prune
void prune(Variable &alpha)
Definition: variable.cc:261
GFPowDown
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
Definition: cf_map_ext.cc:220
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
beta
Variable beta
Definition: facAbsFact.cc:99
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
List::length
int length() const
Definition: ftmpl_list.cc:273
Variable
factory's class for variables
Definition: factory.h:118
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
Falpha2GFRep
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
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
int2imm_gf
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
G
static TreeM * G
Definition: janet.cc:32
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
ListIterator
Definition: ftmpl_list.h:87
GF2FalphaHelper
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
Definition: cf_map_ext.cc:142