source: git/factory/cf_factor.cc @ 72ebdb

spielwiese
Last change on this file since 72ebdb was e4fe2b, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
FIX: Fixed huge BUG in cf_gmp.h CHG: starting to cleanup factory
  • Property mode set to 100644
File size: 20.1 KB
Line 
1/* Emacs edit mode for this file is -*- C++ -*- */
2/* $Id$ */
3
4//{{{ docu
5//
6// cf_factor.cc - factorization and square free algorithms.
7//
8// Used by: fac_multivar.cc, fac_univar.cc, cf_irred.cc
9//
10// Header file: cf_algorithm.h
11//
12//}}}
13
14#include "config.h"
15
16#include "cf_assert.h"
17
18#include "cf_defs.h"
19#include "canonicalform.h"
20#include "cf_iter.h"
21#include "fac_berlekamp.h"
22#include "fac_cantzass.h"
23#include "fac_univar.h"
24#include "fac_multivar.h"
25#include "fac_sqrfree.h"
26#include "cf_algorithm.h"
27#include "facFqFactorize.h"
28#include "cf_map.h"
29#include "algext.h"
30#include "facAlgExt.h"
31#include "facFactorize.h"
32#include "singext.h"
33
34#include "int_int.h"
35#ifdef HAVE_NTL
36#include "NTLconvert.h"
37#endif
38
39#include "cf_gmp.h"
40
41int getExp(); /* cf_char.cc */
42
43//static bool isUnivariateBaseDomain( const CanonicalForm & f )
44//{
45//    CFIterator i = f;
46//    bool ok = i.coeff().inBaseDomain();
47//    i++;
48//    while ( i.hasTerms() && ( ok = ok && i.coeff().inBaseDomain() ) ) i++;
49//    return ok;
50//}
51
52void find_exp(const CanonicalForm & f, int * exp_f)
53{
54  if ( ! f.inCoeffDomain() )
55  {
56    int e=f.level();
57    CFIterator i = f;
58    if (e>=0)
59    {
60      if (i.exp() > exp_f[e]) exp_f[e]=i.exp();
61    }
62    for (; i.hasTerms(); i++ )
63    {
64      find_exp(i.coeff(), exp_f);
65    }
66  }
67}
68
69int find_mvar(const CanonicalForm & f)
70{
71  int mv=f.level();
72  int *exp_f=new int[mv+1];
73  int i;
74  for(i=mv;i>0;i--) exp_f[i]=0;
75  find_exp(f,exp_f);
76  for(i=mv;i>0;i--)
77  {
78    if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
79    {
80      mv=i;
81    }
82  }
83  delete[] exp_f;
84  return mv;
85}
86
87#if 0
88//#ifndef NOSTREAMIO
89void out_cf(const char *s1,const CanonicalForm &f,const char *s2)
90{
91  printf("%s",s1);
92  if (f.isZero()) printf("+0");
93  //else if (! f.inCoeffDomain() )
94  else if (! f.inBaseDomain() )
95  {
96    int l = f.level();
97    for ( CFIterator i = f; i.hasTerms(); i++ )
98    {
99      int e=i.exp();
100      if (i.coeff().isOne())
101      {
102        printf("+");
103        if (e==0) printf("1");
104        else
105        {
106          printf("v(%d)",l);
107          if (e!=1) printf("^%d",e);
108        }
109      }
110      else
111      {
112        out_cf("+(",i.coeff(),")");
113        if (e!=0)
114        {
115          printf("*v(%d)",l);
116          if (e!=1) printf("^%d",e);
117        }
118      }
119    }
120  }
121  else
122  {
123    if ( f.isImm() )
124    {
125      printf("+%d",f.intval());
126    }
127    else
128    {
129    #ifdef NOSTREAMIO
130      if (f.inZ())
131      {
132        mpz_t m;
133        gmp_numerator(f,m);
134        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
135        str = mpz_get_str( str, 10, m );
136        printf("%s",str);
137        delete[] str;
138        mpz_clear(m);
139      }
140      else if (f.inQ())
141      {
142        mpz_t m;
143        gmp_numerator(f,m);
144        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
145        str = mpz_get_str( str, 10, m );
146        printf("%s/",str);
147        delete[] str;
148        mpz_clear(m);
149        gmp_denominator(f,m);
150        str = new char[mpz_sizeinbase( m, 10 ) + 2];
151        str = mpz_get_str( str, 10, m );
152        printf("%s",str);
153        delete[] str;
154        mpz_clear(m);
155      }
156    #else
157       std::cout << f;
158    #endif
159    }
160    //if (f.inZ()) printf("(Z)");
161    //else if (f.inQ()) printf("(Q)");
162    //else if (f.inFF()) printf("(FF)");
163    //else if (f.inPP()) printf("(PP)");
164    //else if (f.inGF()) printf("(PP)");
165    //else
166    if (f.inExtension()) printf("E(%d)",f.level());
167  }
168  printf("%s",s2);
169}
170void out_cff(CFFList &L)
171{
172  //int n = L.length();
173  CFFListIterator J=L;
174  int j=0;
175  for ( ; J.hasItem(); J++, j++ )
176  {
177    printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
178    printf("%d\n", J.getItem().exp());
179  }
180}
181void test_cff(CFFList &L,const CanonicalForm & f)
182{
183  //int n = L.length();
184  CFFListIterator J=L;
185  CanonicalForm t=1;
186  int j=0;
187  if (!(L.getFirst().factor().inCoeffDomain()))
188    printf("first entry is not const\n");
189  for ( ; J.hasItem(); J++, j++ )
190  {
191    CanonicalForm tt=J.getItem().factor();
192    if (tt.inCoeffDomain() && (j!=0))
193      printf("other entry is const\n");
194    j=J.getItem().exp();
195    while(j>0) { t*=tt; j--; }
196  }
197  if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
198}
199//#endif
200#endif
201
202bool isPurePoly_m(const CanonicalForm & f)
203{
204  if (f.inBaseDomain()) return true;
205  if (f.level()<0) return false;
206  for (CFIterator i=f;i.hasTerms();i++)
207  {
208    if (!isPurePoly_m(i.coeff())) return false;
209  }
210  return true;
211}
212bool isPurePoly(const CanonicalForm & f)
213{
214  if (f.level()<=0) return false;
215  for (CFIterator i=f;i.hasTerms();i++)
216  {
217    if (!(i.coeff().inBaseDomain())) return false;
218  }
219  return true;
220}
221
222
223///////////////////////////////////////////////////////////////
224// get_max_degree_Variable returns Variable with             //
225// highest degree. We assume f is *not* a constant!          //
226///////////////////////////////////////////////////////////////
227Variable
228get_max_degree_Variable(const CanonicalForm & f)
229{
230  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
231  int max=0, maxlevel=0, n=level(f);
232  for ( int i=1; i<=n; i++ )
233  {
234    if (degree(f,Variable(i)) >= max)
235    {
236      max= degree(f,Variable(i)); maxlevel= i;
237    }
238  }
239  return Variable(maxlevel);
240}
241
242///////////////////////////////////////////////////////////////
243// get_Terms: Split the polynomial in the containing terms.  //
244// getTerms: the real work is done here.                     //
245///////////////////////////////////////////////////////////////
246void
247getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result )
248{
249  if ( getNumVars(f) == 0 ) result.append(f*t);
250  else{
251    Variable x(level(f));
252    for ( CFIterator i=f; i.hasTerms(); i++ )
253      getTerms( i.coeff(), t*power(x,i.exp()), result);
254  }
255}
256CFList
257get_Terms( const CanonicalForm & f ){
258  CFList result,dummy,dummy2;
259  CFIterator i;
260  CFListIterator j;
261
262  if ( getNumVars(f) == 0 ) result.append(f);
263  else{
264    Variable _x(level(f));
265    for ( i=f; i.hasTerms(); i++ ){
266      getTerms(i.coeff(), 1, dummy);
267      for ( j=dummy; j.hasItem(); j++ )
268        result.append(j.getItem() * power(_x, i.exp()));
269
270      dummy= dummy2; // have to initalize new
271    }
272  }
273  return result;
274}
275
276
277///////////////////////////////////////////////////////////////
278// homogenize homogenizes f with Variable x                  //
279///////////////////////////////////////////////////////////////
280
281CanonicalForm
282homogenize( const CanonicalForm & f, const Variable & x)
283{
284#if 0
285  int maxdeg=totaldegree(f), deg;
286  CFIterator i;
287  CanonicalForm elem, result(0);
288
289  for (i=f; i.hasTerms(); i++)
290  {
291    elem= i.coeff()*power(f.mvar(),i.exp());
292    deg = totaldegree(elem);
293    if ( deg < maxdeg )
294      result += elem * power(x,maxdeg-deg);
295    else
296      result+=elem;
297  }
298  return result;
299#else
300  CFList Newlist, Termlist= get_Terms(f);
301  int maxdeg=totaldegree(f), deg;
302  CFListIterator i;
303  CanonicalForm elem, result(0);
304
305  for (i=Termlist; i.hasItem(); i++)
306  {
307    elem= i.getItem();
308    deg = totaldegree(elem);
309    if ( deg < maxdeg )
310      Newlist.append(elem * power(x,maxdeg-deg));
311    else
312      Newlist.append(elem);
313  }
314  for (i=Newlist; i.hasItem(); i++) // rebuild
315    result += i.getItem();
316
317  return result;
318#endif
319}
320
321CanonicalForm
322homogenize( const CanonicalForm & f, const Variable & x, const Variable & v1, const Variable & v2)
323{
324#if 0
325  int maxdeg=totaldegree(f), deg;
326  CFIterator i;
327  CanonicalForm elem, result(0);
328
329  for (i=f; i.hasTerms(); i++)
330  {
331    elem= i.coeff()*power(f.mvar(),i.exp());
332    deg = totaldegree(elem);
333    if ( deg < maxdeg )
334      result += elem * power(x,maxdeg-deg);
335    else
336      result+=elem;
337  }
338  return result;
339#else
340  CFList Newlist, Termlist= get_Terms(f);
341  int maxdeg=totaldegree(f), deg;
342  CFListIterator i;
343  CanonicalForm elem, result(0);
344
345  for (i=Termlist; i.hasItem(); i++)
346  {
347    elem= i.getItem();
348    deg = totaldegree(elem,v1,v2);
349    if ( deg < maxdeg )
350      Newlist.append(elem * power(x,maxdeg-deg));
351    else
352      Newlist.append(elem);
353  }
354  for (i=Newlist; i.hasItem(); i++) // rebuild
355    result += i.getItem();
356
357  return result;
358#endif
359}
360
361int singular_homog_flag=1;
362
363int cmpCF( const CFFactor & f, const CFFactor & g )
364{
365  if (f.exp() > g.exp()) return 1;
366  if (f.exp() < g.exp()) return 0;
367  if (f.factor() > g.factor()) return 1;
368  return 0;
369}
370
371CFFList factorize ( const CanonicalForm & f, bool issqrfree )
372{
373  if ( f.inCoeffDomain() )
374        return CFFList( f );
375  int mv=f.level();
376  int org_v=mv;
377  //out_cf("factorize:",f,"==================================\n");
378  if (! f.isUnivariate() )
379  {
380    if ( singular_homog_flag && f.isHomogeneous())
381    {
382      Variable xn = get_max_degree_Variable(f);
383      int d_xn = degree(f,xn);
384      CFMap n;
385      CanonicalForm F = compress(f(1,xn),n);
386      CFFList Intermediatelist;
387      Intermediatelist = factorize(F);
388      CFFList Homoglist;
389      CFFListIterator j;
390      for ( j=Intermediatelist; j.hasItem(); j++ )
391      {
392        Homoglist.append(
393            CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
394      }
395      CFFList Unhomoglist;
396      CanonicalForm unhomogelem;
397      for ( j=Homoglist; j.hasItem(); j++ )
398      {
399        unhomogelem= homogenize(j.getItem().factor(),xn);
400        Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
401        d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
402      }
403      if ( d_xn != 0 ) // have to append xn^(d_xn)
404        Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
405      if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
406      return Unhomoglist;
407    }
408    mv=find_mvar(f);
409    if ( getCharacteristic() == 0 )
410    {
411      if (mv!=f.level())
412      {
413        swapvar(f,Variable(mv),f.mvar());
414      }
415    }
416    else
417    {
418      if (mv!=1)
419      {
420        swapvar(f,Variable(mv),Variable(1));
421        org_v=1;
422      }
423    }
424  }
425  CFFList F;
426  if ( getCharacteristic() > 0 )
427  {
428    if (f.isUnivariate())
429    {
430      #ifdef HAVE_NTL
431      if (isOn(SW_USE_NTL) && (isPurePoly(f)))
432      {
433        // USE NTL
434        if (getCharacteristic()!=2)
435        {
436          if (fac_NTL_char!=getCharacteristic())
437          {
438            fac_NTL_char=getCharacteristic();
439            #ifndef NTL_ZZ
440            if (fac_NTL_char >NTL_SP_BOUND)
441            {
442              ZZ r;
443              r=getCharacteristic();
444              ZZ_pContext ccc(r);
445              ccc.restore();
446              ZZ_p::init(r);
447            }
448            else
449            #endif
450            {
451              #ifdef NTL_ZZ
452              ZZ r;
453              r=getCharacteristic();
454              ZZ_pContext ccc(r);
455              #else
456              zz_pContext ccc(getCharacteristic());
457              #endif
458              ccc.restore();
459              #ifdef NTL_ZZ
460              ZZ_p::init(r);
461              #else
462              zz_p::init(getCharacteristic());
463              #endif
464            }
465          }
466          #ifndef NTL_ZZ
467          if (fac_NTL_char >NTL_SP_BOUND)
468          {
469            // convert to NTL
470            ZZ_pX f1=convertFacCF2NTLZZpX(f);
471            ZZ_p leadcoeff = LeadCoeff(f1);
472            //make monic
473            f1=f1 / LeadCoeff(f1);
474            // factorize
475            vec_pair_ZZ_pX_long factors;
476            CanZass(factors,f1);
477            // convert back to factory
478            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
479          }
480          else
481          #endif
482          {
483            // convert to NTL
484            #ifdef NTL_ZZ
485            ZZ_pX f1=convertFacCF2NTLZZpX(f);
486            ZZ_p leadcoeff = LeadCoeff(f1);
487            #else
488            zz_pX f1=convertFacCF2NTLzzpX(f);
489            zz_p leadcoeff = LeadCoeff(f1);
490            #endif
491            //make monic
492            f1=f1 / LeadCoeff(f1);
493            // factorize
494            #ifdef NTL_ZZ
495            vec_pair_ZZ_pX_long factors;
496            #else
497            vec_pair_zz_pX_long factors;
498            #endif
499            CanZass(factors,f1);
500            // convert back to factory
501            #ifdef NTL_ZZ
502            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
503            #else
504            F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
505            #endif
506          }
507          //test_cff(F,f);
508        }
509        else /*getCharacteristic()==2*/
510        {
511          // Specialcase characteristic==2
512          if (fac_NTL_char!=2)
513          {
514            fac_NTL_char=2;
515            zz_p::init(2);
516          }
517          // convert to NTL using the faster conversion routine for characteristic 2
518          GF2X f1=convertFacCF2NTLGF2X(f);
519          // no make monic necessary in GF2
520          //factorize
521          vec_pair_GF2X_long factors;
522          CanZass(factors,f1);
523
524          // convert back to factory again using the faster conversion routine for vectors over GF2X
525          F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
526        }
527      }
528      else
529      #endif
530      {  // Use Factory without NTL
531        if ( isOn( SW_BERLEKAMP ) )
532          F=FpFactorizeUnivariateB( f, issqrfree );
533        else
534          F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
535      }
536    }
537    else
538    {
539      #ifdef HAVE_NTL
540      if (issqrfree)
541      {
542        CFList factors;
543        Variable alpha;
544        if (CFFactory::gettype() == GaloisFieldDomain)
545          factors= GFSqrfFactorize (f);
546        else if (hasFirstAlgVar (f, alpha))
547          factors= FqSqrfFactorize (f, alpha);
548        else
549          factors= FpSqrfFactorize (f);
550        for (CFListIterator i= factors; i.hasItem(); i++)
551          F.append (CFFactor (i.getItem(), 1));
552      }
553      else
554      {
555        Variable alpha;
556        if (CFFactory::gettype() == GaloisFieldDomain)
557          F= GFFactorize (f);
558        else if (hasFirstAlgVar (f, alpha))
559          F= FqFactorize (f, alpha);
560        else
561          F= FpFactorize (f);
562      }
563      #else
564      ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
565      #endif
566    }
567  }
568  else
569  {
570    bool on_rational = isOn(SW_RATIONAL);
571    On(SW_RATIONAL);
572    CanonicalForm cd = bCommonDen( f );
573    CanonicalForm fz = f * cd;
574    Off(SW_RATIONAL);
575    if ( f.isUnivariate() )
576    {
577      #ifdef HAVE_NTL
578      if ((isOn(SW_USE_NTL)) && (isPurePoly(f)))
579      {
580        //USE NTL
581        CanonicalForm ic=icontent(fz);
582        fz/=ic;
583        ZZ c;
584        vec_pair_ZZX_long factors;
585        //factorize the converted polynomial
586        factor(c,factors,convertFacCF2NTLZZX(fz));
587
588        //convert the result back to Factory
589        F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
590        if ( ! ic.isOne() )
591        {
592          if ( F.getFirst().factor().inCoeffDomain() )
593          {
594            CFFactor new_first( F.getFirst().factor() * ic );
595            F.removeFirst();
596            F.insert( new_first );
597          }
598          else
599            F.insert( CFFactor( ic ) );
600        }
601        else
602        {
603          if ( !F.getFirst().factor().inCoeffDomain() )
604          {
605            CFFactor new_first( 1 );
606            F.insert( new_first );
607          }
608        }
609        //if ( F.getFirst().factor().isOne() )
610        //{
611        //  F.removeFirst();
612        //}
613        //printf("NTL:\n");out_cff(F);
614        //F=ZFactorizeUnivariate( fz, issqrfree );
615        //printf("fac.:\n");out_cff(F);
616      }
617      else
618      #endif
619      {
620        //Use Factory without NTL
621        F = ZFactorizeUnivariate( fz, issqrfree );
622      }
623    }
624    else
625    {
626      F = ZFactorizeMultivariate( fz, issqrfree );
627    }
628
629    if ( on_rational )
630      On(SW_RATIONAL);
631    if ( ! cd.isOne() )
632    {
633      if ( F.getFirst().factor().inCoeffDomain() )
634      {
635        CFFactor new_first( F.getFirst().factor() / cd );
636        F.removeFirst();
637        F.insert( new_first );
638      }
639      else
640      {
641        F.insert( CFFactor( 1/cd ) );
642      }
643    }
644  }
645
646  if ((mv!=org_v) && (! f.isUnivariate() ))
647  {
648    CFFListIterator J=F;
649    for ( ; J.hasItem(); J++)
650    {
651      swapvar(J.getItem().factor(),Variable(mv),Variable(org_v));
652    }
653    swapvar(f,Variable(mv),Variable(org_v));
654  }
655  //out_cff(F);
656  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
657  return F;
658}
659
660#ifdef HAVE_NTL
661CanonicalForm fntl ( const CanonicalForm & f, int j )
662{
663  ZZX f1=convertFacCF2NTLZZX(f);
664  return convertZZ2CF(coeff(f1,j));
665}
666#endif
667
668CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
669{
670  if ( f.inCoeffDomain() )
671    return CFFList( f );
672  //out_cf("factorize:",f,"==================================\n");
673  //out_cf("mipo:",getMipo(alpha),"\n");
674  CFFList F;
675  ASSERT( alpha.level() < 0, "not an algebraic extension" );
676  int ch=getCharacteristic();
677  if (f.isUnivariate()&& (ch>0))
678  {
679    #ifdef HAVE_NTL
680    if  (isOn(SW_USE_NTL))
681    {
682      //USE NTL
683      if (ch>2)
684      {
685        // First all cases with characteristic !=2
686        // set remainder
687        if (fac_NTL_char!=getCharacteristic())
688        {
689          fac_NTL_char=getCharacteristic();
690          #ifdef NTL_ZZ
691          ZZ r;
692          r=getCharacteristic();
693          ZZ_pContext ccc(r);
694          #else
695          zz_pContext ccc(getCharacteristic());
696          #endif
697          ccc.restore();
698          #ifdef NTL_ZZ
699          ZZ_p::init(r);
700          #else
701          zz_p::init(getCharacteristic());
702          #endif
703        }
704
705        // set minimal polynomial in NTL
706        #ifdef NTL_ZZ
707        ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha));
708        ZZ_pEContext c(minPo);
709        #else
710        zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
711        zz_pEContext c(minPo);
712        #endif
713
714        c.restore();
715
716        // convert to NTL
717        #ifdef NTL_ZZ
718        ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo);
719        ZZ_pE leadcoeff= LeadCoeff(f1);
720        #else
721        zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
722        zz_pE leadcoeff= LeadCoeff(f1);
723        #endif
724
725        //make monic
726        f1=f1 / leadcoeff;
727
728        // factorize using NTL
729        #ifdef NTL_ZZ
730        vec_pair_ZZ_pEX_long factors;
731        #else
732        vec_pair_zz_pEX_long factors;
733        #endif
734        CanZass(factors,f1);
735
736        // return converted result
737        #ifdef NTL_ZZ
738        F=convertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
739        #else
740        F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
741        #endif
742      }
743      else if (/*getCharacteristic()*/ch==2)
744      {
745        // special case : GF2
746
747        // remainder is two ==> nothing to do
748        // set remainder
749        ZZ r;
750        r=getCharacteristic();
751        ZZ_pContext ccc(r);
752        ccc.restore();
753
754        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
755        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
756        GF2EContext c(minPo);
757        c.restore();
758
759        // convert to NTL again using the faster conversion routines
760        GF2EX f1;
761        if (isPurePoly(f))
762        {
763          GF2X f_tmp=convertFacCF2NTLGF2X(f);
764          f1=to_GF2EX(f_tmp);
765        }
766        else
767        {
768          f1=convertFacCF2NTLGF2EX(f,minPo);
769        }
770
771        // make monic (in Z/2(a))
772        GF2E f1_coef=LeadCoeff(f1);
773        MakeMonic(f1);
774
775        // factorize using NTL
776        vec_pair_GF2EX_long factors;
777        CanZass(factors,f1);
778
779        // return converted result
780        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
781      }
782      else
783      {
784      }
785    }
786    else
787    #endif
788    {
789      F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
790    }
791  }
792  else if (ch>0)
793  {
794    #ifdef HAVE_NTL
795    F= FqFactorize (f, alpha);
796    #else
797    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
798    #endif
799
800  }
801  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
802  {
803    F= AlgExtFactorize (f, alpha);
804  }
805  else //Q(a)[x1,...,xn]
806  {
807    F= ratFactorize (f, alpha);
808  }
809  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
810  return F;
811}
812
813CFFList sqrFree ( const CanonicalForm & f )
814{
815//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
816    CFFList result;
817
818    if ( getCharacteristic() == 0 )
819        result = sqrFreeZ( f );
820    else
821        result = sqrFreeFp( f );
822
823    //return ( sort ? sortCFFList( result ) : result );
824    return result;
825}
826
827bool isSqrFree ( const CanonicalForm & f )
828{
829//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
830    if ( getCharacteristic() == 0 )
831        return isSqrFreeZ( f );
832    else
833        return isSqrFreeFp( f );
834}
835
Note: See TracBrowser for help on using the repository browser.