source: git/factory/cf_factor.cc @ 1f4ed3

spielwiese
Last change on this file since 1f4ed3 was 1f4ed3, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: use for univariate factorization over Fq
  • Property mode set to 100644
File size: 20.0 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
634#ifdef HAVE_NTL
635CanonicalForm fntl ( const CanonicalForm & f, int j )
636{
637  ZZX f1=convertFacCF2NTLZZX(f);
638  return convertZZ2CF(coeff(f1,j));
639}
640#endif
641
642CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
643{
644  if ( f.inCoeffDomain() )
645    return CFFList( f );
646  //out_cf("factorize:",f,"==================================\n");
647  //out_cf("mipo:",getMipo(alpha),"\n");
648  CFFList F;
649  ASSERT( alpha.level() < 0, "not an algebraic extension" );
650  int ch=getCharacteristic();
651  if (f.isUnivariate()&& (ch>0))
652  {
653    #ifdef HAVE_NTL
654    if  (isOn(SW_USE_NTL))
655    {
656      //USE NTL
657      if (ch>2)
658      {
659#if (HAVE_FLINT && __FLINT_VERSION_MINOR >= 4)
660        nmod_poly_t FLINTmipo, leadingCoeff;
661        fq_nmod_ctx_t fq_con;
662
663        nmod_poly_init (FLINTmipo, getCharacteristic());
664        nmod_poly_init (leadingCoeff, getCharacteristic());
665        convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
666
667        fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
668        fq_nmod_poly_t FLINTF;
669        convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
670        fq_nmod_poly_factor_t res;
671        fq_nmod_poly_factor_init (res, fq_con);
672        fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
673        F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
674        F.insert (CFFactor (Lc (f), 1));
675
676        fq_nmod_poly_factor_clear (res, fq_con);
677        fq_nmod_poly_clear (FLINTF, fq_con);
678        nmod_poly_clear (FLINTmipo);
679        nmod_poly_clear (leadingCoeff);
680        fq_nmod_ctx_clear (fq_con);
681#else
682        // First all cases with characteristic !=2
683        // set remainder
684        if (fac_NTL_char != getCharacteristic())
685        {
686          fac_NTL_char = getCharacteristic();
687          zz_p::init(getCharacteristic());
688        }
689
690        // set minimal polynomial in NTL
691        zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
692        zz_pE::init (minPo);
693
694        // convert to NTL
695        zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
696        zz_pE leadcoeff= LeadCoeff(f1);
697
698        //make monic
699        f1=f1 / leadcoeff;
700
701        // factorize using NTL
702        vec_pair_zz_pEX_long factors;
703        CanZass(factors,f1);
704
705        // return converted result
706        F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
707#endif
708      }
709      else if (/*getCharacteristic()*/ch==2)
710      {
711        // special case : GF2
712
713        // remainder is two ==> nothing to do
714
715        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
716        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
717        GF2E::init (minPo);
718
719        // convert to NTL again using the faster conversion routines
720        GF2EX f1;
721        if (isPurePoly(f))
722        {
723          GF2X f_tmp=convertFacCF2NTLGF2X(f);
724          f1=to_GF2EX(f_tmp);
725        }
726        else
727        {
728          f1=convertFacCF2NTLGF2EX(f,minPo);
729        }
730
731        // make monic (in Z/2(a))
732        GF2E f1_coef=LeadCoeff(f1);
733        MakeMonic(f1);
734
735        // factorize using NTL
736        vec_pair_GF2EX_long factors;
737        CanZass(factors,f1);
738
739        // return converted result
740        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
741      }
742      else
743      {
744      }
745    }
746    else
747    #endif
748    {
749      F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
750    }
751  }
752  else if (ch>0)
753  {
754    #ifdef HAVE_NTL
755    F= FqFactorize (f, alpha);
756    #else
757    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
758    factoryError ("multivariate factorization not implemented");
759    return CFFList (CFFactor (f, 1));
760    #endif
761
762  }
763  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
764  {
765    F= AlgExtFactorize (f, alpha);
766  }
767  else //Q(a)[x1,...,xn]
768  {
769#ifdef HAVE_NTL
770    F= ratFactorize (f, alpha);
771#else
772    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
773    factoryError ("multivariate factorization not implemented");
774    return CFFList (CFFactor (f, 1));
775#endif
776  }
777  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
778  return F;
779}
780
781CFFList sqrFree ( const CanonicalForm & f, bool sort )
782{
783//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
784    CFFList result;
785
786    if ( getCharacteristic() == 0 )
787        result = sqrFreeZ( f );
788    else
789    {
790        Variable alpha;
791        if (hasFirstAlgVar (f, alpha))
792          result = FqSqrf( f, alpha );
793        else
794          result= FpSqrf (f);
795    }
796    if (sort)
797    {
798      CFFactor buf= result.getFirst();
799      result.removeFirst();
800      result= sortCFFList (result);
801      result.insert (buf);
802    }
803    return result;
804}
805
806bool isSqrFree ( const CanonicalForm & f )
807{
808//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
809    if ( getCharacteristic() == 0 )
810        return isSqrFreeZ( f );
811    else
812        return isSqrFreeFp( f );
813}
814
Note: See TracBrowser for help on using the repository browser.