My Project
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 #ifdef HAVE_FLINT
32 #include "FLINTconvert.h"
33 #endif
34 
35 // cyclotomoic polys:
36 #include "cf_cyclo.h"
37 
38 #include "cf_map_ext.h"
39 
40 /// helper function
41 int findItem (const CFList& list, const CanonicalForm& item)
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 }
51 
52 /// helper function
53 CanonicalForm getItem (const CFList& list, const int& pos)
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 }
66 
67 /// \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and \f$ \alpha \f$ is a
68 /// primitive element, returns the image of \f$ \alpha \f$
69 static inline
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 }
115 
116 
117 /// the CanonicalForm G is the output of map_up, returns F considered as an
118 /// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
119 /// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
120 /// isomorphic to \f$ F_{p}(\alpha ) \f$
121 static inline
123 mapDown (const CanonicalForm& F, const Variable& alpha, const
124  CanonicalForm& G, CFList& source, CFList& dest)
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 }
172 
173 /// helper function
174 static inline
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 }
194 
196 {
199  prune (beta);
200  return result;
201 }
202 
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 }
226 
227 /// GF_map_up helper
228 static inline
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 }
239 
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 }
250 
251 /// GFMapDown helper
252 static inline
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 }
275 
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 }
286 
287 /// map F in \f$ F_{p} (\alpha ) \f$ which is generated by G into some
288 /// \f$ F_{p}(\beta ) \f$ which is generated by H
289 static inline
291  const Variable& alpha, const CanonicalForm& H,
292  CFList& source, CFList& dest)
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 }
340 
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 }
429 
431 mapDown (const CanonicalForm& F, const CanonicalForm& prim_elem, const
432  CanonicalForm& im_prim_elem, const Variable& alpha, CFList& source,
433  CFList& dest)
434 {
435  return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
436 }
437 
439 mapUp (const CanonicalForm& F, const Variable& alpha, const Variable& /*beta*/,
440  const CanonicalForm& prim_elem, const CanonicalForm& im_prim_elem,
441  CFList& source, CFList& dest)
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 }
447 
448 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
450 mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
451  const Variable& beta)
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 }
501 #endif
502 
504 map (const CanonicalForm& primElem, const Variable& alpha,
505  const CanonicalForm& F, const Variable& beta)
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 }
588 
589 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
590 /*
591  g is in Fp[x]
592  F is in Fp[t]
593  h is in Fp[t]
594  In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that
595  g(F(t)) = 0 mod h(t)
596  i.e. g is the minpoly of the element F(t) of the finite field.
597 */
598 static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
599 {
600  slong i;
601  slong d = nmod_poly_degree(h);
602  mp_limb_t p = h->mod.n;
603  nmod_poly_t Fpow;
604  nmod_berlekamp_massey_t bma;
605 
606  nmod_poly_init(Fpow, p);
607  nmod_berlekamp_massey_init(bma, p);
608 
609  nmod_poly_one(Fpow);
610  for (i = 0; i < 2*d; i++)
611  {
612  nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
613  nmod_poly_mulmod(Fpow, Fpow, F, h);
614  }
615 
616  nmod_berlekamp_massey_reduce(bma);
617 
618  /* something went horribly wrong if V does not kill the whole sequence */
619  FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
620  nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
621 
622  nmod_poly_make_monic(g, nmod_berlekamp_massey_V_poly(bma));
623 #if WANT_ASSERT
624  {
625  nmod_poly_t z;
626  nmod_poly_init(z, p);
627  nmod_poly_compose_mod(z, g, F, h);
628  FLINT_ASSERT(nmod_poly_is_zero(z));
629  nmod_poly_clear(z);
630  }
631 #endif
632  nmod_poly_clear(Fpow);
633  nmod_berlekamp_massey_clear(bma);
634 }
635 #endif
636 
637 
638 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
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 }
690 #endif
CanonicalForm convertFq_nmod_t2FacCF(const fq_nmod_t poly, const Variable &alpha, const fq_nmod_ctx_t ctx)
conversion of a FLINT element of F_q to a CanonicalForm with alg. variable alpha
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...
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
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
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition: NTLconvert.cc:799
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
Conversion to and from NTL.
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
int getGFDegree()
Definition: cf_char.cc:75
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4080
g
Definition: cfModGcd.cc:4092
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
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
Compute cyclotomic polynomials and factorize integers by brute force.
Iterators for CanonicalForm's.
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
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:450
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
Definition: cf_map_ext.cc:175
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:276
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:342
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
Definition: cf_map_ext.cc:640
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
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
Definition: cf_map_ext.cc:229
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
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:240
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:195
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:504
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
Definition: cf_map_ext.cc:253
This file implements functions to map between extensions of finite fields.
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
InternalCF * getval() const
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool inBaseDomain() const
CanonicalForm mapinto() const
bool isUnivariate() const
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: factory.h:134
functions to print debug output
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
#define slong
CanonicalForm res
Definition: facAbsFact.cc:60
Variable beta
Definition: facAbsFact.cc:95
CanonicalForm H
Definition: facAbsFact.cc:60
CanonicalForm mipo
Definition: facAlgExt.cc:57
CanonicalForm buf2
Definition: facFqBivar.cc:73
int j
Definition: facHensel.cc:110
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition: fac_util.cc:115
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
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR Poly * h
Definition: janet.cc:971
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45
void init()
Definition: lintree.cc:864
int status int void * buf
Definition: si_signals.h:59