My Project  UNKNOWN_GIT_VERSION
cf_map_ext.cc
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
3 /** @file cf_map_ext.cc
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 
16 #include "config.h"
17 
18 
19 #include "cf_assert.h"
20 #include "debug.h"
21 
22 #include "canonicalform.h"
23 #include "cf_util.h"
24 #include "imm.h"
25 #include "cf_iter.h"
26 
27 #ifdef HAVE_NTL
28 #include "NTLconvert.h"
29 #endif
30 
31 // cyclotomoic polys:
32 #include "cf_cyclo.h"
33 
34 #include "cf_map_ext.h"
35 
36 /// helper function
37 int findItem (const CFList& list, const CanonicalForm& item)
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 }
47 
48 /// helper function
49 CanonicalForm getItem (const CFList& list, const int& pos)
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 }
62 
63 #ifdef HAVE_NTL
64 /// \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and \f$ \alpha \f$ is a
65 /// primitive element, returns the image of \f$ \alpha \f$
66 static inline
68 {
69  int p= getCharacteristic ();
70  if (fac_NTL_char != p)
71  {
72  fac_NTL_char= p;
73  zz_p::init (p);
74  }
75  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
76  zz_pE::init (NTL_mipo);
77  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
78  zz_pE root= FindRoot (NTL_alpha_mipo);
79  return convertNTLzzpE2CF (root, beta);
80 }
81 
82 #endif
83 
84 /// the CanonicalForm G is the output of map_up, returns F considered as an
85 /// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
86 /// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
87 /// isomorphic to \f$ F_{p}(\alpha ) \f$
88 static inline
90 mapDown (const CanonicalForm& F, const Variable& alpha, const
91  CanonicalForm& G, CFList& source, CFList& dest)
92 {
94  int counter= 0;
95  int pos;
96  int p= getCharacteristic();
97  int d= degree(getMipo(alpha));
98  int bound= ipower(p, d);
100  CanonicalForm remainder;
101  CanonicalForm alpha_power;
102  if (degree(F) == 0) return F;
103  if (F.level() < 0 && F.isUnivariate())
104  {
105  buf= F;
106  remainder= mod (buf, G);
107  ASSERT (remainder.isZero(), "alpha is not primitive");
108  pos= findItem (source, buf);
109  if (pos == 0)
110  source.append (buf);
111  buf2= buf;
112  while (degree (buf) != 0 && counter < bound)
113  {
114  buf /= G;
115  counter++;
116  if (buf == buf2) break;
117  }
118  ASSERT (counter >= bound, "alpha is not primitive");
119  if (pos == 0)
120  {
121  alpha_power= power (alpha, counter);
122  dest.append (alpha_power);
123  }
124  else
125  alpha_power= getItem (dest, pos);
126  result = alpha_power;
127  return result;
128  }
129  else
130  {
131  for (CFIterator i= F; i.hasTerms(); i++)
132  {
133  buf= mapDown (i.coeff(), alpha, G, source, dest);
134  result += buf*power(F.mvar(), i.exp());
135  }
136  return result;
137  }
138 }
139 
140 /// helper function
141 static inline
143 {
144  if (F.isZero())
145  return 0;
146  int exp;
148  InternalCF* buf;
149  if (F.inBaseDomain())
150  {
151  if (F.isOne()) return 1;
152  buf= F.getval();
153  exp= imm2int(buf);
154  result= power (alpha, exp).mapinto();
155  return result;
156  }
157  for (CFIterator i= F; i.hasTerms(); i++)
158  result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
159  return result;
160 }
161 
163 {
166  prune (beta);
167  return result;
168 }
169 
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 }
193 
194 /// GF_map_up helper
195 static inline
197 {
198  if (F.isOne()) return F;
200  if (F.inBaseDomain())
201  return power(F, k);
202  for (CFIterator i= F; i.hasTerms(); i++)
203  result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
204  return result;
205 }
206 
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 }
217 
218 /// GFMapDown helper
219 static inline
221 {
222  if (F.isOne()) return F;
224  int exp;
225  InternalCF* buf;
226  if (F.inBaseDomain())
227  {
228  buf= F.getval();
229  exp= imm2int (buf);
230  if ((exp % k) == 0)
231  exp= exp/k;
232  else
233  return -1;
234 
235  buf= int2imm_gf (exp);
236  return CanonicalForm (buf);
237  }
238  for (CFIterator i= F; i.hasTerms(); i++)
239  result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
240  return result;
241 }
242 
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 }
253 
254 /// map F in \f$ F_{p} (\alpha ) \f$ which is generated by G into some
255 /// \f$ F_{p}(\beta ) \f$ which is generated by H
256 static inline
258  const Variable& alpha, const CanonicalForm& H,
259  CFList& source, CFList& dest)
260 {
262  int counter= 0;
263  int pos;
264  int p= getCharacteristic();
265  int d= degree (getMipo(alpha));
266  int bound= ipower(p, d);
268  CanonicalForm remainder;
269  CanonicalForm H_power;
270  if (degree(F) <= 0) return F;
271  if (F.level() < 0 && F.isUnivariate())
272  {
273  buf= F;
274  remainder= mod (buf, G);
275  ASSERT (remainder.isZero(), "alpha is not primitive");
276  pos= findItem (source, buf);
277  if (pos == 0)
278  source.append (buf);
279  buf2= buf;
280  while (degree (buf) != 0 && counter < bound)
281  {
282  buf /= G;
283  counter++;
284  if (buf == buf2) break;
285  }
286  ASSERT (counter <= bound, "alpha is not primitive");
287  if (pos == 0)
288  {
289  H_power= buf*power (H, counter);
290  dest.append (H_power);
291  }
292  else
293  H_power= getItem (dest, pos);
294  result = H_power;
295  return result;
296  }
297  else
298  {
299  for (CFIterator i= F; i.hasTerms(); i++)
300  {
301  buf= mapUp (i.coeff(), G, alpha, H, source, dest);
302  result += buf*power(F.mvar(), i.exp());
303  }
304  return result;
305  }
306 }
307 
308 #ifdef HAVE_NTL
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 }
355 #endif
356 
358 mapDown (const CanonicalForm& F, const CanonicalForm& prim_elem, const
359  CanonicalForm& im_prim_elem, const Variable& alpha, CFList& source,
360  CFList& dest)
361 {
362  return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
363 }
364 
366 mapUp (const CanonicalForm& F, const Variable& alpha, const Variable& /*beta*/,
367  const CanonicalForm& prim_elem, const CanonicalForm& im_prim_elem,
368  CFList& source, CFList& dest)
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 }
374 
375 #ifdef HAVE_NTL
377 mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
378  const Variable& beta)
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 }
398 
400 map (const CanonicalForm& primElem, const Variable& alpha,
401  const CanonicalForm& F, const Variable& beta)
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 }
432 
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 }
468 
469 #endif
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
canonicalform.h
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
map
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
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
cf_cyclo.h
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
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:41
getItem
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
primitiveElement
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
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:77
GFMapDown
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::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
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
cf_util.h
cf_iter.h
cf_map_ext.h
findMinPoly
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
Definition: cf_map_ext.cc:434
NTLconvert.h
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
imm.h
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
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
List::length
int length() const
Definition: ftmpl_list.cc:273
imm2int
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
Variable
factory's class for variables
Definition: factory.h:117
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
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
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
cf_assert.h
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List< CanonicalForm >
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
H
CanonicalForm H
Definition: facAbsFact.cc:64
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
GF2FalphaRep
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
int2imm_gf
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
GFMapUp
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
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
buf2
CanonicalForm buf2
Definition: facFqBivar.cc:71
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
debug.h
mapDown
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:90
ListIterator
Definition: ftmpl_list.h:17
CanonicalForm::getval
InternalCF * getval() const
Definition: canonicalform.cc:31
GF2FalphaHelper
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
Definition: cf_map_ext.cc:142