My Project
Functions
cf_map_ext.cc File Reference

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 "FLINTconvert.h"
#include "cf_cyclo.h"
#include "cf_map_ext.h"

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...
 
static CanonicalForm mapUp (const Variable &alpha, const Variable &beta)
 $ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and $ \alpha $ is a primitive element, returns the image of $ \alpha $ 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 $ F_{p}(\alpha ) $, WARNING: make sure coefficients of F are really elements of a subfield of $ F_{p}(\beta ) $ which is isomorphic to $ F_{p}(\alpha ) $ 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 $ GF(p^{k}) $ to a polynomial over $ GF(p^{d}) $ , 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 $ GF(p^{d}) $ to a polynomial over $ GF(p^{k})$ , 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 $ F_{p} (\alpha ) $ which is generated by G into some $ F_{p}(\beta ) $ which is generated by H 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 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 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 $ F_{p} (\alpha ) $ to $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $. More...
 
CanonicalForm mapPrimElem (const CanonicalForm &primElem, 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 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.cc.

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 203 of file cf_map_ext.cc.

204 {
206  InternalCF* buf;
207 
208  if (F.inCoeffDomain())
209  {
210  if (F.inBaseDomain())
211  return F.mapinto();
212  else
213  {
214  for (CFIterator i= F; i.hasTerms(); i++)
215  {
216  buf= int2imm_gf (i.exp());
217  result += i.coeff().mapinto()*CanonicalForm (buf);
218  }
219  }
220  return result;
221  }
222  for (CFIterator i= F; i.hasTerms(); i++)
223  result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
224  return result;
225 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int i
Definition: cfEzgcd.cc:132
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:203
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
bool inBaseDomain() const
CanonicalForm mapinto() const
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
return result
Definition: facAbsBiFact.cc:75
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
int status int void * buf
Definition: si_signals.h:59

◆ findItem()

int findItem ( const CFList list,
const CanonicalForm item 
)

helper function

Definition at line 41 of file cf_map_ext.cc.

42 {
43  int result= 1;
44  for (CFListIterator i= list; i.hasItem(); i++, result++)
45  {
46  if (i.getItem() == item)
47  return result;
48  }
49  return 0;
50 }

◆ 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 640 of file cf_map_ext.cc.

641 {
642  ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
643 
644  int p=getCharacteristic();
645  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
646  nmod_poly_t FLINT_F,FLINT_alpha,g;
647  nmod_poly_init(g,p);
648  convertFacCF2nmod_poly_t(FLINT_F,F);
649  convertFacCF2nmod_poly_t(FLINT_alpha,getMipo(alpha));
650  minpoly(g,FLINT_F,FLINT_alpha);
651  nmod_poly_clear(FLINT_alpha);
652  nmod_poly_clear(FLINT_F);
655  return res;
656  #elif defined(HAVE_NTL)
657  if (fac_NTL_char != p)
658  {
659  fac_NTL_char= p;
660  zz_p::init (p);
661  }
662  zz_pX NTLF= convertFacCF2NTLzzpX (F);
663  int d= degree (getMipo (alpha));
664 
665  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
666  zz_pE::init (NTLMipo);
667  vec_zz_p pows;
668  pows.SetLength (2*d);
669 
670  zz_pE powNTLF;
671  set (powNTLF);
672  zz_pE NTLFE= to_zz_pE (NTLF);
673  zz_pX buf;
674  for (int i= 0; i < 2*d; i++)
675  {
676  buf= rep (powNTLF);
677  buf.rep.SetLength (d);
678  pows [i]= buf.rep[0];
679  powNTLF *= NTLFE;
680  }
681 
682  zz_pX NTLMinPoly;
683  MinPolySeq (NTLMinPoly, pows, d);
684 
685  return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
686  #else
687  factoryError("NTL/FLINT missing: findMinPoly");
688  #endif
689 }
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
int degree(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
#define ASSERT(expression, message)
Definition: cf_assert.h:99
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
bool isUnivariate() const
factory's class for variables
Definition: factory.h:127
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm res
Definition: facAbsFact.cc:60
nmod_poly_init(FLINTmipo, getCharacteristic())
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void init()
Definition: lintree.cc:864

◆ getItem()

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

helper function

Definition at line 53 of file cf_map_ext.cc.

54 {
55  int j= 1;
56  if ((pos > 0) && (pos <= list.length()))
57  {
58  for (CFListIterator i= list; j <= pos; i++, j++)
59  {
60  if (j == pos)
61  return i.getItem();
62  }
63  }
64  return 0;
65 }
int length() const
Definition: ftmpl_list.cc:273
int j
Definition: facHensel.cc:110

◆ GF2FalphaHelper()

static CanonicalForm GF2FalphaHelper ( const CanonicalForm F,
const Variable alpha 
)
inlinestatic

helper function

Definition at line 175 of file cf_map_ext.cc.

176 {
177  if (F.isZero())
178  return 0;
179  int exp;
181  InternalCF* buf;
182  if (F.inBaseDomain())
183  {
184  if (F.isOne()) return 1;
185  buf= F.getval();
186  exp= imm2int(buf);
187  result= power (alpha, exp).mapinto();
188  return result;
189  }
190  for (CFIterator i= F; i.hasTerms(); i++)
191  result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
192  return result;
193 }
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
Definition: cf_map_ext.cc:175
CF_NO_INLINE bool isZero() const
InternalCF * getval() const
CF_NO_INLINE bool isOne() const
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357

◆ 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 195 of file cf_map_ext.cc.

196 {
199  prune (beta);
200  return result;
201 }
Variable beta
Definition: facAbsFact.cc:95
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56

◆ 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 276 of file cf_map_ext.cc.

277 {
278  int d= getGFDegree();
279  ASSERT (d % k == 0, "multiple of GF degree expected");
280  int p= getCharacteristic();
281  int ext_field_size= ipower (p, d);
282  int field_size= ipower ( p, k);
283  int diff= (ext_field_size - 1)/(field_size - 1);
284  return GFPowDown (F, diff);
285 }
int getGFDegree()
Definition: cf_char.cc:75
int k
Definition: cfEzgcd.cc:99
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
Definition: cf_map_ext.cc:253
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45

◆ 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 240 of file cf_map_ext.cc.

241 {
242  int d= getGFDegree();
243  ASSERT (d%k == 0, "multiple of GF degree expected");
244  int p= getCharacteristic();
245  int ext_field_size= ipower (p, d);
246  int field_size= ipower ( p, k);
247  int diff= (ext_field_size - 1)/(field_size - 1);
248  return GFPowUp (F, diff);
249 }
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
Definition: cf_map_ext.cc:229

◆ GFPowDown()

static CanonicalForm GFPowDown ( const CanonicalForm F,
int  k 
)
inlinestatic

GFMapDown helper.

Definition at line 253 of file cf_map_ext.cc.

254 {
255  if (F.isOne()) return F;
257  int exp;
258  InternalCF* buf;
259  if (F.inBaseDomain())
260  {
261  buf= F.getval();
262  exp= imm2int (buf);
263  if ((exp % k) == 0)
264  exp= exp/k;
265  else
266  return -1;
267 
268  buf= int2imm_gf (exp);
269  return CanonicalForm (buf);
270  }
271  for (CFIterator i= F; i.hasTerms(); i++)
272  result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
273  return result;
274 }

◆ GFPowUp()

static CanonicalForm GFPowUp ( const CanonicalForm F,
int  k 
)
inlinestatic

GF_map_up helper.

Definition at line 229 of file cf_map_ext.cc.

230 {
231  if (F.isOne()) return F;
233  if (F.inBaseDomain())
234  return power(F, k);
235  for (CFIterator i= F; i.hasTerms(); i++)
236  result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
237  return result;
238 }

◆ 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 504 of file cf_map_ext.cc.

506 {
507  CanonicalForm G= F;
508  int order= 0;
509  while (!G.isOne())
510  {
511  G /= primElem;
512  order++;
513  }
514  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
515  // convert mipo
516  nmod_poly_t mipo1;
518  fq_nmod_ctx_t ctx;
519  fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
520  nmod_poly_clear(mipo1);
521  // convert mipo2 (alpha)
522  fq_nmod_poly_t mipo2;
524  fq_nmod_poly_factor_t fac;
525  fq_nmod_poly_factor_init(fac,ctx);
526  fq_nmod_poly_roots(fac, mipo2, 0, ctx);
527  // roots in fac, #=fac->num
528  int ind=-1;
529  fq_nmod_t r0,FLINTbeta;
530  fq_nmod_init(r0, ctx);
531  fq_nmod_init(FLINTbeta, ctx);
532  convertFacCF2Fq_nmod_t(FLINTbeta,beta,ctx);
533  fmpz_t FLINTorder;
534  fmpz_set_si(FLINTorder,order);
535  for(int i=0;i< fac->num;i++)
536  {
537  // get the root (-abs.term of linear factor)
538  fq_nmod_poly_get_coeff(r0,fac->poly+i,0,ctx);
539  fq_nmod_neg(r0,r0,ctx);
540  // r^order
541  fq_nmod_pow(r0,r0,FLINTorder,ctx);
542  // ==beta?
543  if (fq_nmod_equal(r0,FLINTbeta,ctx))
544  {
545  ind=i;
546  break;
547  }
548  }
549  fmpz_clear(FLINTorder);
550  // convert
551  fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
552  fq_nmod_neg(r0,r0,ctx);
554  // cleanup
555  fq_nmod_poly_factor_clear(fac,ctx);
556  fq_nmod_clear(r0, ctx);
557  fq_nmod_clear(FLINTbeta,ctx);
558  fq_nmod_poly_clear(mipo2,ctx);
559  fq_nmod_ctx_clear(ctx);
560  return r1;
561  #elif defined(HAVE_NTL)
562  int p= getCharacteristic ();
563  if (fac_NTL_char != p)
564  {
565  fac_NTL_char= p;
566  zz_p::init (p);
567  }
568  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
569  zz_pE::init (NTL_mipo);
570  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
571  zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
572  vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
573  long ind=-1;
574  for (long i= 0; i < roots.length(); i++)
575  {
576  if (power (roots [i], order)== NTLBeta)
577  {
578  ind= i;
579  break;
580  }
581  }
582  return (convertNTLzzpE2CF (roots[ind], beta));
583  #else
584  factoryError("NTL/FLINT missing: map");
585  return CanonicalForm(0);
586  #endif
587 }
void convertFacCF2Fq_nmod_t(fq_nmod_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory element of F_q to a FLINT fq_nmod_t, does not do any memory allocation for po...
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CanonicalForm convertFq_nmod_t2FacCF(const fq_nmod_t poly, const Variable &alpha, const fq_nmod_ctx_t)
conversion of a FLINT element of F_q to a CanonicalForm with alg. variable alpha
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition: NTLconvert.cc:799
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear(prod, fq_con)
STATIC_VAR TreeM * G
Definition: janet.cc:31

◆ mapDown() [1/2]

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 431 of file cf_map_ext.cc.

434 {
435  return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
436 }
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70

◆ mapDown() [2/2]

static CanonicalForm mapDown ( const CanonicalForm F,
const Variable alpha,
const CanonicalForm G,
CFList source,
CFList dest 
)
inlinestatic

the CanonicalForm G is the output of map_up, returns F considered as an element over $ F_{p}(\alpha ) $, WARNING: make sure coefficients of F are really elements of a subfield of $ F_{p}(\beta ) $ which is isomorphic to $ F_{p}(\alpha ) $

Definition at line 123 of file cf_map_ext.cc.

125 {
127  int counter= 0;
128  int pos;
129  int p= getCharacteristic();
130  int d= degree(getMipo(alpha));
131  int bound= ipower(p, d);
134  CanonicalForm alpha_power;
135  if (degree(F) == 0) return F;
136  if (F.level() < 0 && F.isUnivariate())
137  {
138  buf= F;
139  remainder= mod (buf, G);
140  ASSERT (remainder.isZero(), "alpha is not primitive");
141  pos= findItem (source, buf);
142  if (pos == 0)
143  source.append (buf);
144  buf2= buf;
145  while (degree (buf) != 0 && counter < bound)
146  {
147  buf /= G;
148  counter++;
149  if (buf == buf2) break;
150  }
151  ASSERT (counter >= bound, "alpha is not primitive");
152  if (pos == 0)
153  {
154  alpha_power= power (alpha, counter);
155  dest.append (alpha_power);
156  }
157  else
158  alpha_power= getItem (dest, pos);
159  result = alpha_power;
160  return result;
161  }
162  else
163  {
164  for (CFIterator i= F; i.hasTerms(); i++)
165  {
166  buf= mapDown (i.coeff(), alpha, G, source, dest);
167  result += buf*power(F.mvar(), i.exp());
168  }
169  return result;
170  }
171 }
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:41
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 ,...
Definition: cf_map_ext.cc:123
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
CanonicalForm buf2
Definition: facFqBivar.cc:73
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition: fac_util.cc:115

◆ mapPrimElem()

CanonicalForm mapPrimElem ( const CanonicalForm primElem,
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]primElemprimitive element
[in]alphaalgebraic variable
[in]betaalgebraic variable

Definition at line 450 of file cf_map_ext.cc.

452 {
453  if (primElem == alpha)
454  return mapUp (alpha, beta);
455  else
456  {
457  CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
458  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
459  // convert mipo1
460  nmod_poly_t mipo1;
462  fq_nmod_ctx_t ctx;
463  fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
464  nmod_poly_clear(mipo1);
465  // convert mipo2 (primElemMipo)
466  fq_nmod_poly_t mipo2;
467  convertFacCF2Fq_nmod_poly_t(mipo2,primElemMipo,ctx);
468  fq_nmod_poly_factor_t fac;
469  fq_nmod_poly_factor_init(fac,ctx);
470  fq_nmod_poly_roots(fac, mipo2, 0, ctx);
471  // root of first (linear) factor: -absolute Term
472  fq_nmod_t r0;
473  fq_nmod_init(r0, ctx);
474  fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
475  fq_nmod_neg(r0, r0, ctx);
476  // convert
478  // cleanup
479  fq_nmod_poly_factor_clear(fac,ctx);
480  fq_nmod_clear(r0, ctx);
481  fq_nmod_poly_clear(mipo2,ctx);
482  fq_nmod_ctx_clear(ctx);
483  return r1;
484  #elif defined(HAVE_NTL)
485  int p= getCharacteristic ();
486  if (fac_NTL_char != p)
487  {
488  fac_NTL_char= p;
489  zz_p::init (p);
490  }
491  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta));
492  zz_pE::init (NTLMipo);
493  zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
494  zz_pE root= FindRoot (NTLPrimElemMipo);
495  return convertNTLzzpE2CF (root, beta);
496  #else
497  factoryError("NTL/FLINT missing: mapPrimElem");
498  #endif
499  }
500 }
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
Definition: cf_map_ext.cc:640

◆ mapUp() [1/3]

static CanonicalForm mapUp ( const CanonicalForm F,
const CanonicalForm G,
const Variable alpha,
const CanonicalForm H,
CFList source,
CFList dest 
)
inlinestatic

map F in $ F_{p} (\alpha ) $ which is generated by G into some $ F_{p}(\beta ) $ which is generated by H

Definition at line 290 of file cf_map_ext.cc.

293 {
295  int counter= 0;
296  int pos;
297  int p= getCharacteristic();
298  int d= degree (getMipo(alpha));
299  int bound= ipower(p, d);
302  CanonicalForm H_power;
303  if (degree(F) <= 0) return F;
304  if (F.level() < 0 && F.isUnivariate())
305  {
306  buf= F;
307  remainder= mod (buf, G);
308  ASSERT (remainder.isZero(), "alpha is not primitive");
309  pos= findItem (source, buf);
310  if (pos == 0)
311  source.append (buf);
312  buf2= buf;
313  while (degree (buf) != 0 && counter < bound)
314  {
315  buf /= G;
316  counter++;
317  if (buf == buf2) break;
318  }
319  ASSERT (counter <= bound, "alpha is not primitive");
320  if (pos == 0)
321  {
322  H_power= buf*power (H, counter);
323  dest.append (H_power);
324  }
325  else
326  H_power= getItem (dest, pos);
327  result = H_power;
328  return result;
329  }
330  else
331  {
332  for (CFIterator i= F; i.hasTerms(); i++)
333  {
334  buf= mapUp (i.coeff(), G, alpha, H, source, dest);
335  result += buf*power(F.mvar(), i.exp());
336  }
337  return result;
338  }
339 }
CanonicalForm H
Definition: facAbsFact.cc:60

◆ mapUp() [2/3]

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 439 of file cf_map_ext.cc.

442 {
443  if (prim_elem == alpha)
444  return F (im_prim_elem, alpha);
445  return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
446 }

◆ mapUp() [3/3]

static CanonicalForm mapUp ( const Variable alpha,
const Variable beta 
)
inlinestatic

$ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and $ \alpha $ is a primitive element, returns the image of $ \alpha $

Definition at line 70 of file cf_map_ext.cc.

71 {
72  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
73  // convert mipo1
74  nmod_poly_t mipo1;
76  fq_nmod_ctx_t ctx;
77  fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
78  nmod_poly_clear(mipo1);
79  // convert mipo2 (alpah)
80  fq_nmod_poly_t mipo2;
82  fq_nmod_poly_factor_t fac;
83  fq_nmod_poly_factor_init(fac,ctx);
84  fq_nmod_poly_roots(fac, mipo2, 0, ctx);
85  // root of first (linear) factor: -absolute Term
86  fq_nmod_t r0;
87  fq_nmod_init(r0, ctx);
88  fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
89  fq_nmod_neg(r0, r0, ctx);
90  // convert
92  // cleanup
93  fq_nmod_poly_factor_clear(fac,ctx);
94  fq_nmod_clear(r0, ctx);
95  fq_nmod_poly_clear(mipo2,ctx);
96  fq_nmod_ctx_clear(ctx);
97  return r1;
98  #elif defined(HAVE_NTL)
99  int p= getCharacteristic ();
100  if (fac_NTL_char != p)
101  {
102  fac_NTL_char= p;
103  zz_p::init (p);
104  }
105  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
106  zz_pE::init (NTL_mipo);
107  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
108  zz_pE root= FindRoot (NTL_alpha_mipo);
109  return convertNTLzzpE2CF (root, beta);
110  #else
111  factoryError("NTL/FLINT missing: mapUp");
112  return CanonicalForm(0); // to avoid warnings
113  #endif
114 }

◆ 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 342 of file cf_map_ext.cc.

343 {
344  bool primitive= false;
345  fail= false;
346  primitive= isPrimitive (alpha, fail);
347  if (fail)
348  return 0;
349  if (primitive)
350  {
351  beta= alpha;
352  return alpha;
353  }
355  int d= degree (mipo);
356  int p= getCharacteristic ();
357  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
358  nmod_poly_t FLINT_mipo;
359  nmod_poly_init(FLINT_mipo,p);
360  #elif defined(HAVE_NTL)
361  if (fac_NTL_char != p)
362  {
363  fac_NTL_char= p;
364  zz_p::init (p);
365  }
366  zz_pX NTL_mipo;
367  #else
368  factoryError("NTL/FLINT missing: primitiveElement");
369  return CanonicalForm(0);
370  #endif
371  CanonicalForm mipo2;
372  primitive= false;
373  fail= false;
374  bool initialized= false;
375  do
376  {
377  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
378  nmod_poly_randtest_monic_irreducible(FLINT_mipo, FLINTrandom, d+1);
379  mipo2=convertnmod_poly_t2FacCF(FLINT_mipo,Variable(1));
380  #elif defined(HAVE_NTL)
381  BuildIrred (NTL_mipo, d);
382  mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
383  #endif
384  if (!initialized)
385  beta= rootOf (mipo2);
386  else
387  setMipo (beta, mipo2);
388  primitive= isPrimitive (beta, fail);
389  if (primitive)
390  break;
391  if (fail)
392  return 0;
393  } while (1);
394  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
395  nmod_poly_clear(FLINT_mipo);
396  // convert alpha_mipo
397  nmod_poly_t alpha_mipo;
398  convertFacCF2nmod_poly_t(alpha_mipo,mipo);
399  fq_nmod_ctx_t ctx;
400  fq_nmod_ctx_init_modulus(ctx,alpha_mipo,"t");
401  nmod_poly_clear(alpha_mipo);
402  // convert beta_mipo (mipo2)
403  fq_nmod_poly_t FLINT_beta_mipo;
404  convertFacCF2Fq_nmod_poly_t(FLINT_beta_mipo,mipo2,ctx);
405  fq_nmod_poly_factor_t fac;
406  fq_nmod_poly_factor_init(fac,ctx);
407  fq_nmod_poly_roots(fac, FLINT_beta_mipo, 0, ctx);
408  // root of first (linear) factor: -absolute Term
409  fq_nmod_t r0;
410  fq_nmod_init(r0, ctx);
411  fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
412  fq_nmod_neg(r0, r0, ctx);
413  // convert
415  // cleanup
416  fq_nmod_poly_factor_clear(fac,ctx);
417  fq_nmod_clear(r0, ctx);
418  fq_nmod_poly_clear(FLINT_beta_mipo,ctx);
419  fq_nmod_ctx_clear(ctx);
420  return r1;
421  #elif defined(HAVE_NTL)
422  zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
423  zz_pE::init (alpha_mipo);
424  zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
425  zz_pE root= FindRoot (NTL_beta_mipo);
426  return convertNTLzzpE2CF (root, alpha);
427  #endif
428 }
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:131
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
CanonicalForm mipo
Definition: facAlgExt.cc:57
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219