source: git/factory/cf_factor.cc @ 6e12a45

spielwiese
Last change on this file since 6e12a45 was 6e12a45, checked in by Hans Schoenemann <hannes@…>, 4 years ago
univariate factorization over Z via FLINT
  • Property mode set to 100644
File size: 19.4 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      #ifdef HAVE_NTL
548      //USE NTL
549      CanonicalForm ic=icontent(fz);
550      fz/=ic;
551      ZZ c;
552      vec_pair_ZZX_long factors;
553      //factorize the converted polynomial
554      factor(c,factors,convertFacCF2NTLZZX(fz));
555
556      //convert the result back to Factory
557      F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
558      if ( ! ic.isOne() )
559      {
560        if ( F.getFirst().factor().inCoeffDomain() )
561        {
562          CFFactor new_first( F.getFirst().factor() * ic );
563          F.removeFirst();
564          F.insert( new_first );
565        }
566        else
567          F.insert( CFFactor( ic ) );
568      }
569      else
570      {
571        if ( !F.getFirst().factor().inCoeffDomain() )
572        {
573          CFFactor new_first( 1 );
574          F.insert( new_first );
575        }
576      }
577      if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
578      return F;
579      #endif
580      #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20504)
581      // use FLINT
582      fmpz_poly_t f1;
583      convertFacCF2Fmpz_poly_t (f1, f);
584      fmpz_poly_factor_t result;
585      fmpz_poly_factor_init (result);
586      fmpz_poly_factor_zassenhaus(result, f1);
587      F= convertFLINTfmpz_poly_factor2FacCFFList (result, f.mvar());
588      fmpz_poly_factor_clear (result);
589      fmpz_poly_clear (f1);
590      if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
591      return F;
592      #endif
593      #if !defined(AHE_NTL) && !defined(HAVE_FLINT)
594      factoryError ("univariate factorization over Z depends on NTL/FLINT(missing)");
595      return CFFList (CFFactor (f, 1));
596      #endif
597    }
598    else // not univariate,  char 0
599    {
600      On (SW_RATIONAL);
601      if (issqrfree)
602      {
603        CFList factors;
604        #ifdef HAVE_NTL
605        factors= ratSqrfFactorize (fz);
606        for (CFListIterator i= factors; i.hasItem(); i++)
607          F.append (CFFactor (i.getItem(), 1));
608        #else
609        factoryError ("multivariate factorization over Z depends on NTL(missing)");
610        return CFFList (CFFactor (f, 1));
611        #endif
612      }
613      else
614        F = ratFactorize (fz);
615      Off (SW_RATIONAL);
616    }
617
618    if ( on_rational )
619      On(SW_RATIONAL);
620    if ( ! cd.isOne() )
621    {
622      if ( F.getFirst().factor().inCoeffDomain() )
623      {
624        CFFactor new_first( F.getFirst().factor() / cd );
625        F.removeFirst();
626        F.insert( new_first );
627      }
628      else
629      {
630        F.insert( CFFactor( 1/cd ) );
631      }
632    }
633  }
634
635  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
636  return F;
637}
638
639/**
640 * factorization over \f$ F_p(\alpha) \f$ or \f$ Q(\alpha) \f$
641**/
642CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
643{
644  if ( f.inCoeffDomain() )
645    return CFFList( f );
646  //out_cf("factorize:",f,"==================================\n");
647  //out_cf("mipo:",getMipo(alpha),"\n");
648
649  CFFList F;
650  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
651#ifndef NOASSERT
652  Variable beta;
653  if (hasFirstAlgVar(f, beta))
654    ASSERT (beta == alpha, "f has an algebraic variable that \
655                            does not coincide with alpha");
656#endif
657  int ch=getCharacteristic();
658  if (ch>0)
659  {
660    if (f.isUnivariate())
661    {
662#ifdef HAVE_NTL
663      if (/*getCharacteristic()*/ch==2)
664      {
665        // special case : GF2
666
667        // remainder is two ==> nothing to do
668
669        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
670        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
671        GF2E::init (minPo);
672
673        // convert to NTL again using the faster conversion routines
674        GF2EX f1;
675        if (isPurePoly(f))
676        {
677          GF2X f_tmp=convertFacCF2NTLGF2X(f);
678          f1=to_GF2EX(f_tmp);
679        }
680        else
681          f1=convertFacCF2NTLGF2EX(f,minPo);
682
683        // make monic (in Z/2(a))
684        GF2E f1_coef=LeadCoeff(f1);
685        MakeMonic(f1);
686
687        // factorize using NTL
688        vec_pair_GF2EX_long factors;
689        CanZass(factors,f1);
690
691        // return converted result
692        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
693        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
694        return F;
695      }
696#endif
697#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
698      {
699        // use FLINT
700        nmod_poly_t FLINTmipo, leadingCoeff;
701        fq_nmod_ctx_t fq_con;
702
703        nmod_poly_init (FLINTmipo, getCharacteristic());
704        nmod_poly_init (leadingCoeff, getCharacteristic());
705        convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
706
707        fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
708        fq_nmod_poly_t FLINTF;
709        convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
710        fq_nmod_poly_factor_t res;
711        fq_nmod_poly_factor_init (res, fq_con);
712        fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
713        F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
714        F.insert (CFFactor (Lc (f), 1));
715
716        fq_nmod_poly_factor_clear (res, fq_con);
717        fq_nmod_poly_clear (FLINTF, fq_con);
718        nmod_poly_clear (FLINTmipo);
719        nmod_poly_clear (leadingCoeff);
720        fq_nmod_ctx_clear (fq_con);
721        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
722        return F;
723      }
724#endif
725#ifdef HAVE_NTL
726      {
727        // use NTL
728        if (fac_NTL_char != getCharacteristic())
729        {
730          fac_NTL_char = getCharacteristic();
731          zz_p::init(getCharacteristic());
732        }
733
734        // convert to NTL
735        zz_pX f1=convertFacCF2NTLzzpX(f);
736        zz_p leadcoeff = LeadCoeff(f1);
737
738        //make monic
739        f1=f1 / LeadCoeff(f1);
740        // factorize
741        vec_pair_zz_pX_long factors;
742        CanZass(factors,f1);
743
744        F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
745        //test_cff(F,f);
746        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
747        return F;
748      }
749#endif
750#if !defined(HAVE_NTL) && !defined(HAVEFLINT)
751      factoryError ("univariate factorization  depends on NTL(missing)");
752      return CFFList (CFFactor (f, 1));
753#endif //HAVE_NTL
754    }
755    else
756    {
757      F= FqFactorize (f, alpha);
758    }
759  }
760  else // Q(a)[x]
761  {
762    if (f.isUnivariate())
763    {
764      F= AlgExtFactorize (f, alpha);
765    }
766    else //Q(a)[x1,...,xn]
767    {
768      F= ratFactorize (f, alpha);
769    }
770  }
771  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
772  return F;
773}
774
775/**
776 * squarefree factorization
777**/
778CFFList sqrFree ( const CanonicalForm & f, bool sort )
779{
780//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
781    CFFList result;
782
783    if ( getCharacteristic() == 0 )
784        result = sqrFreeZ( f );
785    else
786    {
787        Variable alpha;
788        if (hasFirstAlgVar (f, alpha))
789          result = FqSqrf( f, alpha );
790        else
791          result= FpSqrf (f);
792    }
793    if (sort)
794    {
795      CFFactor buf= result.getFirst();
796      result.removeFirst();
797      result= sortCFFList (result);
798      result.insert (buf);
799    }
800    return result;
801}
802
Note: See TracBrowser for help on using the repository browser.