source: git/factory/cf_factor.cc @ faa1b8d

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