source: git/factory/cf_factor.cc @ 903f87

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