source: git/factory/cf_factor.cc @ ec16f0

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