My Project  UNKNOWN_GIT_VERSION
cf_factor.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  *
5  * @file cf_factor.cc
6  *
7  * Interface to factorization and square free factorization algorithms.
8  *
9  * Used by: cf_irred.cc
10  *
11  * Header file: cf_algorithm.h
12  *
13 **/
14 
15 
16 #include "config.h"
17 
18 
19 #include "cf_assert.h"
20 
21 #include "cf_defs.h"
22 #include "canonicalform.h"
23 #include "cf_iter.h"
24 #include "fac_sqrfree.h"
25 #include "cf_algorithm.h"
26 #include "facFqFactorize.h"
27 #include "facFqSquarefree.h"
28 #include "cf_map.h"
29 #include "facAlgExt.h"
30 #include "facFactorize.h"
31 #include "singext.h"
32 #include "cf_util.h"
33 
34 #include "int_int.h"
35 #ifdef HAVE_NTL
36 #include "NTLconvert.h"
37 #endif
38 
39 #include "factory/cf_gmp.h"
40 #ifdef HAVE_FLINT
41 #include "FLINTconvert.h"
42 #endif
43 
44 //static bool isUnivariateBaseDomain( const CanonicalForm & f )
45 //{
46 // CFIterator i = f;
47 // bool ok = i.coeff().inBaseDomain();
48 // i++;
49 // while ( i.hasTerms() && ( ok = ok && i.coeff().inBaseDomain() ) ) i++;
50 // return ok;
51 //}
52 
53 void find_exp(const CanonicalForm & f, int * exp_f)
54 {
55  if ( ! f.inCoeffDomain() )
56  {
57  int e=f.level();
58  CFIterator i = f;
59  if (e>=0)
60  {
61  if (i.exp() > exp_f[e]) exp_f[e]=i.exp();
62  }
63  for (; i.hasTerms(); i++ )
64  {
65  find_exp(i.coeff(), exp_f);
66  }
67  }
68 }
69 
71 {
72  int mv=f.level();
73  int *exp_f=NEW_ARRAY(int,mv+1);
74  int i;
75  for(i=mv;i>0;i--) exp_f[i]=0;
76  find_exp(f,exp_f);
77  for(i=mv;i>0;i--)
78  {
79  if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
80  {
81  mv=i;
82  }
83  }
84  DELETE_ARRAY(exp_f);
85  return mv;
86 }
87 
88 #if 1
89 //#ifndef NOSTREAMIO
90 void out_cf(const char *s1,const CanonicalForm &f,const char *s2)
91 {
92  printf("%s",s1);
93  if (f.isZero()) printf("+0");
94  //else if (! f.inCoeffDomain() )
95  else if (! f.inBaseDomain() )
96  {
97  int l = f.level();
98  for ( CFIterator i = f; i.hasTerms(); i++ )
99  {
100  int e=i.exp();
101  if (i.coeff().isOne())
102  {
103  printf("+");
104  if (e==0) printf("1");
105  else
106  {
107  printf("v(%d)",l);
108  if (e!=1) printf("^%d",e);
109  }
110  }
111  else
112  {
113  out_cf("+(",i.coeff(),")");
114  if (e!=0)
115  {
116  printf("*v(%d)",l);
117  if (e!=1) printf("^%d",e);
118  }
119  }
120  }
121  }
122  else
123  {
124  if ( f.isImm() )
125  {
127  {
128  long a= imm2int (f.getval());
129  if ( a == gf_q )
130  printf ("+%ld", a);
131  else if ( a == 0L )
132  printf ("+1");
133  else if ( a == 1L )
134  printf ("+%c",gf_name);
135  else
136  {
137  printf ("+%c",gf_name);
138  printf ("^%ld",a);
139  }
140  }
141  else
142  printf("+%ld",f.intval());
143  }
144  else
145  {
146  #ifdef NOSTREAMIO
147  if (f.inZ())
148  {
149  mpz_t m;
150  gmp_numerator(f,m);
151  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
152  str = mpz_get_str( str, 10, m );
153  puts(str);
154  delete[] str;
155  mpz_clear(m);
156  }
157  else if (f.inQ())
158  {
159  mpz_t m;
160  gmp_numerator(f,m);
161  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
162  str = mpz_get_str( str, 10, m );
163  puts(str);putchar('/');
164  delete[] str;
165  mpz_clear(m);
167  str = new char[mpz_sizeinbase( m, 10 ) + 2];
168  str = mpz_get_str( str, 10, m );
169  puts(str);
170  delete[] str;
171  mpz_clear(m);
172  }
173  #else
174  std::cout << f;
175  #endif
176  }
177  //if (f.inZ()) printf("(Z)");
178  //else if (f.inQ()) printf("(Q)");
179  //else if (f.inFF()) printf("(FF)");
180  //else if (f.inPP()) printf("(PP)");
181  //else if (f.inGF()) printf("(PP)");
182  //else
183  if (f.inExtension()) printf("E(%d)",f.level());
184  }
185  printf("%s",s2);
186 }
187 void out_cff(CFFList &L)
188 {
189  //int n = L.length();
190  CFFListIterator J=L;
191  int j=0;
192  for ( ; J.hasItem(); J++, j++ )
193  {
194  printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
195  printf("%d\n", J.getItem().exp());
196  }
197 }
198 void test_cff(CFFList &L,const CanonicalForm & f)
199 {
200  //int n = L.length();
201  CFFListIterator J=L;
202  CanonicalForm t=1;
203  int j=0;
204  if (!(L.getFirst().factor().inCoeffDomain()))
205  printf("first entry is not const\n");
206  for ( ; J.hasItem(); J++, j++ )
207  {
208  CanonicalForm tt=J.getItem().factor();
209  if (tt.inCoeffDomain() && (j!=0))
210  printf("other entry is const\n");
211  j=J.getItem().exp();
212  while(j>0) { t*=tt; j--; }
213  }
214  if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
215 }
216 //#endif
217 #endif
218 
220 {
221  if (f.inBaseDomain()) return true;
222  if (f.level()<0) return false;
223  for (CFIterator i=f;i.hasTerms();i++)
224  {
225  if (!isPurePoly_m(i.coeff())) return false;
226  }
227  return true;
228 }
230 {
231  if (f.level()<=0) return false;
232  for (CFIterator i=f;i.hasTerms();i++)
233  {
234  if (!(i.coeff().inBaseDomain())) return false;
235  }
236  return true;
237 }
238 
239 
240 /**
241  * get_max_degree_Variable returns Variable with
242  * highest degree. We assume f is *not* a constant!
243 **/
244 Variable
246 {
247  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
248  int max=0, maxlevel=0, n=level(f);
249  for ( int i=1; i<=n; i++ )
250  {
251  if (degree(f,Variable(i)) >= max)
252  {
253  max= degree(f,Variable(i)); maxlevel= i;
254  }
255  }
256  return Variable(maxlevel);
257 }
258 
259 /**
260  * get_Terms: Split the polynomial in the containing terms.
261  * getTerms: the real work is done here.
262 **/
263 void
265 {
266  if ( getNumVars(f) == 0 ) result.append(f*t);
267  else{
268  Variable x(level(f));
269  for ( CFIterator i=f; i.hasTerms(); i++ )
270  getTerms( i.coeff(), t*power(x,i.exp()), result);
271  }
272 }
273 CFList
275  CFList result,dummy,dummy2;
276  CFIterator i;
278 
279  if ( getNumVars(f) == 0 ) result.append(f);
280  else{
281  Variable _x(level(f));
282  for ( i=f; i.hasTerms(); i++ ){
283  getTerms(i.coeff(), 1, dummy);
284  for ( j=dummy; j.hasItem(); j++ )
285  result.append(j.getItem() * power(_x, i.exp()));
286 
287  dummy= dummy2; // have to initalize new
288  }
289  }
290  return result;
291 }
292 
293 
294 /**
295  * homogenize homogenizes f with Variable x
296 **/
298 homogenize( const CanonicalForm & f, const Variable & x)
299 {
300 #if 0
301  int maxdeg=totaldegree(f), deg;
302  CFIterator i;
303  CanonicalForm elem, result(0);
304 
305  for (i=f; i.hasTerms(); i++)
306  {
307  elem= i.coeff()*power(f.mvar(),i.exp());
308  deg = totaldegree(elem);
309  if ( deg < maxdeg )
310  result += elem * power(x,maxdeg-deg);
311  else
312  result+=elem;
313  }
314  return result;
315 #else
316  CFList Newlist, Termlist= get_Terms(f);
317  int maxdeg=totaldegree(f), deg;
319  CanonicalForm elem, result(0);
320 
321  for (i=Termlist; i.hasItem(); i++)
322  {
323  elem= i.getItem();
324  deg = totaldegree(elem);
325  if ( deg < maxdeg )
326  Newlist.append(elem * power(x,maxdeg-deg));
327  else
328  Newlist.append(elem);
329  }
330  for (i=Newlist; i.hasItem(); i++) // rebuild
331  result += i.getItem();
332 
333  return result;
334 #endif
335 }
336 
338 homogenize( const CanonicalForm & f, const Variable & x, const Variable & v1, const Variable & v2)
339 {
340 #if 0
341  int maxdeg=totaldegree(f), deg;
342  CFIterator i;
343  CanonicalForm elem, result(0);
344 
345  for (i=f; i.hasTerms(); i++)
346  {
347  elem= i.coeff()*power(f.mvar(),i.exp());
348  deg = totaldegree(elem);
349  if ( deg < maxdeg )
350  result += elem * power(x,maxdeg-deg);
351  else
352  result+=elem;
353  }
354  return result;
355 #else
356  CFList Newlist, Termlist= get_Terms(f);
357  int maxdeg=totaldegree(f), deg;
359  CanonicalForm elem, result(0);
360 
361  for (i=Termlist; i.hasItem(); i++)
362  {
363  elem= i.getItem();
364  deg = totaldegree(elem,v1,v2);
365  if ( deg < maxdeg )
366  Newlist.append(elem * power(x,maxdeg-deg));
367  else
368  Newlist.append(elem);
369  }
370  for (i=Newlist; i.hasItem(); i++) // rebuild
371  result += i.getItem();
372 
373  return result;
374 #endif
375 }
376 
378 
379 int cmpCF( const CFFactor & f, const CFFactor & g )
380 {
381  if (f.exp() > g.exp()) return 1;
382  if (f.exp() < g.exp()) return 0;
383  if (f.factor() > g.factor()) return 1;
384  return 0;
385 }
386 
387 /**
388  * factorization over \f$ F_p \f$ or \f$ Q \f$
389 **/
390 CFFList factorize ( const CanonicalForm & f, bool issqrfree )
391 {
392  if ( f.inCoeffDomain() )
393  return CFFList( f );
394 #ifndef NOASSERT
395  Variable a;
396  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
397  ( const CanonicalForm & f, const Variable & alpha ) instead");
398 #endif
399  //out_cf("factorize:",f,"==================================\n");
400  if (! f.isUnivariate() )
401  {
402  if ( singular_homog_flag && f.isHomogeneous())
403  {
405  int d_xn = degree(f,xn);
406  CFMap n;
407  CanonicalForm F = compress(f(1,xn),n);
408  CFFList Intermediatelist;
409  Intermediatelist = factorize(F);
410  CFFList Homoglist;
412  for ( j=Intermediatelist; j.hasItem(); j++ )
413  {
414  Homoglist.append(
415  CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
416  }
417  CFFList Unhomoglist;
418  CanonicalForm unhomogelem;
419  for ( j=Homoglist; j.hasItem(); j++ )
420  {
421  unhomogelem= homogenize(j.getItem().factor(),xn);
422  Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
423  d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
424  }
425  if ( d_xn != 0 ) // have to append xn^(d_xn)
426  Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
427  if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
428  return Unhomoglist;
429  }
430  }
431  CFFList F;
432  if ( getCharacteristic() > 0 )
433  {
434  if (f.isUnivariate())
435  {
436 #ifdef HAVE_NTL
437 #ifdef HAVE_FLINT
438  if (degree (f) < 300)
439  {
440  nmod_poly_t f1;
442  nmod_poly_factor_t result;
443  nmod_poly_factor_init (result);
444  mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
445  F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
446  nmod_poly_factor_clear (result);
447  nmod_poly_clear (f1);
448  }
449  else
450 #endif
451  {
452  // USE NTL
453  if (getCharacteristic()!=2)
454  {
456  {
458  zz_p::init(getCharacteristic());
459  }
460 
461  // convert to NTL
462  zz_pX f1=convertFacCF2NTLzzpX(f);
463  zz_p leadcoeff = LeadCoeff(f1);
464 
465  //make monic
466  f1=f1 / LeadCoeff(f1);
467  // factorize
468  vec_pair_zz_pX_long factors;
469  CanZass(factors,f1);
470 
471  F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
472  //test_cff(F,f);
473  }
474  else /*getCharacteristic()==2*/
475  {
476  // Specialcase characteristic==2
477  if (fac_NTL_char != 2)
478  {
479  fac_NTL_char = 2;
480  zz_p::init(2);
481  }
482  // convert to NTL using the faster conversion routine for characteristic 2
483  GF2X f1=convertFacCF2NTLGF2X(f);
484  // no make monic necessary in GF2
485  //factorize
486  vec_pair_GF2X_long factors;
487  CanZass(factors,f1);
488 
489  // convert back to factory again using the faster conversion routine for vectors over GF2X
490  F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
491  }
492  }
493 #else
494  // Use Factory without NTL
495  factoryError ("univariate factorization depends on NTL(missing)");
496  return CFFList (CFFactor (f, 1));
497 #endif //HAVE_NTL
498  }
499  else
500  {
501  #ifdef HAVE_NTL
502  if (issqrfree)
503  {
504  CFList factors;
505  Variable alpha;
507  factors= GFSqrfFactorize (f);
508  else
509  factors= FpSqrfFactorize (f);
510  for (CFListIterator i= factors; i.hasItem(); i++)
511  F.append (CFFactor (i.getItem(), 1));
512  }
513  else
514  {
515  Variable alpha;
517  F= GFFactorize (f);
518  else
519  F= FpFactorize (f);
520  }
521  #else
522  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
523  factoryError ("multivariate factorization depends on NTL(missing)");
524  return CFFList (CFFactor (f, 1));
525  #endif
526  }
527  }
528  else
529  {
530  bool on_rational = isOn(SW_RATIONAL);
531  On(SW_RATIONAL);
533  CanonicalForm fz = f * cd;
534  Off(SW_RATIONAL);
535  if ( f.isUnivariate() )
536  {
537  #ifdef HAVE_NTL
538  //USE NTL
539  CanonicalForm ic=icontent(fz);
540  fz/=ic;
541  ZZ c;
542  vec_pair_ZZX_long factors;
543  //factorize the converted polynomial
544  factor(c,factors,convertFacCF2NTLZZX(fz));
545 
546  //convert the result back to Factory
548  if ( ! ic.isOne() )
549  {
550  if ( F.getFirst().factor().inCoeffDomain() )
551  {
552  CFFactor new_first( F.getFirst().factor() * ic );
553  F.removeFirst();
554  F.insert( new_first );
555  }
556  else
557  F.insert( CFFactor( ic ) );
558  }
559  else
560  {
561  if ( !F.getFirst().factor().inCoeffDomain() )
562  {
563  CFFactor new_first( 1 );
564  F.insert( new_first );
565  }
566  }
567  #else
568  factoryError ("univariate factorization over Z depends on NTL(missing)");
569  return CFFList (CFFactor (f, 1));
570  #endif
571  }
572  else
573  {
574  #ifdef HAVE_NTL
575  On (SW_RATIONAL);
576  if (issqrfree)
577  {
578  CFList factors;
579  factors= ratSqrfFactorize (fz);
580  for (CFListIterator i= factors; i.hasItem(); i++)
581  F.append (CFFactor (i.getItem(), 1));
582  }
583  else
584  F = ratFactorize (fz);
585  Off (SW_RATIONAL);
586  #else
587  factoryError ("multivariate factorization depends on NTL(missing)");
588  return CFFList (CFFactor (f, 1));
589  #endif
590  }
591 
592  if ( on_rational )
593  On(SW_RATIONAL);
594  if ( ! cd.isOne() )
595  {
596  if ( F.getFirst().factor().inCoeffDomain() )
597  {
598  CFFactor new_first( F.getFirst().factor() / cd );
599  F.removeFirst();
600  F.insert( new_first );
601  }
602  else
603  {
604  F.insert( CFFactor( 1/cd ) );
605  }
606  }
607  }
608 
609  //out_cff(F);
610  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
611  return F;
612 }
613 
614 /**
615  * factorization over \f$ F_p(\alpha) \f$ or \f$ Q(\alpha) \f$
616 **/
618 {
619  if ( f.inCoeffDomain() )
620  return CFFList( f );
621  //out_cf("factorize:",f,"==================================\n");
622  //out_cf("mipo:",getMipo(alpha),"\n");
623 
624  CFFList F;
625  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
626 #ifndef NOASSERT
627  Variable beta;
628  if (hasFirstAlgVar(f, beta))
629  ASSERT (beta == alpha, "f has an algebraic variable that \
630  does not coincide with alpha");
631 #endif
632  int ch=getCharacteristic();
633  if (f.isUnivariate()&& (ch>0))
634  {
635 #ifdef HAVE_NTL
636  //USE NTL
637  if (ch>2)
638  {
639 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
640  nmod_poly_t FLINTmipo, leadingCoeff;
641  fq_nmod_ctx_t fq_con;
642 
643  nmod_poly_init (FLINTmipo, getCharacteristic());
644  nmod_poly_init (leadingCoeff, getCharacteristic());
645  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
646 
647  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
648  fq_nmod_poly_t FLINTF;
650  fq_nmod_poly_factor_t res;
651  fq_nmod_poly_factor_init (res, fq_con);
652  fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
654  F.insert (CFFactor (Lc (f), 1));
655 
656  fq_nmod_poly_factor_clear (res, fq_con);
657  fq_nmod_poly_clear (FLINTF, fq_con);
658  nmod_poly_clear (FLINTmipo);
659  nmod_poly_clear (leadingCoeff);
661 #else
662  // First all cases with characteristic !=2
663  // set remainder
665  {
667  zz_p::init(getCharacteristic());
668  }
669 
670  // set minimal polynomial in NTL
671  zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
672  zz_pE::init (minPo);
673 
674  // convert to NTL
675  zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
676  zz_pE leadcoeff= LeadCoeff(f1);
677 
678  //make monic
679  f1=f1 / leadcoeff;
680 
681  // factorize using NTL
682  vec_pair_zz_pEX_long factors;
683  CanZass(factors,f1);
684 
685  // return converted result
686  F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
687 #endif
688  }
689  else if (/*getCharacteristic()*/ch==2)
690  {
691  // special case : GF2
692 
693  // remainder is two ==> nothing to do
694 
695  // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
696  GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
697  GF2E::init (minPo);
698 
699  // convert to NTL again using the faster conversion routines
700  GF2EX f1;
701  if (isPurePoly(f))
702  {
703  GF2X f_tmp=convertFacCF2NTLGF2X(f);
704  f1=to_GF2EX(f_tmp);
705  }
706  else
707  f1=convertFacCF2NTLGF2EX(f,minPo);
708 
709  // make monic (in Z/2(a))
710  GF2E f1_coef=LeadCoeff(f1);
711  MakeMonic(f1);
712 
713  // factorize using NTL
714  vec_pair_GF2EX_long factors;
715  CanZass(factors,f1);
716 
717  // return converted result
718  F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
719  }
720 #else
721  factoryError ("univariate factorization depends on NTL(missing)");
722  return CFFList (CFFactor (f, 1));
723 #endif //HAVE_NTL
724  }
725  else if (ch>0)
726  {
727  #ifdef HAVE_NTL
728  F= FqFactorize (f, alpha);
729  #else
730  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
731  factoryError ("multivariate factorization depends on NTL(missing)");
732  return CFFList (CFFactor (f, 1));
733  #endif
734 
735  }
736  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
737  {
738  F= AlgExtFactorize (f, alpha);
739  }
740  else //Q(a)[x1,...,xn]
741  {
742 #ifdef HAVE_NTL
743  F= ratFactorize (f, alpha);
744 #else
745  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
746  factoryError ("multivariate factorization depends on NTL(missing)");
747  return CFFList (CFFactor (f, 1));
748 #endif
749  }
750  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
751  return F;
752 }
753 
754 /**
755  * squarefree factorization
756 **/
757 CFFList sqrFree ( const CanonicalForm & f, bool sort )
758 {
759 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
760  CFFList result;
761 
762  if ( getCharacteristic() == 0 )
763  result = sqrFreeZ( f );
764  else
765  {
766  Variable alpha;
767  if (hasFirstAlgVar (f, alpha))
768  result = FqSqrf( f, alpha );
769  else
770  result= FpSqrf (f);
771  }
772  if (sort)
773  {
774  CFFactor buf= result.getFirst();
775  result.removeFirst();
777  result.insert (buf);
778  }
779  return result;
780 }
781 
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition: facFqSquarefree.h:38
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
cmpCF
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:379
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
find_exp
void find_exp(const CanonicalForm &f, int *exp_f)
Definition: cf_factor.cc:53
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition: facSparseHensel.h:468
convertNTLvec_pair_ZZX_long2FacCFFList
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &multi, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition: NTLconvert.cc:747
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
singular_homog_flag
int singular_homog_flag
Definition: cf_factor.cc:377
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:229
canonicalform.h
Header for factory's main class CanonicalForm.
icontent
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
getTerms
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
convertNTLvec_pair_zzpX_long2FacCFFList
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
Definition: NTLconvert.cc:392
result
return result
Definition: facAbsBiFact.cc:76
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition: cf_factor.cc:390
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
FqFactorize
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:184
FqSqrf
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition: facFqSquarefree.h:77
singext.h
helper functions for conversion to and from Singular
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition: cf_defs.h:49
homogenize
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:298
cf_gmp.h
fq_con
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
sqrFree
CFFList sqrFree(const CanonicalForm &f, bool sort)
squarefree factorization
Definition: cf_factor.cc:757
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
FpSqrfFactorize
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Definition: facFqFactorize.h:47
CFMap
class CFMap
Definition: cf_map.h:85
ratFactorize
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:77
CFFList
List< CFFactor > CFFList
Definition: canonicalform.h:386
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
g
g
Definition: cfModGcd.cc:4031
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
get_max_degree_Variable
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:245
int_int.h
Factory's internal integers.
facFqSquarefree.h
This file provides functions for squarefrees factorizing over , or GF.
gf_name
char gf_name
Definition: gfops.cc:52
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
sqrFreeZ
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:45
CanonicalForm
factory's main class
Definition: canonicalform.h:83
xn
int xn
Definition: walk.cc:4508
convertFacCF2Fq_nmod_poly_t
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
Definition: FLINTconvert.cc:385
SW_USE_NTL_SORT
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:36
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
convertNTLvec_pair_GF2X_long2FacCFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:439
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
out_cf
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:90
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
res
CanonicalForm res
Definition: facAbsFact.cc:64
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
ratSqrfFactorize
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
buf
int status int void * buf
Definition: si_signals.h:59
convertFLINTFq_nmod_poly_factor2FacCFFList
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
Definition: FLINTconvert.cc:275
cd
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4030
out_cff
void out_cff(CFFList &L)
Definition: cf_factor.cc:187
AlgExtFactorize
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:370
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
cf_defs.h
factory switches.
cf_util.h
cf_iter.h
Iterators for CanonicalForm's.
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
max
static int max(int a, int b)
Definition: fast_mult.cc:264
fac_sqrfree.h
squarefree part and factorization over Q, Q(a)
NTLconvert.h
Conversion to and from NTL.
convertNTLvec_pair_zzpEX_long2FacCFFList
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:865
cf_algorithm.h
declarations of higher level algorithms.
gf_q
int gf_q
Definition: gfops.cc:47
Variable::level
int level() const
Definition: factory.h:134
get_Terms
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:21
find_mvar
int find_mvar(const CanonicalForm &f)
Definition: cf_factor.cc:70
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
convertFLINTnmod_poly_factor2FacCFFList
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
Definition: FLINTconvert.cc:255
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition: facSparseHensel.h:114
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
beta
Variable beta
Definition: facAbsFact.cc:99
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
Factor
Definition: ftmpl_factor.h:18
cf_map.h
map polynomials
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
factoryError
void(* factoryError)(const char *s)
Definition: cf_util.cc:75
factor
CanonicalForm factor
Definition: facAbsFact.cc:101
convertFacCF2NTLGF2EX
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1006
imm2int
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
FpFactorize
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:101
Variable
factory's class for variables
Definition: factory.h:118
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
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
facFactorize.h
multivariate factorization over Q(a)
m
int m
Definition: cfEzgcd.cc:121
GFSqrfFactorize
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
Definition: facFqFactorize.h:82
l
int l
Definition: cfEzgcd.cc:93
test_cff
void test_cff(CFFList &L, const CanonicalForm &f)
Definition: cf_factor.cc:198
cf_assert.h
assertions for Factory
facAlgExt.h
Univariate factorization over algebraic extension of Q using Trager's algorithm.
gmp_denominator
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
GFFactorize
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Definition: facFqFactorize.h:267
gmp_numerator
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
List
Definition: ftmpl_list.h:52
fq_nmod_poly_clear
fq_nmod_poly_clear(prod, fq_con)
convertFacCF2NTLGF2X
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:177
getReduce
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
isPurePoly_m
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:219
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
convertNTLvec_pair_GF2EX_long2FacCFFList
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:954
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
List::sort
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:48
ListIterator
Definition: ftmpl_list.h:87
facFqFactorize.h
This file provides functions for factorizing a multivariate polynomial over , or GF.