source: git/factory/cf_factor.cc @ 8e4601

jengelh-datetimespielwiese
Last change on this file since 8e4601 was 8e4601, checked in by Adrian <adi_popescum@…>, 10 years ago
64 bits for Spielwiese Last
  • Property mode set to 100644
File size: 21.6 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 1
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         long a= imm2int (f.getval());
132         if ( a == gf_q )
133           printf ("+%ld", a);
134         else  if ( a == 0L )
135           printf ("+1");
136         else  if ( a == 1L )
137           printf ("+%c",gf_name);
138         else
139         {
140           printf ("+%c",gf_name);
141           printf ("^%ld",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  //out_cf("factorize:",f,"==================================\n");
396  if (! f.isUnivariate() )
397  {
398    if ( singular_homog_flag && f.isHomogeneous())
399    {
400      Variable xn = get_max_degree_Variable(f);
401      int d_xn = degree(f,xn);
402      CFMap n;
403      CanonicalForm F = compress(f(1,xn),n);
404      CFFList Intermediatelist;
405      Intermediatelist = factorize(F);
406      CFFList Homoglist;
407      CFFListIterator j;
408      for ( j=Intermediatelist; j.hasItem(); j++ )
409      {
410        Homoglist.append(
411            CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
412      }
413      CFFList Unhomoglist;
414      CanonicalForm unhomogelem;
415      for ( j=Homoglist; j.hasItem(); j++ )
416      {
417        unhomogelem= homogenize(j.getItem().factor(),xn);
418        Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
419        d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
420      }
421      if ( d_xn != 0 ) // have to append xn^(d_xn)
422        Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
423      if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
424      return Unhomoglist;
425    }
426  }
427  CFFList F;
428  if ( getCharacteristic() > 0 )
429  {
430    if (f.isUnivariate())
431    {
432#ifdef HAVE_FLINT
433      nmod_poly_t f1;
434      convertFacCF2nmod_poly_t (f1, f);
435      nmod_poly_factor_t result;
436      nmod_poly_factor_init (result);
437      mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
438      F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
439      nmod_poly_factor_clear (result);
440      nmod_poly_clear (f1);
441#else
442#ifdef HAVE_NTL
443      if (isOn(SW_USE_NTL) && (isPurePoly(f)))
444      {
445        // USE NTL
446        if (getCharacteristic()!=2)
447        {
448          if (fac_NTL_char != getCharacteristic())
449          {
450            fac_NTL_char = getCharacteristic();
451            #ifndef NTL_ZZ
452            if (fac_NTL_char > NTL_SP_BOUND)
453            {
454              ZZ r;
455              r=getCharacteristic();
456              ZZ_pContext ccc(r);
457              ccc.restore();
458              ZZ_p::init(r);
459            }
460            else
461            #endif
462            {
463              #ifdef NTL_ZZ
464              ZZ r;
465              r=getCharacteristic();
466              ZZ_pContext ccc(r);
467              #else
468              zz_pContext ccc(getCharacteristic());
469              #endif
470              ccc.restore();
471              #ifdef NTL_ZZ
472              ZZ_p::init(r);
473              #else
474              zz_p::init(getCharacteristic());
475              #endif
476            }
477          }
478          #ifndef NTL_ZZ
479          if (fac_NTL_char > NTL_SP_BOUND)
480          {
481            // convert to NTL
482            ZZ_pX f1=convertFacCF2NTLZZpX(f);
483            ZZ_p leadcoeff = LeadCoeff(f1);
484            //make monic
485            f1=f1 / LeadCoeff(f1);
486            // factorize
487            vec_pair_ZZ_pX_long factors;
488            CanZass(factors,f1);
489            // convert back to factory
490            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
491          }
492          else
493          #endif
494          {
495            // convert to NTL
496            #ifdef NTL_ZZ
497            ZZ_pX f1=convertFacCF2NTLZZpX(f);
498            ZZ_p leadcoeff = LeadCoeff(f1);
499            #else
500            zz_pX f1=convertFacCF2NTLzzpX(f);
501            zz_p leadcoeff = LeadCoeff(f1);
502            #endif
503            //make monic
504            f1=f1 / LeadCoeff(f1);
505            // factorize
506            #ifdef NTL_ZZ
507            vec_pair_ZZ_pX_long factors;
508            #else
509            vec_pair_zz_pX_long factors;
510            #endif
511            CanZass(factors,f1);
512            // convert back to factory
513            #ifdef NTL_ZZ
514            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
515            #else
516            F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
517            #endif
518          }
519          //test_cff(F,f);
520        }
521        else /*getCharacteristic()==2*/
522        {
523          // Specialcase characteristic==2
524          if (fac_NTL_char != 2)
525          {
526            fac_NTL_char = 2;
527            zz_p::init(2);
528          }
529          // convert to NTL using the faster conversion routine for characteristic 2
530          GF2X f1=convertFacCF2NTLGF2X(f);
531          // no make monic necessary in GF2
532          //factorize
533          vec_pair_GF2X_long factors;
534          CanZass(factors,f1);
535
536          // convert back to factory again using the faster conversion routine for vectors over GF2X
537          F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
538        }
539      }
540      else
541#endif //HAVE_NTL
542      {  // Use Factory without NTL
543        if ( isOn( SW_BERLEKAMP ) )
544          F=FpFactorizeUnivariateB( f, issqrfree );
545        else
546          F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
547      }
548#endif //HAVE_FLINT
549    }
550    else
551    {
552      #ifdef HAVE_NTL
553      if (issqrfree)
554      {
555        CFList factors;
556        Variable alpha;
557        if (CFFactory::gettype() == GaloisFieldDomain)
558          factors= GFSqrfFactorize (f);
559        else if (hasFirstAlgVar (f, alpha))
560          factors= FqSqrfFactorize (f, alpha);
561        else
562          factors= FpSqrfFactorize (f);
563        for (CFListIterator i= factors; i.hasItem(); i++)
564          F.append (CFFactor (i.getItem(), 1));
565      }
566      else
567      {
568        Variable alpha;
569        if (CFFactory::gettype() == GaloisFieldDomain)
570          F= GFFactorize (f);
571        else if (hasFirstAlgVar (f, alpha))
572          F= FqFactorize (f, alpha);
573        else
574          F= FpFactorize (f);
575      }
576      #else
577      ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
578      factoryError ("multivariate factorization not implemented");
579      return CFFList (CFFactor (f, 1));
580      #endif
581    }
582  }
583  else
584  {
585    bool on_rational = isOn(SW_RATIONAL);
586    On(SW_RATIONAL);
587    CanonicalForm cd = bCommonDen( f );
588    CanonicalForm fz = f * cd;
589    Off(SW_RATIONAL);
590    if ( f.isUnivariate() )
591    {
592      #ifdef HAVE_NTL
593      if ((isOn(SW_USE_NTL)) && (isPurePoly(f)))
594      {
595        //USE NTL
596        CanonicalForm ic=icontent(fz);
597        fz/=ic;
598        ZZ c;
599        vec_pair_ZZX_long factors;
600        //factorize the converted polynomial
601        factor(c,factors,convertFacCF2NTLZZX(fz));
602
603        //convert the result back to Factory
604        F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
605        if ( ! ic.isOne() )
606        {
607          if ( F.getFirst().factor().inCoeffDomain() )
608          {
609            CFFactor new_first( F.getFirst().factor() * ic );
610            F.removeFirst();
611            F.insert( new_first );
612          }
613          else
614            F.insert( CFFactor( ic ) );
615        }
616        else
617        {
618          if ( !F.getFirst().factor().inCoeffDomain() )
619          {
620            CFFactor new_first( 1 );
621            F.insert( new_first );
622          }
623        }
624        //if ( F.getFirst().factor().isOne() )
625        //{
626        //  F.removeFirst();
627        //}
628        //printf("NTL:\n");out_cff(F);
629        //F=ZFactorizeUnivariate( fz, issqrfree );
630        //printf("fac.:\n");out_cff(F);
631      }
632      #else
633      {
634        //Use Factory without NTL
635        //F = ZFactorizeUnivariate( fz, issqrfree );
636        factoryError ("univariate factorization over Z not implemented"); 
637        return CFFList (CFFactor (f, 1));
638      }
639      #endif
640    }
641    else
642    {
643      #ifdef HAVE_NTL
644      On (SW_RATIONAL);
645      if (issqrfree)
646      {
647        CFList factors;
648        factors= ratSqrfFactorize (fz);
649        for (CFListIterator i= factors; i.hasItem(); i++)
650          F.append (CFFactor (i.getItem(), 1));
651      }
652      else
653        F = ratFactorize (fz);
654      Off (SW_RATIONAL);
655      #else
656      factoryError ("multivariate factorization not implemented");
657      return CFFList (CFFactor (f, 1));
658      #endif
659    }
660
661    if ( on_rational )
662      On(SW_RATIONAL);
663    if ( ! cd.isOne() )
664    {
665      if ( F.getFirst().factor().inCoeffDomain() )
666      {
667        CFFactor new_first( F.getFirst().factor() / cd );
668        F.removeFirst();
669        F.insert( new_first );
670      }
671      else
672      {
673        F.insert( CFFactor( 1/cd ) );
674      }
675    }
676  }
677
678  //out_cff(F);
679  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
680  return F;
681}
682
683#ifdef HAVE_NTL
684CanonicalForm fntl ( const CanonicalForm & f, int j )
685{
686  ZZX f1=convertFacCF2NTLZZX(f);
687  return convertZZ2CF(coeff(f1,j));
688}
689#endif
690
691CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
692{
693  if ( f.inCoeffDomain() )
694    return CFFList( f );
695  //out_cf("factorize:",f,"==================================\n");
696  //out_cf("mipo:",getMipo(alpha),"\n");
697  CFFList F;
698  ASSERT( alpha.level() < 0, "not an algebraic extension" );
699  int ch=getCharacteristic();
700  if (f.isUnivariate()&& (ch>0))
701  {
702    #ifdef HAVE_NTL
703    if  (isOn(SW_USE_NTL))
704    {
705      //USE NTL
706      if (ch>2)
707      {
708        // First all cases with characteristic !=2
709        // set remainder
710        if (fac_NTL_char != getCharacteristic())
711        {
712          fac_NTL_char = getCharacteristic();
713          #ifdef NTL_ZZ
714          ZZ r;
715          r=getCharacteristic();
716          ZZ_pContext ccc(r);
717          #else
718          zz_pContext ccc(getCharacteristic());
719          #endif
720          ccc.restore();
721          #ifdef NTL_ZZ
722          ZZ_p::init(r);
723          #else
724          zz_p::init(getCharacteristic());
725          #endif
726        }
727
728        // set minimal polynomial in NTL
729        #ifdef NTL_ZZ
730        ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha));
731        ZZ_pEContext c(minPo);
732        #else
733        zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
734        zz_pEContext c(minPo);
735        #endif
736
737        c.restore();
738
739        // convert to NTL
740        #ifdef NTL_ZZ
741        ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo);
742        ZZ_pE leadcoeff= LeadCoeff(f1);
743        #else
744        zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
745        zz_pE leadcoeff= LeadCoeff(f1);
746        #endif
747
748        //make monic
749        f1=f1 / leadcoeff;
750
751        // factorize using NTL
752        #ifdef NTL_ZZ
753        vec_pair_ZZ_pEX_long factors;
754        #else
755        vec_pair_zz_pEX_long factors;
756        #endif
757        CanZass(factors,f1);
758
759        // return converted result
760        #ifdef NTL_ZZ
761        F=convertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
762        #else
763        F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
764        #endif
765      }
766      else if (/*getCharacteristic()*/ch==2)
767      {
768        // special case : GF2
769
770        // remainder is two ==> nothing to do
771        // set remainder
772        ZZ r;
773        r=getCharacteristic();
774        ZZ_pContext ccc(r);
775        ccc.restore();
776
777        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
778        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
779        GF2EContext c(minPo);
780        c.restore();
781
782        // convert to NTL again using the faster conversion routines
783        GF2EX f1;
784        if (isPurePoly(f))
785        {
786          GF2X f_tmp=convertFacCF2NTLGF2X(f);
787          f1=to_GF2EX(f_tmp);
788        }
789        else
790        {
791          f1=convertFacCF2NTLGF2EX(f,minPo);
792        }
793
794        // make monic (in Z/2(a))
795        GF2E f1_coef=LeadCoeff(f1);
796        MakeMonic(f1);
797
798        // factorize using NTL
799        vec_pair_GF2EX_long factors;
800        CanZass(factors,f1);
801
802        // return converted result
803        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
804      }
805      else
806      {
807      }
808    }
809    else
810    #endif
811    {
812      F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
813    }
814  }
815  else if (ch>0)
816  {
817    #ifdef HAVE_NTL
818    F= FqFactorize (f, alpha);
819    #else
820    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
821    factoryError ("multivariate factorization not implemented");
822    return CFFList (CFFactor (f, 1));
823    #endif
824
825  }
826  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
827  {
828    F= AlgExtFactorize (f, alpha);
829  }
830  else //Q(a)[x1,...,xn]
831  {
832#ifdef HAVE_NTL
833    F= ratFactorize (f, alpha);
834#else
835    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
836    factoryError ("multivariate factorization not implemented");
837    return CFFList (CFFactor (f, 1));
838#endif
839  }
840  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
841  return F;
842}
843
844CFFList sqrFree ( const CanonicalForm & f, bool sort )
845{
846//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
847    CFFList result;
848
849    if ( getCharacteristic() == 0 )
850        result = sqrFreeZ( f );
851    else
852    {
853        Variable alpha;
854        if (hasFirstAlgVar (f, alpha))
855          result = FqSqrf( f, alpha );
856        else
857          result= FpSqrf (f);
858    }
859    if (sort)
860    {
861      CFFactor buf= result.getFirst();
862      result.removeFirst();
863      result= sortCFFList (result);
864      result.insert (buf);
865    }
866    return result;
867}
868
869bool isSqrFree ( const CanonicalForm & f )
870{
871//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
872    if ( getCharacteristic() == 0 )
873        return isSqrFreeZ( f );
874    else
875        return isSqrFreeFp( f );
876}
877
Note: See TracBrowser for help on using the repository browser.