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  if (issqrfree) nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
587  else nmod_mpoly_factor(factors,Flint_f,ctx);
588  nmod_mpoly_t fac;
589  nmod_mpoly_init(fac,ctx);
590  CanonicalForm cf_fac;
591  int cf_exp;
592  cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
593  F.append(CFFactor(cf_fac,1));
594  for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
595  {
596  nmod_mpoly_factor_get_base(fac,factors,i,ctx);
597  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
598  cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
599  F.append(CFFactor(cf_fac,cf_exp));
600  }
601  nmod_mpoly_factor_clear(factors,ctx);
602  nmod_mpoly_clear(Flint_f,ctx);
603  nmod_mpoly_ctx_clear(ctx);
604  #endif
605  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
606  #ifndef HAVE_NTL
607  factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
608  return CFFList (CFFactor (f, 1));
609  #endif
610  #endif
611  }
612  }
613  }
614  else // char 0
615  {
616  bool on_rational = isOn(SW_RATIONAL);
617  On(SW_RATIONAL);
619  CanonicalForm fz = f * cd;
620  Off(SW_RATIONAL);
621  if ( f.isUnivariate() )
622  {
623  CanonicalForm ic=icontent(fz);
624  fz/=ic;
625  if (fz.degree()==1)
626  {
627  F=CFFList(CFFactor(fz,1));
628  F.insert(CFFactor(ic,1));
629  }
630  else
631  #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
632  {
633  // FLINT 2.6.0 has a bug:
634  // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
635  // use FLINT: char 0, univariate
636  fmpz_poly_t f1;
637  convertFacCF2Fmpz_poly_t (f1, fz);
638  fmpz_poly_factor_t result;
639  fmpz_poly_factor_init (result);
640  fmpz_poly_factor(result, f1);
642  fmpz_poly_factor_clear (result);
643  fmpz_poly_clear (f1);
644  if ( ! ic.isOne() )
645  {
646  // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
647  // first entry is in CoeffDomain
648  CFFactor new_first( F.getFirst().factor() * ic );
649  F.removeFirst();
650  F.insert( new_first );
651  }
652  }
653  goto end_char0;
654  #elif defined(HAVE_NTL)
655  {
656  //use NTL
657  ZZ c;
658  vec_pair_ZZX_long factors;
659  //factorize the converted polynomial
660  factor(c,factors,convertFacCF2NTLZZX(fz));
661 
662  //convert the result back to Factory
664  if ( ! ic.isOne() )
665  {
666  // according to convertNTLvec_pair_ZZX_long2FacCFFList
667  // first entry is in CoeffDomain
668  CFFactor new_first( F.getFirst().factor() * ic );
669  F.removeFirst();
670  F.insert( new_first );
671  }
672  }
673  goto end_char0;
674  #else
675  {
676  //Use Factory without NTL: char 0, univariate
677  F = ZFactorizeUnivariate( fz, issqrfree );
678  goto end_char0;
679  }
680  #endif
681  }
682  else // multivariate, char 0
683  {
684  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
685  if (isOn(SW_USE_FL_FAC_0))
686  {
687  On (SW_RATIONAL);
688  fmpz_mpoly_ctx_t ctx;
689  fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
690  fmpz_mpoly_t Flint_f;
691  fmpz_mpoly_init(Flint_f,ctx);
692  convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
693  fmpz_mpoly_factor_t factors;
694  fmpz_mpoly_factor_init(factors,ctx);
695  int rr;
696  if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
697  else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
698  if (rr==0) printf("fail\n");
699  fmpz_mpoly_t fac;
700  fmpz_mpoly_init(fac,ctx);
701  CanonicalForm cf_fac;
702  int cf_exp;
703  fmpz_t c;
704  fmpz_init(c);
705  fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
706  cf_fac=convertFmpz2CF(c);
707  fmpz_clear(c);
708  F.append(CFFactor(cf_fac,1));
709  for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
710  {
711  fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
712  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
713  cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
714  F.append(CFFactor(cf_fac,cf_exp));
715  }
716  fmpz_mpoly_factor_clear(factors,ctx);
717  fmpz_mpoly_clear(Flint_f,ctx);
718  fmpz_mpoly_ctx_clear(ctx);
719  goto end_char0;
720  }
721  #endif
722  #if defined(HAVE_NTL)
723  On (SW_RATIONAL);
724  if (issqrfree)
725  {
726  CFList factors= ratSqrfFactorize (fz);
727  for (CFListIterator i= factors; i.hasItem(); i++)
728  F.append (CFFactor (i.getItem(), 1));
729  }
730  else
731  {
732  F = ratFactorize (fz);
733  }
734  #endif
735  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
736  #ifndef HAVE_NTL
737  F=ZFactorizeMultivariate(fz, issqrfree);
738  #endif
739  #endif
740  }
741 
742 end_char0:
743  if ( on_rational )
744  On(SW_RATIONAL);
745  else
746  Off(SW_RATIONAL);
747  if ( ! cd.isOne() )
748  {
749  CFFactor new_first( F.getFirst().factor() / cd );
750  F.removeFirst();
751  F.insert( new_first );
752  }
753  }
754 
755 end_charp:
756  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
757  return F;
758 }
759 
760 /**
761  * factorization over \f$ F_p(\alpha) \f$ or \f$ Q(\alpha) \f$
762 **/
764 {
765  if ( f.inCoeffDomain() )
766  return CFFList( f );
767  //out_cf("factorize:",f,"==================================\n");
768  //out_cf("mipo:",getMipo(alpha),"\n");
769 
770  CFFList F;
771  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
772 #ifndef NOASSERT
773  Variable beta;
774  if (hasFirstAlgVar(f, beta))
775  ASSERT (beta == alpha, "f has an algebraic variable that \
776  does not coincide with alpha");
777 #endif
778  int ch=getCharacteristic();
779  if (ch>0)
780  {
781  if (f.isUnivariate())
782  {
783 #ifdef HAVE_NTL
784  if (/*getCharacteristic()*/ch==2)
785  {
786  // special case : GF2
787 
788  // remainder is two ==> nothing to do
789 
790  // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
791  GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
792  GF2E::init (minPo);
793 
794  // convert to NTL again using the faster conversion routines
795  GF2EX f1;
796  if (isPurePoly(f))
797  {
798  GF2X f_tmp=convertFacCF2NTLGF2X(f);
799  f1=to_GF2EX(f_tmp);
800  }
801  else
802  f1=convertFacCF2NTLGF2EX(f,minPo);
803 
804  // make monic (in Z/2(a))
805  GF2E f1_coef=LeadCoeff(f1);
806  MakeMonic(f1);
807 
808  // factorize using NTL
809  vec_pair_GF2EX_long factors;
810  CanZass(factors,f1);
811 
812  // return converted result
813  F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
814  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
815  return F;
816  }
817 #endif
818 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
819  {
820  // use FLINT
821  nmod_poly_t FLINTmipo, leadingCoeff;
822  fq_nmod_ctx_t fq_con;
823 
824  nmod_poly_init (FLINTmipo, ch);
825  nmod_poly_init (leadingCoeff, ch);
826  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
827 
828  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
829  fq_nmod_poly_t FLINTF;
831  fq_nmod_poly_factor_t res;
832  fq_nmod_poly_factor_init (res, fq_con);
833  fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
835  F.insert (CFFactor (Lc (f), 1));
836 
837  fq_nmod_poly_factor_clear (res, fq_con);
838  fq_nmod_poly_clear (FLINTF, fq_con);
839  nmod_poly_clear (FLINTmipo);
840  nmod_poly_clear (leadingCoeff);
842  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
843  return F;
844  }
845 #endif
846 #ifdef HAVE_NTL
847  {
848  // use NTL
849  if (fac_NTL_char != ch)
850  {
851  fac_NTL_char = ch;
852  zz_p::init(ch);
853  }
854 
855  // set minimal polynomial in NTL
856  zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
857  zz_pE::init (minPo);
858 
859  // convert to NTL
860  zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
861  zz_pE leadcoeff= LeadCoeff(f1);
862 
863  //make monic
864  f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
865 
866  // factorize
867  vec_pair_zz_pEX_long factors;
868  CanZass(factors,f1);
869 
870  // return converted result
871  F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
872  //test_cff(F,f);
873  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
874  return F;
875  }
876 #endif
877 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
878  // char p, extension, univariate
879  CanonicalForm c=Lc(f);
880  CanonicalForm fc=f/c;
881  F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
882  F.insert (CFFactor (c, 1));
883 #endif
884  }
885  else // char p, multivariate
886  {
887  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
888  // use FLINT
889  nmod_poly_t FLINTmipo;
890  fq_nmod_ctx_t fq_con;
891  fq_nmod_mpoly_ctx_t ctx;
892 
893  nmod_poly_init (FLINTmipo, ch);
894  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
895 
896  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
897  fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
898 
899  fq_nmod_mpoly_t FLINTF;
900  fq_nmod_mpoly_init(FLINTF,ctx);
901  convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
902  fq_nmod_mpoly_factor_t res;
903  fq_nmod_mpoly_factor_init (res, ctx);
904  fq_nmod_mpoly_factor (res, FLINTF, ctx);
905  F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
906  //F.insert (CFFactor (Lc (f), 1));
907 
908  fq_nmod_mpoly_factor_clear (res, ctx);
909  fq_nmod_mpoly_clear (FLINTF, ctx);
910  nmod_poly_clear (FLINTmipo);
911  fq_nmod_mpoly_ctx_clear (ctx);
913  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
914  return F;
915  #elif defined(HAVE_NTL)
916  F= FqFactorize (f, alpha);
917  #else
918  factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
919  return CFFList (CFFactor (f, 1));
920  #endif
921  }
922  }
923  else // Q(a)[x]
924  {
925  if (f.isUnivariate())
926  {
927  F= AlgExtFactorize (f, alpha);
928  }
929  else //Q(a)[x1,...,xn]
930  {
931  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
932  F= ratFactorize (f, alpha);
933  #else
934  factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
935  return CFFList (CFFactor (f, 1));
936  #endif
937  }
938  }
939  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
940  return F;
941 }
942 
943 /**
944  * squarefree factorization
945 **/
946 CFFList sqrFree ( const CanonicalForm & f, bool sort )
947 {
948 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
949  CFFList result;
950 
951  if ( getCharacteristic() == 0 )
952  result = sqrFreeZ( f );
953  else
954  {
955  Variable alpha;
956  if (hasFirstAlgVar (f, alpha))
957  result = FqSqrf( f, alpha );
958  else
959  result= FpSqrf (f);
960  }
961  if (sort)
962  {
963  CFFactor buf= result.getFirst();
964  result.removeFirst();
966  result.insert (buf);
967  }
968  return result;
969 }
970 
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.
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
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:4084
g
Definition: cfModGcd.cc:4092
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4091
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:64
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:38
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:56
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:63
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:54
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition: cf_defs.h:50
#define GaloisFieldDomain
Definition: cf_defs.h:24
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:946
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:134
int level() const
Definition: factory.h:150
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