My Project
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 #include "fac_berlekamp.h"
34 #include "fac_cantzass.h"
35 #include "fac_univar.h"
36 #include "fac_multivar.h"
37 
38 #include "int_int.h"
39 #ifdef HAVE_NTL
40 #include "NTLconvert.h"
41 #endif
42 
43 #include "factory/cf_gmp.h"
44 #ifdef HAVE_FLINT
45 #include "FLINTconvert.h"
46 #if (__FLINT_RELEASE >= 20700)
47 #include <flint/nmod_mpoly_factor.h>
48 #include <flint/fmpq_mpoly_factor.h>
49 #include <flint/fq_nmod_mpoly_factor.h>
50 #endif
51 #endif
52 
53 //static bool isUnivariateBaseDomain( const CanonicalForm & f )
54 //{
55 // CFIterator i = f;
56 // bool ok = i.coeff().inBaseDomain();
57 // i++;
58 // while ( i.hasTerms() && ( ok = ok && i.coeff().inBaseDomain() ) ) i++;
59 // return ok;
60 //}
61 
62 void find_exp(const CanonicalForm & f, int * exp_f)
63 {
64  if ( ! f.inCoeffDomain() )
65  {
66  int e=f.level();
67  CFIterator i = f;
68  if (e>=0)
69  {
70  if (i.exp() > exp_f[e]) exp_f[e]=i.exp();
71  }
72  for (; i.hasTerms(); i++ )
73  {
74  find_exp(i.coeff(), exp_f);
75  }
76  }
77 }
78 
80 {
81  int mv=f.level();
82  int *exp_f=NEW_ARRAY(int,mv+1);
83  int i;
84  for(i=mv;i>0;i--) exp_f[i]=0;
85  find_exp(f,exp_f);
86  for(i=mv;i>0;i--)
87  {
88  if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
89  {
90  mv=i;
91  }
92  }
93  DELETE_ARRAY(exp_f);
94  return mv;
95 }
96 
97 #if 1
98 //#ifndef NOSTREAMIO
99 void out_cf(const char *s1,const CanonicalForm &f,const char *s2)
100 {
101  printf("%s",s1);
102  if (f.isZero()) printf("+0");
103  //else if (! f.inCoeffDomain() )
104  else if (! f.inBaseDomain() )
105  {
106  int l = f.level();
107  for ( CFIterator i = f; i.hasTerms(); i++ )
108  {
109  int e=i.exp();
110  if (i.coeff().isOne())
111  {
112  printf("+");
113  if (e==0) printf("1");
114  else
115  {
116  printf("%c",'a'+l-1);
117  if (e!=1) printf("^%d",e);
118  }
119  }
120  else
121  {
122  out_cf("+(",i.coeff(),")");
123  if (e!=0)
124  {
125  printf("*%c",'a'+l-1);
126  if (e!=1) printf("^%d",e);
127  }
128  }
129  }
130  }
131  else
132  {
133  if ( f.isImm() )
134  {
136  {
137  long a= imm2int (f.getval());
138  if ( a == gf_q )
139  printf ("+%ld", a);
140  else if ( a == 0L )
141  printf ("+1");
142  else if ( a == 1L )
143  printf ("+%c",gf_name);
144  else
145  {
146  printf ("+%c",gf_name);
147  printf ("^%ld",a);
148  }
149  }
150  else
151  {
152  long l=f.intval();
153  if (l<0) printf("%ld",l);
154  else printf("+%ld",l);
155  }
156  }
157  else
158  {
159  #ifdef NOSTREAMIO
160  if (f.inZ())
161  {
162  mpz_t m;
163  gmp_numerator(f,m);
164  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
165  str = mpz_get_str( str, 10, m );
166  puts(str);
167  delete[] str;
168  mpz_clear(m);
169  }
170  else if (f.inQ())
171  {
172  mpz_t m;
173  gmp_numerator(f,m);
174  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
175  str = mpz_get_str( str, 10, m );
176  while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
177  puts(str);putchar('/');
178  delete[] str;
179  mpz_clear(m);
181  str = new char[mpz_sizeinbase( m, 10 ) + 2];
182  str = mpz_get_str( str, 10, m );
183  while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
184  puts(str);
185  delete[] str;
186  mpz_clear(m);
187  }
188  #else
189  std::cout << f;
190  #endif
191  }
192  //if (f.inZ()) printf("(Z)");
193  //else if (f.inQ()) printf("(Q)");
194  //else if (f.inFF()) printf("(FF)");
195  //else if (f.inPP()) printf("(PP)");
196  //else if (f.inGF()) printf("(PP)");
197  //else
198  if (f.inExtension()) printf("E(%d)",f.level());
199  }
200  printf("%s",s2);
201 }
202 void out_cff(CFFList &L)
203 {
204  //int n = L.length();
205  CFFListIterator J=L;
206  int j=0;
207  for ( ; J.hasItem(); J++, j++ )
208  {
209  printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
210  printf("%d\n", J.getItem().exp());
211  }
212 }
213 void test_cff(CFFList &L,const CanonicalForm & f)
214 {
215  //int n = L.length();
216  CFFListIterator J=L;
217  CanonicalForm t=1;
218  int j=0;
219  if (!(L.getFirst().factor().inCoeffDomain()))
220  printf("first entry is not const\n");
221  for ( ; J.hasItem(); J++, j++ )
222  {
223  CanonicalForm tt=J.getItem().factor();
224  if (tt.inCoeffDomain() && (j!=0))
225  printf("other entry is const\n");
226  j=J.getItem().exp();
227  while(j>0) { t*=tt; j--; }
228  }
229  if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
230 }
231 //#endif
232 #endif
233 
235 {
236  if (f.inBaseDomain()) return true;
237  if (f.level()<0) return false;
238  for (CFIterator i=f;i.hasTerms();i++)
239  {
240  if (!isPurePoly_m(i.coeff())) return false;
241  }
242  return true;
243 }
245 {
246  if (f.level()<=0) return false;
247  for (CFIterator i=f;i.hasTerms();i++)
248  {
249  if (!(i.coeff().inBaseDomain())) return false;
250  }
251  return true;
252 }
253 
254 
255 /**
256  * get_max_degree_Variable returns Variable with
257  * highest degree. We assume f is *not* a constant!
258 **/
259 Variable
261 {
262  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
263  int max=0, maxlevel=0, n=level(f);
264  for ( int i=1; i<=n; i++ )
265  {
266  if (degree(f,Variable(i)) >= max)
267  {
268  max= degree(f,Variable(i)); maxlevel= i;
269  }
270  }
271  return Variable(maxlevel);
272 }
273 
274 /**
275  * get_Terms: Split the polynomial in the containing terms.
276  * getTerms: the real work is done here.
277 **/
278 void
280 {
281  if ( getNumVars(f) == 0 ) result.append(f*t);
282  else{
283  Variable x(level(f));
284  for ( CFIterator i=f; i.hasTerms(); i++ )
285  getTerms( i.coeff(), t*power(x,i.exp()), result);
286  }
287 }
288 CFList
290  CFList result,dummy,dummy2;
291  CFIterator i;
293 
294  if ( getNumVars(f) == 0 ) result.append(f);
295  else{
296  Variable _x(level(f));
297  for ( i=f; i.hasTerms(); i++ ){
298  getTerms(i.coeff(), 1, dummy);
299  for ( j=dummy; j.hasItem(); j++ )
300  result.append(j.getItem() * power(_x, i.exp()));
301 
302  dummy= dummy2; // have to initalize new
303  }
304  }
305  return result;
306 }
307 
308 
309 /**
310  * homogenize homogenizes f with Variable x
311 **/
313 homogenize( const CanonicalForm & f, const Variable & x)
314 {
315 #if 0
316  int maxdeg=totaldegree(f), deg;
317  CFIterator i;
318  CanonicalForm elem, result(0);
319 
320  for (i=f; i.hasTerms(); i++)
321  {
322  elem= i.coeff()*power(f.mvar(),i.exp());
323  deg = totaldegree(elem);
324  if ( deg < maxdeg )
325  result += elem * power(x,maxdeg-deg);
326  else
327  result+=elem;
328  }
329  return result;
330 #else
331  CFList Newlist, Termlist= get_Terms(f);
332  int maxdeg=totaldegree(f), deg;
334  CanonicalForm elem, result(0);
335 
336  for (i=Termlist; i.hasItem(); i++)
337  {
338  elem= i.getItem();
339  deg = totaldegree(elem);
340  if ( deg < maxdeg )
341  Newlist.append(elem * power(x,maxdeg-deg));
342  else
343  Newlist.append(elem);
344  }
345  for (i=Newlist; i.hasItem(); i++) // rebuild
346  result += i.getItem();
347 
348  return result;
349 #endif
350 }
351 
353 homogenize( const CanonicalForm & f, const Variable & x, const Variable & v1, const Variable & v2)
354 {
355 #if 0
356  int maxdeg=totaldegree(f), deg;
357  CFIterator i;
358  CanonicalForm elem, result(0);
359 
360  for (i=f; i.hasTerms(); i++)
361  {
362  elem= i.coeff()*power(f.mvar(),i.exp());
363  deg = totaldegree(elem);
364  if ( deg < maxdeg )
365  result += elem * power(x,maxdeg-deg);
366  else
367  result+=elem;
368  }
369  return result;
370 #else
371  CFList Newlist, Termlist= get_Terms(f);
372  int maxdeg=totaldegree(f), deg;
374  CanonicalForm elem, result(0);
375 
376  for (i=Termlist; i.hasItem(); i++)
377  {
378  elem= i.getItem();
379  deg = totaldegree(elem,v1,v2);
380  if ( deg < maxdeg )
381  Newlist.append(elem * power(x,maxdeg-deg));
382  else
383  Newlist.append(elem);
384  }
385  for (i=Newlist; i.hasItem(); i++) // rebuild
386  result += i.getItem();
387 
388  return result;
389 #endif
390 }
391 
393 
394 int cmpCF( const CFFactor & f, const CFFactor & g )
395 {
396  if (f.exp() > g.exp()) return 1;
397  if (f.exp() < g.exp()) return 0;
398  if (f.factor() > g.factor()) return 1;
399  return 0;
400 }
401 
402 /**
403  * factorization over \f$ F_p \f$ or \f$ Q \f$
404 **/
405 CFFList factorize ( const CanonicalForm & f, bool issqrfree )
406 {
407  if ( f.inCoeffDomain() )
408  return CFFList( f );
409 #ifndef NOASSERT
410  Variable a;
411  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
412  ( const CanonicalForm & f, const Variable & alpha ) instead");
413 #endif
414  //out_cf("factorize:",f,"==================================\n");
415  if (! f.isUnivariate() ) // preprocess homog. polys
416  {
417  if ( singular_homog_flag && f.isHomogeneous())
418  {
420  int d_xn = degree(f,xn);
421  CFMap n;
422  CanonicalForm F = compress(f(1,xn),n);
423  CFFList Intermediatelist;
424  Intermediatelist = factorize(F);
425  CFFList Homoglist;
427  for ( j=Intermediatelist; j.hasItem(); j++ )
428  {
429  Homoglist.append(
430  CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
431  }
432  CFFList Unhomoglist;
433  CanonicalForm unhomogelem;
434  for ( j=Homoglist; j.hasItem(); j++ )
435  {
436  unhomogelem= homogenize(j.getItem().factor(),xn);
437  Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
438  d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
439  }
440  if ( d_xn != 0 ) // have to append xn^(d_xn)
441  Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
442  if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
443  return Unhomoglist;
444  }
445  }
446  CFFList F;
447  if ( getCharacteristic() > 0 )
448  {
449  if (f.isUnivariate())
450  {
451 #ifdef HAVE_FLINT
452 #ifdef HAVE_NTL
453  if (degree (f) < 300)
454 #endif
455  {
456  // use FLINT: char p, univariate
457  nmod_poly_t f1;
459  nmod_poly_factor_t result;
460  nmod_poly_factor_init (result);
461  mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
462  F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
463  nmod_poly_factor_clear (result);
464  nmod_poly_clear (f1);
465  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
466  return F;
467  }
468 #endif
469 #ifdef HAVE_NTL
470  { // NTL char 2, univariate
471  if (getCharacteristic()==2)
472  {
473  // Specialcase characteristic==2
474  if (fac_NTL_char != 2)
475  {
476  fac_NTL_char = 2;
477  zz_p::init(2);
478  }
479  // convert to NTL using the faster conversion routine for characteristic 2
480  GF2X f1=convertFacCF2NTLGF2X(f);
481  // no make monic necessary in GF2
482  //factorize
483  vec_pair_GF2X_long factors;
484  CanZass(factors,f1);
485 
486  // convert back to factory again using the faster conversion routine for vectors over GF2X
487  F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
488  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
489  return F;
490  }
491  }
492 #endif
493 #ifdef HAVE_NTL
494  {
495  // use NTL char p, univariate
497  {
500  }
501 
502  // convert to NTL
503  zz_pX f1=convertFacCF2NTLzzpX(f);
504  zz_p leadcoeff = LeadCoeff(f1);
505 
506  //make monic
507  f1=f1 / LeadCoeff(f1);
508  // factorize
509  vec_pair_zz_pX_long factors;
510  CanZass(factors,f1);
511 
512  F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
513  //test_cff(F,f);
514  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
515  return F;
516  }
517 #endif
518 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
519  // Use Factory without NTL and without FLINT: char p, univariate
520  {
521  if ( isOn( SW_BERLEKAMP ) )
522  F=FpFactorizeUnivariateB( f, issqrfree );
523  else
524  F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
525  return F;
526  }
527 #endif
528  }
529  else // char p, multivariate
530  {
532  {
533  #if defined(HAVE_NTL)
534  if (issqrfree)
535  {
536  CFList factors;
537  Variable alpha;
538  factors= GFSqrfFactorize (f);
539  for (CFListIterator i= factors; i.hasItem(); i++)
540  F.append (CFFactor (i.getItem(), 1));
541  }
542  else
543  {
544  Variable alpha;
545  F= GFFactorize (f);
546  }
547  #else
548  factoryError ("multivariate factorization over GF depends on NTL(missing)");
549  return CFFList (CFFactor (f, 1));
550  #endif
551  }
552  else
553  {
554  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
555  if (!isOn(SW_USE_FL_FAC_P))
556  {
557  #endif
558  #if defined(HAVE_NTL)
559  if (issqrfree)
560  {
561  CFList factors;
562  Variable alpha;
563  factors= FpSqrfFactorize (f);
564  for (CFListIterator i= factors; i.hasItem(); i++)
565  F.append (CFFactor (i.getItem(), 1));
566  goto end_charp;
567  }
568  else
569  {
570  Variable alpha;
571  F= FpFactorize (f);
572  goto end_charp;
573  }
574  #endif
575  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
576  }
577  #endif
578  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
579  nmod_mpoly_ctx_t ctx;
580  nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
581  nmod_mpoly_t Flint_f;
582  nmod_mpoly_init(Flint_f,ctx);
583  convFactoryPFlintMP(f,Flint_f,ctx,f.level());
584  nmod_mpoly_factor_t factors;
585  nmod_mpoly_factor_init(factors,ctx);
586  int okay;
587  if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
588  else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
589  nmod_mpoly_t fac;
590  nmod_mpoly_init(fac,ctx);
591  CanonicalForm cf_fac;
592  int cf_exp;
593  cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
594  F.append(CFFactor(cf_fac,1));
595  for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
596  {
597  nmod_mpoly_factor_get_base(fac,factors,i,ctx);
598  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
599  cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
600  F.append(CFFactor(cf_fac,cf_exp));
601  }
602  nmod_mpoly_factor_clear(factors,ctx);
603  nmod_mpoly_clear(Flint_f,ctx);
604  nmod_mpoly_ctx_clear(ctx);
605  if (okay==0)
606  {
609  F=factorize(f,issqrfree);
612  }
613  #endif
614  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
615  #ifndef HAVE_NTL
616  factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
617  return CFFList (CFFactor (f, 1));
618  #endif
619  #endif
620  }
621  }
622  }
623  else // char 0
624  {
625  bool on_rational = isOn(SW_RATIONAL);
626  On(SW_RATIONAL);
628  CanonicalForm fz = f * cd;
629  Off(SW_RATIONAL);
630  if ( f.isUnivariate() )
631  {
632  CanonicalForm ic=icontent(fz);
633  fz/=ic;
634  if (fz.degree()==1)
635  {
636  F=CFFList(CFFactor(fz,1));
637  F.insert(CFFactor(ic,1));
638  }
639  else
640  #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
641  {
642  // FLINT 2.6.0 has a bug:
643  // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
644  // use FLINT: char 0, univariate
645  fmpz_poly_t f1;
646  convertFacCF2Fmpz_poly_t (f1, fz);
647  fmpz_poly_factor_t result;
648  fmpz_poly_factor_init (result);
649  fmpz_poly_factor(result, f1);
651  fmpz_poly_factor_clear (result);
652  fmpz_poly_clear (f1);
653  if ( ! ic.isOne() )
654  {
655  // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
656  // first entry is in CoeffDomain
657  CFFactor new_first( F.getFirst().factor() * ic );
658  F.removeFirst();
659  F.insert( new_first );
660  }
661  }
662  goto end_char0;
663  #elif defined(HAVE_NTL)
664  {
665  //use NTL
666  ZZ c;
667  vec_pair_ZZX_long factors;
668  //factorize the converted polynomial
669  factor(c,factors,convertFacCF2NTLZZX(fz));
670 
671  //convert the result back to Factory
673  if ( ! ic.isOne() )
674  {
675  // according to convertNTLvec_pair_ZZX_long2FacCFFList
676  // first entry is in CoeffDomain
677  CFFactor new_first( F.getFirst().factor() * ic );
678  F.removeFirst();
679  F.insert( new_first );
680  }
681  }
682  goto end_char0;
683  #else
684  {
685  //Use Factory without NTL: char 0, univariate
686  F = ZFactorizeUnivariate( fz, issqrfree );
687  goto end_char0;
688  }
689  #endif
690  }
691  else // multivariate, char 0
692  {
693  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
694  if (isOn(SW_USE_FL_FAC_0))
695  {
696  On (SW_RATIONAL);
697  fmpz_mpoly_ctx_t ctx;
698  fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
699  fmpz_mpoly_t Flint_f;
700  fmpz_mpoly_init(Flint_f,ctx);
701  convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
702  fmpz_mpoly_factor_t factors;
703  fmpz_mpoly_factor_init(factors,ctx);
704  int rr;
705  if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
706  else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
707  if (rr==0) printf("fail\n");
708  fmpz_mpoly_t fac;
709  fmpz_mpoly_init(fac,ctx);
710  CanonicalForm cf_fac;
711  int cf_exp;
712  fmpz_t c;
713  fmpz_init(c);
714  fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
715  cf_fac=convertFmpz2CF(c);
716  fmpz_clear(c);
717  F.append(CFFactor(cf_fac,1));
718  for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
719  {
720  fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
721  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
722  cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
723  F.append(CFFactor(cf_fac,cf_exp));
724  }
725  fmpz_mpoly_factor_clear(factors,ctx);
726  fmpz_mpoly_clear(Flint_f,ctx);
727  fmpz_mpoly_ctx_clear(ctx);
728  goto end_char0;
729  }
730  #endif
731  #if defined(HAVE_NTL)
732  On (SW_RATIONAL);
733  if (issqrfree)
734  {
735  CFList factors= ratSqrfFactorize (fz);
736  for (CFListIterator i= factors; i.hasItem(); i++)
737  F.append (CFFactor (i.getItem(), 1));
738  }
739  else
740  {
741  F = ratFactorize (fz);
742  }
743  #endif
744  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
745  #ifndef HAVE_NTL
746  F=ZFactorizeMultivariate(fz, issqrfree);
747  #endif
748  #endif
749  }
750 
751 end_char0:
752  if ( on_rational )
753  On(SW_RATIONAL);
754  else
755  Off(SW_RATIONAL);
756  if ( ! cd.isOne() )
757  {
758  CFFactor new_first( F.getFirst().factor() / cd );
759  F.removeFirst();
760  F.insert( new_first );
761  }
762  }
763 
764 #if defined(HAVE_NTL)
765 end_charp:
766 #endif
767  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
768  return F;
769 }
770 
771 /**
772  * factorization over \f$ F_p(\alpha) \f$ or \f$ Q(\alpha) \f$
773 **/
775 {
776  if ( f.inCoeffDomain() )
777  return CFFList( f );
778  //out_cf("factorize:",f,"==================================\n");
779  //out_cf("mipo:",getMipo(alpha),"\n");
780 
781  CFFList F;
782  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
783 #ifndef NOASSERT
784  Variable beta;
785  if (hasFirstAlgVar(f, beta))
786  ASSERT (beta == alpha, "f has an algebraic variable that \
787  does not coincide with alpha");
788 #endif
789  int ch=getCharacteristic();
790  if (ch>0)
791  {
792  if (f.isUnivariate())
793  {
794 #ifdef HAVE_NTL
795  if (/*getCharacteristic()*/ch==2)
796  {
797  // special case : GF2
798 
799  // remainder is two ==> nothing to do
800 
801  // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
802  GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
803  GF2E::init (minPo);
804 
805  // convert to NTL again using the faster conversion routines
806  GF2EX f1;
807  if (isPurePoly(f))
808  {
809  GF2X f_tmp=convertFacCF2NTLGF2X(f);
810  f1=to_GF2EX(f_tmp);
811  }
812  else
813  f1=convertFacCF2NTLGF2EX(f,minPo);
814 
815  // make monic (in Z/2(a))
816  GF2E f1_coef=LeadCoeff(f1);
817  MakeMonic(f1);
818 
819  // factorize using NTL
820  vec_pair_GF2EX_long factors;
821  CanZass(factors,f1);
822 
823  // return converted result
824  F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
825  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
826  return F;
827  }
828 #endif
829 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
830  {
831  // use FLINT
832  nmod_poly_t FLINTmipo, leadingCoeff;
833  fq_nmod_ctx_t fq_con;
834 
835  nmod_poly_init (FLINTmipo, ch);
836  nmod_poly_init (leadingCoeff, ch);
837  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
838 
839  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
840  fq_nmod_poly_t FLINTF;
842  fq_nmod_poly_factor_t res;
843  fq_nmod_poly_factor_init (res, fq_con);
844  fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
846  F.insert (CFFactor (Lc (f), 1));
847 
848  fq_nmod_poly_factor_clear (res, fq_con);
849  fq_nmod_poly_clear (FLINTF, fq_con);
850  nmod_poly_clear (FLINTmipo);
851  nmod_poly_clear (leadingCoeff);
853  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
854  return F;
855  }
856 #endif
857 #ifdef HAVE_NTL
858  {
859  // use NTL
860  if (fac_NTL_char != ch)
861  {
862  fac_NTL_char = ch;
863  zz_p::init(ch);
864  }
865 
866  // set minimal polynomial in NTL
867  zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
868  zz_pE::init (minPo);
869 
870  // convert to NTL
871  zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
872  zz_pE leadcoeff= LeadCoeff(f1);
873 
874  //make monic
875  f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
876 
877  // factorize
878  vec_pair_zz_pEX_long factors;
879  CanZass(factors,f1);
880 
881  // return converted result
882  F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
883  //test_cff(F,f);
884  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
885  return F;
886  }
887 #endif
888 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
889  // char p, extension, univariate
890  CanonicalForm c=Lc(f);
891  CanonicalForm fc=f/c;
892  F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
893  F.insert (CFFactor (c, 1));
894 #endif
895  }
896  else // char p, multivariate
897  {
898  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
899  // use FLINT
900  nmod_poly_t FLINTmipo;
901  fq_nmod_ctx_t fq_con;
902  fq_nmod_mpoly_ctx_t ctx;
903 
904  nmod_poly_init (FLINTmipo, ch);
905  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
906 
907  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
908  fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
909 
910  fq_nmod_mpoly_t FLINTF;
911  fq_nmod_mpoly_init(FLINTF,ctx);
912  convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
913  fq_nmod_mpoly_factor_t res;
914  fq_nmod_mpoly_factor_init (res, ctx);
915  fq_nmod_mpoly_factor (res, FLINTF, ctx);
916  F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
917  //F.insert (CFFactor (Lc (f), 1));
918 
919  fq_nmod_mpoly_factor_clear (res, ctx);
920  fq_nmod_mpoly_clear (FLINTF, ctx);
921  nmod_poly_clear (FLINTmipo);
922  fq_nmod_mpoly_ctx_clear (ctx);
924  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
925  return F;
926  #elif defined(HAVE_NTL)
927  F= FqFactorize (f, alpha);
928  #else
929  factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
930  return CFFList (CFFactor (f, 1));
931  #endif
932  }
933  }
934  else // Q(a)[x]
935  {
936  if (f.isUnivariate())
937  {
938  F= AlgExtFactorize (f, alpha);
939  }
940  else //Q(a)[x1,...,xn]
941  {
942  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
943  F= ratFactorize (f, alpha);
944  #else
945  factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
946  return CFFList (CFFactor (f, 1));
947  #endif
948  }
949  }
950  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
951  return F;
952 }
953 
954 /**
955  * squarefree factorization
956 **/
957 CFFList sqrFree ( const CanonicalForm & f, bool sort )
958 {
959 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
960  CFFList result;
961 
962  if ( getCharacteristic() == 0 )
963  result = sqrFreeZ( f );
964  else
965  {
966  Variable alpha;
967  if (hasFirstAlgVar (f, alpha))
968  result = FqSqrf( f, alpha );
969  else
970  result= FpSqrf (f);
971  }
972  if (sort)
973  {
974  CFFactor buf= result.getFirst();
975  result.removeFirst();
977  result.insert (buf);
978  }
979  return result;
980 }
981 
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
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
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
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
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CFFList convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac, const Variable &x)
conversion of a FLINT factorization over Z to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:446
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:870
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:959
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition: NTLconvert.cc:399
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1007
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:184
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &cont, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition: NTLconvert.cc:753
Conversion to and from NTL.
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int degree(const CanonicalForm &f)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
int level(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4089
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
declarations of higher level algorithms.
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition: cf_defs.h:47
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:39
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:57
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:55
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition: cf_defs.h:51
#define GaloisFieldDomain
Definition: cf_defs.h:18
void test_cff(CFFList &L, const CanonicalForm &f)
Definition: cf_factor.cc:213
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:260
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:244
void out_cff(CFFList &L)
Definition: cf_factor.cc:202
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:394
int find_mvar(const CanonicalForm &f)
Definition: cf_factor.cc:79
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:234
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:279
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:289
VAR int singular_homog_flag
Definition: cf_factor.cc:392
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:99
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:313
CFFList sqrFree(const CanonicalForm &f, bool sort)
squarefree factorization
Definition: cf_factor.cc:957
void find_exp(const CanonicalForm &f, int *exp_f)
Definition: cf_factor.cc:62
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition: cf_factor.cc:405
Iterators for CanonicalForm's.
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
map polynomials
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
FILE * f
Definition: checklibs.c:9
static int gettype()
Definition: cf_factory.h:28
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: factory.h:127
int level() const
Definition: factory.h:143
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
CanonicalForm res
Definition: facAbsFact.cc:60
Variable beta
Definition: facAbsFact.cc:95
CanonicalForm factor
Definition: facAbsFact.cc:97
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:370
Univariate factorization over algebraic extension of Q using Trager's algorithm.
multivariate factorization over Q(a)
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:79
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
This file provides functions for factorizing a multivariate polynomial over , or GF.
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
This file provides functions for squarefrees factorizing over , or GF.
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
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)
bool isZero(const CFArray &A)
checks if entries of A are zero
void sort(CFArray &A, int l=0)
quick sort A
CFFList FpFactorizeUnivariateB(const CanonicalForm &f, bool issqrfree=false)
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:49
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:25
squarefree part and factorization over Q, Q(a)
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void FACTORY_PUBLIC gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
void FACTORY_PUBLIC gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
static int max(int a, int b)
Definition: fast_mult.cc:264
VAR int gf_q
Definition: gfops.cc:47
VAR char gf_name
Definition: gfops.cc:52
#define VAR
Definition: globaldefs.h:5
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
Factory's internal integers.
char * str(leftv arg)
Definition: shared.cc:704
void init()
Definition: lintree.cc:864
int status int void * buf
Definition: si_signals.h:59
helper functions for conversion to and from Singular
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
VAR int xn
Definition: walk.cc:4508