source: git/factory/cf_factor.cc @ 24a611c

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