source: git/factory/cf_factor.cc @ edd818

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