source: git/factory/cf_factor.cc @ 0dff6bc

jengelh-datetimespielwiese
Last change on this file since 0dff6bc was 0dff6bc, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: threshold for using FLINT factorization over Z/p
  • 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_NTL
433#ifdef HAVE_FLINT
434      if (degree (f) < 300)
435      {
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      }
445      else
446#endif
447      if (isOn(SW_USE_NTL) && (isPurePoly(f)))
448      {
449        // USE NTL
450        if (getCharacteristic()!=2)
451        {
452          if (fac_NTL_char != getCharacteristic())
453          {
454            fac_NTL_char = getCharacteristic();
455            #ifndef NTL_ZZ
456            if (fac_NTL_char > NTL_SP_BOUND)
457            {
458              ZZ r;
459              r=getCharacteristic();
460              ZZ_pContext ccc(r);
461              ccc.restore();
462              ZZ_p::init(r);
463            }
464            else
465            #endif
466            {
467              #ifdef NTL_ZZ
468              ZZ r;
469              r=getCharacteristic();
470              ZZ_pContext ccc(r);
471              #else
472              zz_pContext ccc(getCharacteristic());
473              #endif
474              ccc.restore();
475              #ifdef NTL_ZZ
476              ZZ_p::init(r);
477              #else
478              zz_p::init(getCharacteristic());
479              #endif
480            }
481          }
482          #ifndef NTL_ZZ
483          if (fac_NTL_char > NTL_SP_BOUND)
484          {
485            // convert to NTL
486            ZZ_pX f1=convertFacCF2NTLZZpX(f);
487            ZZ_p leadcoeff = LeadCoeff(f1);
488            //make monic
489            f1=f1 / LeadCoeff(f1);
490            // factorize
491            vec_pair_ZZ_pX_long factors;
492            CanZass(factors,f1);
493            // convert back to factory
494            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
495          }
496          else
497          #endif
498          {
499            // convert to NTL
500            #ifdef NTL_ZZ
501            ZZ_pX f1=convertFacCF2NTLZZpX(f);
502            ZZ_p leadcoeff = LeadCoeff(f1);
503            #else
504            zz_pX f1=convertFacCF2NTLzzpX(f);
505            zz_p leadcoeff = LeadCoeff(f1);
506            #endif
507            //make monic
508            f1=f1 / LeadCoeff(f1);
509            // factorize
510            #ifdef NTL_ZZ
511            vec_pair_ZZ_pX_long factors;
512            #else
513            vec_pair_zz_pX_long factors;
514            #endif
515            CanZass(factors,f1);
516            // convert back to factory
517            #ifdef NTL_ZZ
518            F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar());
519            #else
520            F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
521            #endif
522          }
523          //test_cff(F,f);
524        }
525        else /*getCharacteristic()==2*/
526        {
527          // Specialcase characteristic==2
528          if (fac_NTL_char != 2)
529          {
530            fac_NTL_char = 2;
531            zz_p::init(2);
532          }
533          // convert to NTL using the faster conversion routine for characteristic 2
534          GF2X f1=convertFacCF2NTLGF2X(f);
535          // no make monic necessary in GF2
536          //factorize
537          vec_pair_GF2X_long factors;
538          CanZass(factors,f1);
539
540          // convert back to factory again using the faster conversion routine for vectors over GF2X
541          F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
542        }
543      }
544      else
545#endif //HAVE_NTL
546      {  // Use Factory without NTL
547        if ( isOn( SW_BERLEKAMP ) )
548          F=FpFactorizeUnivariateB( f, issqrfree );
549        else
550          F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
551      }
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  //out_cff(F);
682  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
683  return F;
684}
685
686#ifdef HAVE_NTL
687CanonicalForm fntl ( const CanonicalForm & f, int j )
688{
689  ZZX f1=convertFacCF2NTLZZX(f);
690  return convertZZ2CF(coeff(f1,j));
691}
692#endif
693
694CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
695{
696  if ( f.inCoeffDomain() )
697    return CFFList( f );
698  //out_cf("factorize:",f,"==================================\n");
699  //out_cf("mipo:",getMipo(alpha),"\n");
700  CFFList F;
701  ASSERT( alpha.level() < 0, "not an algebraic extension" );
702  int ch=getCharacteristic();
703  if (f.isUnivariate()&& (ch>0))
704  {
705    #ifdef HAVE_NTL
706    if  (isOn(SW_USE_NTL))
707    {
708      //USE NTL
709      if (ch>2)
710      {
711        // First all cases with characteristic !=2
712        // set remainder
713        if (fac_NTL_char != getCharacteristic())
714        {
715          fac_NTL_char = getCharacteristic();
716          #ifdef NTL_ZZ
717          ZZ r;
718          r=getCharacteristic();
719          ZZ_pContext ccc(r);
720          #else
721          zz_pContext ccc(getCharacteristic());
722          #endif
723          ccc.restore();
724          #ifdef NTL_ZZ
725          ZZ_p::init(r);
726          #else
727          zz_p::init(getCharacteristic());
728          #endif
729        }
730
731        // set minimal polynomial in NTL
732        #ifdef NTL_ZZ
733        ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha));
734        ZZ_pEContext c(minPo);
735        #else
736        zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
737        zz_pEContext c(minPo);
738        #endif
739
740        c.restore();
741
742        // convert to NTL
743        #ifdef NTL_ZZ
744        ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo);
745        ZZ_pE leadcoeff= LeadCoeff(f1);
746        #else
747        zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
748        zz_pE leadcoeff= LeadCoeff(f1);
749        #endif
750
751        //make monic
752        f1=f1 / leadcoeff;
753
754        // factorize using NTL
755        #ifdef NTL_ZZ
756        vec_pair_ZZ_pEX_long factors;
757        #else
758        vec_pair_zz_pEX_long factors;
759        #endif
760        CanZass(factors,f1);
761
762        // return converted result
763        #ifdef NTL_ZZ
764        F=convertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
765        #else
766        F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
767        #endif
768      }
769      else if (/*getCharacteristic()*/ch==2)
770      {
771        // special case : GF2
772
773        // remainder is two ==> nothing to do
774        // set remainder
775        ZZ r;
776        r=getCharacteristic();
777        ZZ_pContext ccc(r);
778        ccc.restore();
779
780        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
781        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
782        GF2EContext c(minPo);
783        c.restore();
784
785        // convert to NTL again using the faster conversion routines
786        GF2EX f1;
787        if (isPurePoly(f))
788        {
789          GF2X f_tmp=convertFacCF2NTLGF2X(f);
790          f1=to_GF2EX(f_tmp);
791        }
792        else
793        {
794          f1=convertFacCF2NTLGF2EX(f,minPo);
795        }
796
797        // make monic (in Z/2(a))
798        GF2E f1_coef=LeadCoeff(f1);
799        MakeMonic(f1);
800
801        // factorize using NTL
802        vec_pair_GF2EX_long factors;
803        CanZass(factors,f1);
804
805        // return converted result
806        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
807      }
808      else
809      {
810      }
811    }
812    else
813    #endif
814    {
815      F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );
816    }
817  }
818  else if (ch>0)
819  {
820    #ifdef HAVE_NTL
821    F= FqFactorize (f, alpha);
822    #else
823    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
824    factoryError ("multivariate factorization not implemented");
825    return CFFList (CFFactor (f, 1));
826    #endif
827
828  }
829  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
830  {
831    F= AlgExtFactorize (f, alpha);
832  }
833  else //Q(a)[x1,...,xn]
834  {
835#ifdef HAVE_NTL
836    F= ratFactorize (f, alpha);
837#else
838    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
839    factoryError ("multivariate factorization not implemented");
840    return CFFList (CFFactor (f, 1));
841#endif
842  }
843  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
844  return F;
845}
846
847CFFList sqrFree ( const CanonicalForm & f, bool sort )
848{
849//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
850    CFFList result;
851
852    if ( getCharacteristic() == 0 )
853        result = sqrFreeZ( f );
854    else
855    {
856        Variable alpha;
857        if (hasFirstAlgVar (f, alpha))
858          result = FqSqrf( f, alpha );
859        else
860          result= FpSqrf (f);
861    }
862    if (sort)
863    {
864      CFFactor buf= result.getFirst();
865      result.removeFirst();
866      result= sortCFFList (result);
867      result.insert (buf);
868    }
869    return result;
870}
871
872bool isSqrFree ( const CanonicalForm & f )
873{
874//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
875    if ( getCharacteristic() == 0 )
876        return isSqrFreeZ( f );
877    else
878        return isSqrFreeFp( f );
879}
880
Note: See TracBrowser for help on using the repository browser.