source: git/factory/cf_factor.cc @ cac0f8

spielwiese
Last change on this file since cac0f8 was cac0f8, checked in by Hans Schoenemann <hannes@…>, 4 years ago
temp. disable factore over Z via FLINT
  • Property mode set to 100644
File size: 19.5 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2
3/**
4 *
5 * @file cf_factor.cc
6 *
7 * Interface to factorization and square free factorization algorithms.
8 *
9 * Used by: cf_irred.cc
10 *
11 * Header file: cf_algorithm.h
12 *
13**/
14
15
16#include "config.h"
17
18
19#include "cf_assert.h"
20
21#include "cf_defs.h"
22#include "canonicalform.h"
23#include "cf_iter.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 "facAlgExt.h"
30#include "facFactorize.h"
31#include "singext.h"
32#include "cf_util.h"
33
34#include "int_int.h"
35#ifdef HAVE_NTL
36#include "NTLconvert.h"
37#endif
38
39#include "factory/cf_gmp.h"
40#ifdef HAVE_FLINT
41#include "FLINTconvert.h"
42#endif
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_ARRAY(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_ARRAY(exp_f);
85  return mv;
86}
87
88#if 1
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      if (CFFactory::gettype()==GaloisFieldDomain)
127      {
128         long a= imm2int (f.getval());
129         if ( a == gf_q )
130           printf ("+%ld", a);
131         else  if ( a == 0L )
132           printf ("+1");
133         else  if ( a == 1L )
134           printf ("+%c",gf_name);
135         else
136         {
137           printf ("+%c",gf_name);
138           printf ("^%ld",a);
139         }
140      }
141      else
142        printf("+%ld",f.intval());
143    }
144    else
145    {
146    #ifdef NOSTREAMIO
147      if (f.inZ())
148      {
149        mpz_t m;
150        gmp_numerator(f,m);
151        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
152        str = mpz_get_str( str, 10, m );
153        puts(str);
154        delete[] str;
155        mpz_clear(m);
156      }
157      else if (f.inQ())
158      {
159        mpz_t m;
160        gmp_numerator(f,m);
161        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
162        str = mpz_get_str( str, 10, m );
163        puts(str);putchar('/');
164        delete[] str;
165        mpz_clear(m);
166        gmp_denominator(f,m);
167        str = new char[mpz_sizeinbase( m, 10 ) + 2];
168        str = mpz_get_str( str, 10, m );
169        puts(str);
170        delete[] str;
171        mpz_clear(m);
172      }
173    #else
174       std::cout << f;
175    #endif
176    }
177    //if (f.inZ()) printf("(Z)");
178    //else if (f.inQ()) printf("(Q)");
179    //else if (f.inFF()) printf("(FF)");
180    //else if (f.inPP()) printf("(PP)");
181    //else if (f.inGF()) printf("(PP)");
182    //else
183    if (f.inExtension()) printf("E(%d)",f.level());
184  }
185  printf("%s",s2);
186}
187void out_cff(CFFList &L)
188{
189  //int n = L.length();
190  CFFListIterator J=L;
191  int j=0;
192  for ( ; J.hasItem(); J++, j++ )
193  {
194    printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
195    printf("%d\n", J.getItem().exp());
196  }
197}
198void test_cff(CFFList &L,const CanonicalForm & f)
199{
200  //int n = L.length();
201  CFFListIterator J=L;
202  CanonicalForm t=1;
203  int j=0;
204  if (!(L.getFirst().factor().inCoeffDomain()))
205    printf("first entry is not const\n");
206  for ( ; J.hasItem(); J++, j++ )
207  {
208    CanonicalForm tt=J.getItem().factor();
209    if (tt.inCoeffDomain() && (j!=0))
210      printf("other entry is const\n");
211    j=J.getItem().exp();
212    while(j>0) { t*=tt; j--; }
213  }
214  if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
215}
216//#endif
217#endif
218
219bool isPurePoly_m(const CanonicalForm & f)
220{
221  if (f.inBaseDomain()) return true;
222  if (f.level()<0) return false;
223  for (CFIterator i=f;i.hasTerms();i++)
224  {
225    if (!isPurePoly_m(i.coeff())) return false;
226  }
227  return true;
228}
229bool isPurePoly(const CanonicalForm & f)
230{
231  if (f.level()<=0) return false;
232  for (CFIterator i=f;i.hasTerms();i++)
233  {
234    if (!(i.coeff().inBaseDomain())) return false;
235  }
236  return true;
237}
238
239
240/**
241 * get_max_degree_Variable returns Variable with
242 * highest degree. We assume f is *not* a constant!
243**/
244Variable
245get_max_degree_Variable(const CanonicalForm & f)
246{
247  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
248  int max=0, maxlevel=0, n=level(f);
249  for ( int i=1; i<=n; i++ )
250  {
251    if (degree(f,Variable(i)) >= max)
252    {
253      max= degree(f,Variable(i)); maxlevel= i;
254    }
255  }
256  return Variable(maxlevel);
257}
258
259/**
260 * get_Terms: Split the polynomial in the containing terms.
261 * getTerms: the real work is done here.
262**/
263void
264getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result )
265{
266  if ( getNumVars(f) == 0 ) result.append(f*t);
267  else{
268    Variable x(level(f));
269    for ( CFIterator i=f; i.hasTerms(); i++ )
270      getTerms( i.coeff(), t*power(x,i.exp()), result);
271  }
272}
273CFList
274get_Terms( const CanonicalForm & f ){
275  CFList result,dummy,dummy2;
276  CFIterator i;
277  CFListIterator j;
278
279  if ( getNumVars(f) == 0 ) result.append(f);
280  else{
281    Variable _x(level(f));
282    for ( i=f; i.hasTerms(); i++ ){
283      getTerms(i.coeff(), 1, dummy);
284      for ( j=dummy; j.hasItem(); j++ )
285        result.append(j.getItem() * power(_x, i.exp()));
286
287      dummy= dummy2; // have to initalize new
288    }
289  }
290  return result;
291}
292
293
294/**
295 * homogenize homogenizes f with Variable x
296**/
297CanonicalForm
298homogenize( const CanonicalForm & f, const Variable & x)
299{
300#if 0
301  int maxdeg=totaldegree(f), deg;
302  CFIterator i;
303  CanonicalForm elem, result(0);
304
305  for (i=f; i.hasTerms(); i++)
306  {
307    elem= i.coeff()*power(f.mvar(),i.exp());
308    deg = totaldegree(elem);
309    if ( deg < maxdeg )
310      result += elem * power(x,maxdeg-deg);
311    else
312      result+=elem;
313  }
314  return result;
315#else
316  CFList Newlist, Termlist= get_Terms(f);
317  int maxdeg=totaldegree(f), deg;
318  CFListIterator i;
319  CanonicalForm elem, result(0);
320
321  for (i=Termlist; i.hasItem(); i++)
322  {
323    elem= i.getItem();
324    deg = totaldegree(elem);
325    if ( deg < maxdeg )
326      Newlist.append(elem * power(x,maxdeg-deg));
327    else
328      Newlist.append(elem);
329  }
330  for (i=Newlist; i.hasItem(); i++) // rebuild
331    result += i.getItem();
332
333  return result;
334#endif
335}
336
337CanonicalForm
338homogenize( const CanonicalForm & f, const Variable & x, const Variable & v1, const Variable & v2)
339{
340#if 0
341  int maxdeg=totaldegree(f), deg;
342  CFIterator i;
343  CanonicalForm elem, result(0);
344
345  for (i=f; i.hasTerms(); i++)
346  {
347    elem= i.coeff()*power(f.mvar(),i.exp());
348    deg = totaldegree(elem);
349    if ( deg < maxdeg )
350      result += elem * power(x,maxdeg-deg);
351    else
352      result+=elem;
353  }
354  return result;
355#else
356  CFList Newlist, Termlist= get_Terms(f);
357  int maxdeg=totaldegree(f), deg;
358  CFListIterator i;
359  CanonicalForm elem, result(0);
360
361  for (i=Termlist; i.hasItem(); i++)
362  {
363    elem= i.getItem();
364    deg = totaldegree(elem,v1,v2);
365    if ( deg < maxdeg )
366      Newlist.append(elem * power(x,maxdeg-deg));
367    else
368      Newlist.append(elem);
369  }
370  for (i=Newlist; i.hasItem(); i++) // rebuild
371    result += i.getItem();
372
373  return result;
374#endif
375}
376
377VAR int singular_homog_flag=1;
378
379int cmpCF( const CFFactor & f, const CFFactor & g )
380{
381  if (f.exp() > g.exp()) return 1;
382  if (f.exp() < g.exp()) return 0;
383  if (f.factor() > g.factor()) return 1;
384  return 0;
385}
386
387/**
388 * factorization over \f$ F_p \f$ or \f$ Q \f$
389**/
390CFFList factorize ( const CanonicalForm & f, bool issqrfree )
391{
392  if ( f.inCoeffDomain() )
393        return CFFList( f );
394#ifndef NOASSERT
395  Variable a;
396  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
397          ( const CanonicalForm & f, const Variable & alpha ) instead");
398#endif
399  //out_cf("factorize:",f,"==================================\n");
400  if (! f.isUnivariate() )
401  {
402    if ( singular_homog_flag && f.isHomogeneous())
403    {
404      Variable xn = get_max_degree_Variable(f);
405      int d_xn = degree(f,xn);
406      CFMap n;
407      CanonicalForm F = compress(f(1,xn),n);
408      CFFList Intermediatelist;
409      Intermediatelist = factorize(F);
410      CFFList Homoglist;
411      CFFListIterator j;
412      for ( j=Intermediatelist; j.hasItem(); j++ )
413      {
414        Homoglist.append(
415            CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
416      }
417      CFFList Unhomoglist;
418      CanonicalForm unhomogelem;
419      for ( j=Homoglist; j.hasItem(); j++ )
420      {
421        unhomogelem= homogenize(j.getItem().factor(),xn);
422        Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
423        d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
424      }
425      if ( d_xn != 0 ) // have to append xn^(d_xn)
426        Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
427      if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
428      return Unhomoglist;
429    }
430  }
431  CFFList F;
432  if ( getCharacteristic() > 0 )
433  {
434    if (f.isUnivariate())
435    {
436#ifdef HAVE_FLINT
437#ifdef HAVE_NTL
438      if (degree (f) < 300)
439#endif
440      {
441        // use FLINT
442        nmod_poly_t f1;
443        convertFacCF2nmod_poly_t (f1, f);
444        nmod_poly_factor_t result;
445        nmod_poly_factor_init (result);
446        mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
447        F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
448        nmod_poly_factor_clear (result);
449        nmod_poly_clear (f1);
450        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
451        return F;
452      }
453#endif
454#ifdef HAVE_NTL
455      {
456        if (getCharacteristic()==2)
457        {
458          // Specialcase characteristic==2
459          if (fac_NTL_char != 2)
460          {
461            fac_NTL_char = 2;
462            zz_p::init(2);
463          }
464          // convert to NTL using the faster conversion routine for characteristic 2
465          GF2X f1=convertFacCF2NTLGF2X(f);
466          // no make monic necessary in GF2
467          //factorize
468          vec_pair_GF2X_long factors;
469          CanZass(factors,f1);
470
471          // convert back to factory again using the faster conversion routine for vectors over GF2X
472          F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
473          if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
474          return F;
475        }
476      }
477#endif
478#ifdef HAVE_NTL
479      {
480        // USE NTL
481        if (fac_NTL_char != getCharacteristic())
482        {
483          fac_NTL_char = getCharacteristic();
484          zz_p::init(getCharacteristic());
485        }
486
487        // convert to NTL
488        zz_pX f1=convertFacCF2NTLzzpX(f);
489        zz_p leadcoeff = LeadCoeff(f1);
490
491        //make monic
492        f1=f1 / LeadCoeff(f1);
493        // factorize
494        vec_pair_zz_pX_long factors;
495        CanZass(factors,f1);
496
497        F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
498        //test_cff(F,f);
499        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
500        return F;
501      }
502#endif
503#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
504      // Use Factory without NTL
505      factoryError ("univariate factorization depends on FLINT/NTL(missing)");
506      return CFFList (CFFactor (f, 1));
507#endif
508    }
509    else
510    {
511      #if defined(HAVE_NTL) || defined(HAVE_FLINT)
512      if (issqrfree)
513      {
514        CFList factors;
515        Variable alpha;
516        if (CFFactory::gettype() == GaloisFieldDomain)
517          factors= GFSqrfFactorize (f);
518        else
519          factors= FpSqrfFactorize (f);
520        for (CFListIterator i= factors; i.hasItem(); i++)
521          F.append (CFFactor (i.getItem(), 1));
522      }
523      else
524      {
525        Variable alpha;
526        if (CFFactory::gettype() == GaloisFieldDomain)
527          F= GFFactorize (f);
528        else
529          F= FpFactorize (f);
530      }
531      #else
532      ASSERT( f.isUnivariate(), "multivariate factorization depends on FLINT/NTL(missing)" );
533      factoryError ("multivariate factorization depends on FLINT/NTL(missing)");
534      return CFFList (CFFactor (f, 1));
535      #endif
536    }
537  }
538  else // char 0
539  {
540    bool on_rational = isOn(SW_RATIONAL);
541    On(SW_RATIONAL);
542    CanonicalForm cd = bCommonDen( f );
543    CanonicalForm fz = f * cd;
544    Off(SW_RATIONAL);
545    if ( f.isUnivariate() )
546    {
547      CanonicalForm ic=icontent(fz);
548      fz/=ic;
549      #if 0 // #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20504)
550      // use FLINT
551      fmpz_poly_t f1;
552      convertFacCF2Fmpz_poly_t (f1, fz);
553      fmpz_poly_factor_t result;
554      fmpz_poly_factor_init (result);
555      fmpz_poly_factor_zassenhaus(result, f1);
556      F= convertFLINTfmpz_poly_factor2FacCFFList (result, fz.mvar());
557      fmpz_poly_factor_clear (result);
558      fmpz_poly_clear (f1);
559      if ( ! ic.isOne() )
560      {
561        if ( F.getFirst().factor().inCoeffDomain() )
562        {
563          CFFactor new_first( F.getFirst().factor() * ic );
564          F.removeFirst();
565          F.insert( new_first );
566        }
567        else
568          F.insert( CFFactor( ic ) );
569      }
570      goto end_char0;
571      #elif defined HAVE_NTL
572      //USE NTL
573      ZZ c;
574      vec_pair_ZZX_long factors;
575      //factorize the converted polynomial
576      factor(c,factors,convertFacCF2NTLZZX(fz));
577
578      //convert the result back to Factory
579      F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
580      if ( ! ic.isOne() )
581      {
582        if ( F.getFirst().factor().inCoeffDomain() )
583        {
584          CFFactor new_first( F.getFirst().factor() * ic );
585          F.removeFirst();
586          F.insert( new_first );
587        }
588        else
589          F.insert( CFFactor( ic ) );
590      }
591      else
592      {
593        if ( !F.getFirst().factor().inCoeffDomain() )
594        {
595          CFFactor new_first( 1 );
596          F.insert( new_first );
597        }
598      }
599      goto end_char0;
600      #else
601      factoryError ("univariate factorization over Z depends on NTL/FLINT(missing)");
602      return CFFList (CFFactor (f, 1));
603      #endif
604    }
605    else // not univariate,  char 0
606    {
607      On (SW_RATIONAL);
608      if (issqrfree)
609      {
610        CFList factors;
611        #ifdef HAVE_NTL
612        factors= ratSqrfFactorize (fz);
613        for (CFListIterator i= factors; i.hasItem(); i++)
614          F.append (CFFactor (i.getItem(), 1));
615        #else
616        factoryError ("multivariate factorization over Z depends on NTL(missing)");
617        return CFFList (CFFactor (f, 1));
618        #endif
619      }
620      else
621        F = ratFactorize (fz);
622      Off (SW_RATIONAL);
623    }
624
625end_char0:
626    if ( on_rational )
627      On(SW_RATIONAL);
628    if ( ! cd.isOne() )
629    {
630      if ( F.getFirst().factor().inCoeffDomain() )
631      {
632        CFFactor new_first( F.getFirst().factor() / cd );
633        F.removeFirst();
634        F.insert( new_first );
635      }
636      else
637      {
638        F.insert( CFFactor( 1/cd ) );
639      }
640    }
641  }
642
643  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
644  return F;
645}
646
647/**
648 * factorization over \f$ F_p(\alpha) \f$ or \f$ Q(\alpha) \f$
649**/
650CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
651{
652  if ( f.inCoeffDomain() )
653    return CFFList( f );
654  //out_cf("factorize:",f,"==================================\n");
655  //out_cf("mipo:",getMipo(alpha),"\n");
656
657  CFFList F;
658  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
659#ifndef NOASSERT
660  Variable beta;
661  if (hasFirstAlgVar(f, beta))
662    ASSERT (beta == alpha, "f has an algebraic variable that \
663                            does not coincide with alpha");
664#endif
665  int ch=getCharacteristic();
666  if (ch>0)
667  {
668    if (f.isUnivariate())
669    {
670#ifdef HAVE_NTL
671      if (/*getCharacteristic()*/ch==2)
672      {
673        // special case : GF2
674
675        // remainder is two ==> nothing to do
676
677        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
678        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
679        GF2E::init (minPo);
680
681        // convert to NTL again using the faster conversion routines
682        GF2EX f1;
683        if (isPurePoly(f))
684        {
685          GF2X f_tmp=convertFacCF2NTLGF2X(f);
686          f1=to_GF2EX(f_tmp);
687        }
688        else
689          f1=convertFacCF2NTLGF2EX(f,minPo);
690
691        // make monic (in Z/2(a))
692        GF2E f1_coef=LeadCoeff(f1);
693        MakeMonic(f1);
694
695        // factorize using NTL
696        vec_pair_GF2EX_long factors;
697        CanZass(factors,f1);
698
699        // return converted result
700        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
701        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
702        return F;
703      }
704#endif
705#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
706      {
707        // use FLINT
708        nmod_poly_t FLINTmipo, leadingCoeff;
709        fq_nmod_ctx_t fq_con;
710
711        nmod_poly_init (FLINTmipo, getCharacteristic());
712        nmod_poly_init (leadingCoeff, getCharacteristic());
713        convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
714
715        fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
716        fq_nmod_poly_t FLINTF;
717        convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
718        fq_nmod_poly_factor_t res;
719        fq_nmod_poly_factor_init (res, fq_con);
720        fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
721        F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
722        F.insert (CFFactor (Lc (f), 1));
723
724        fq_nmod_poly_factor_clear (res, fq_con);
725        fq_nmod_poly_clear (FLINTF, fq_con);
726        nmod_poly_clear (FLINTmipo);
727        nmod_poly_clear (leadingCoeff);
728        fq_nmod_ctx_clear (fq_con);
729        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
730        return F;
731      }
732#endif
733#ifdef HAVE_NTL
734      {
735        // use NTL
736        if (fac_NTL_char != getCharacteristic())
737        {
738          fac_NTL_char = getCharacteristic();
739          zz_p::init(getCharacteristic());
740        }
741
742        // convert to NTL
743        zz_pX f1=convertFacCF2NTLzzpX(f);
744        zz_p leadcoeff = LeadCoeff(f1);
745
746        //make monic
747        f1=f1 / LeadCoeff(f1);
748        // factorize
749        vec_pair_zz_pX_long factors;
750        CanZass(factors,f1);
751
752        F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
753        //test_cff(F,f);
754        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
755        return F;
756      }
757#endif
758#if !defined(HAVE_NTL) && !defined(HAVEFLINT)
759      factoryError ("univariate factorization  depends on NTL(missing)");
760      return CFFList (CFFactor (f, 1));
761#endif //HAVE_NTL
762    }
763    else
764    {
765      F= FqFactorize (f, alpha);
766    }
767  }
768  else // Q(a)[x]
769  {
770    if (f.isUnivariate())
771    {
772      F= AlgExtFactorize (f, alpha);
773    }
774    else //Q(a)[x1,...,xn]
775    {
776      F= ratFactorize (f, alpha);
777    }
778  }
779  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
780  return F;
781}
782
783/**
784 * squarefree factorization
785**/
786CFFList sqrFree ( const CanonicalForm & f, bool sort )
787{
788//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
789    CFFList result;
790
791    if ( getCharacteristic() == 0 )
792        result = sqrFreeZ( f );
793    else
794    {
795        Variable alpha;
796        if (hasFirstAlgVar (f, alpha))
797          result = FqSqrf( f, alpha );
798        else
799          result= FpSqrf (f);
800    }
801    if (sort)
802    {
803      CFFactor buf= result.getFirst();
804      result.removeFirst();
805      result= sortCFFList (result);
806      result.insert (buf);
807    }
808    return result;
809}
810
Note: See TracBrowser for help on using the repository browser.