source: git/factory/cf_factor.cc @ e71776

spielwiese
Last change on this file since e71776 was e71776, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: better assertions in factorize and deletion of SW_USE_NTL
  • Property mode set to 100644
File size: 19.2 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#ifdef HAVE_CONFIG_H
14#include "config.h"
15#endif /* HAVE_CONFIG_H */
16
17#include "cf_assert.h"
18
19#include "cf_defs.h"
20#include "canonicalform.h"
21#include "cf_iter.h"
22#include "fac_sqrfree.h"
23#include "cf_algorithm.h"
24#include "facFqFactorize.h"
25#include "facFqSquarefree.h"
26#include "cf_map.h"
27#include "algext.h"
28#include "facAlgExt.h"
29#include "facFactorize.h"
30#include "singext.h"
31#include "cf_util.h"
32
33#include "int_int.h"
34#ifdef HAVE_NTL
35#include "NTLconvert.h"
36#endif
37
38#include <factory/cf_gmp.h>
39#ifdef HAVE_FLINT
40#include "FLINTconvert.h"
41#endif
42
43//static bool isUnivariateBaseDomain( const CanonicalForm & f )
44//{
45//    CFIterator i = f;
46//    bool ok = i.coeff().inBaseDomain();
47//    i++;
48//    while ( i.hasTerms() && ( ok = ok && i.coeff().inBaseDomain() ) ) i++;
49//    return ok;
50//}
51
52void find_exp(const CanonicalForm & f, int * exp_f)
53{
54  if ( ! f.inCoeffDomain() )
55  {
56    int e=f.level();
57    CFIterator i = f;
58    if (e>=0)
59    {
60      if (i.exp() > exp_f[e]) exp_f[e]=i.exp();
61    }
62    for (; i.hasTerms(); i++ )
63    {
64      find_exp(i.coeff(), exp_f);
65    }
66  }
67}
68
69int find_mvar(const CanonicalForm & f)
70{
71  int mv=f.level();
72  int *exp_f=new int[mv+1];
73  int i;
74  for(i=mv;i>0;i--) exp_f[i]=0;
75  find_exp(f,exp_f);
76  for(i=mv;i>0;i--)
77  {
78    if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
79    {
80      mv=i;
81    }
82  }
83  delete[] exp_f;
84  return mv;
85}
86
87#if 1
88//#ifndef NOSTREAMIO
89void out_cf(const char *s1,const CanonicalForm &f,const char *s2)
90{
91  printf("%s",s1);
92  if (f.isZero()) printf("+0");
93  //else if (! f.inCoeffDomain() )
94  else if (! f.inBaseDomain() )
95  {
96    int l = f.level();
97    for ( CFIterator i = f; i.hasTerms(); i++ )
98    {
99      int e=i.exp();
100      if (i.coeff().isOne())
101      {
102        printf("+");
103        if (e==0) printf("1");
104        else
105        {
106          printf("v(%d)",l);
107          if (e!=1) printf("^%d",e);
108        }
109      }
110      else
111      {
112        out_cf("+(",i.coeff(),")");
113        if (e!=0)
114        {
115          printf("*v(%d)",l);
116          if (e!=1) printf("^%d",e);
117        }
118      }
119    }
120  }
121  else
122  {
123    if ( f.isImm() )
124    {
125      if (CFFactory::gettype()==GaloisFieldDomain)
126      {
127         long a= imm2int (f.getval());
128         if ( a == gf_q )
129           printf ("+%ld", a);
130         else  if ( a == 0L )
131           printf ("+1");
132         else  if ( a == 1L )
133           printf ("+%c",gf_name);
134         else
135         {
136           printf ("+%c",gf_name);
137           printf ("^%ld",a);
138         }
139      }
140      else
141        printf("+%ld",f.intval());
142    }
143    else
144    {
145    #ifdef NOSTREAMIO
146      if (f.inZ())
147      {
148        mpz_t m;
149        gmp_numerator(f,m);
150        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
151        str = mpz_get_str( str, 10, m );
152        printf("%s",str);
153        delete[] str;
154        mpz_clear(m);
155      }
156      else if (f.inQ())
157      {
158        mpz_t m;
159        gmp_numerator(f,m);
160        char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
161        str = mpz_get_str( str, 10, m );
162        printf("%s/",str);
163        delete[] str;
164        mpz_clear(m);
165        gmp_denominator(f,m);
166        str = new char[mpz_sizeinbase( m, 10 ) + 2];
167        str = mpz_get_str( str, 10, m );
168        printf("%s",str);
169        delete[] str;
170        mpz_clear(m);
171      }
172    #else
173       std::cout << f;
174    #endif
175    }
176    //if (f.inZ()) printf("(Z)");
177    //else if (f.inQ()) printf("(Q)");
178    //else if (f.inFF()) printf("(FF)");
179    //else if (f.inPP()) printf("(PP)");
180    //else if (f.inGF()) printf("(PP)");
181    //else
182    if (f.inExtension()) printf("E(%d)",f.level());
183  }
184  printf("%s",s2);
185}
186void out_cff(CFFList &L)
187{
188  //int n = L.length();
189  CFFListIterator J=L;
190  int j=0;
191  for ( ; J.hasItem(); J++, j++ )
192  {
193    printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
194    printf("%d\n", J.getItem().exp());
195  }
196}
197void test_cff(CFFList &L,const CanonicalForm & f)
198{
199  //int n = L.length();
200  CFFListIterator J=L;
201  CanonicalForm t=1;
202  int j=0;
203  if (!(L.getFirst().factor().inCoeffDomain()))
204    printf("first entry is not const\n");
205  for ( ; J.hasItem(); J++, j++ )
206  {
207    CanonicalForm tt=J.getItem().factor();
208    if (tt.inCoeffDomain() && (j!=0))
209      printf("other entry is const\n");
210    j=J.getItem().exp();
211    while(j>0) { t*=tt; j--; }
212  }
213  if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
214}
215//#endif
216#endif
217
218bool isPurePoly_m(const CanonicalForm & f)
219{
220  if (f.inBaseDomain()) return true;
221  if (f.level()<0) return false;
222  for (CFIterator i=f;i.hasTerms();i++)
223  {
224    if (!isPurePoly_m(i.coeff())) return false;
225  }
226  return true;
227}
228bool isPurePoly(const CanonicalForm & f)
229{
230  if (f.level()<=0) return false;
231  for (CFIterator i=f;i.hasTerms();i++)
232  {
233    if (!(i.coeff().inBaseDomain())) return false;
234  }
235  return true;
236}
237
238
239///////////////////////////////////////////////////////////////
240// get_max_degree_Variable returns Variable with             //
241// highest degree. We assume f is *not* a constant!          //
242///////////////////////////////////////////////////////////////
243Variable
244get_max_degree_Variable(const CanonicalForm & f)
245{
246  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
247  int max=0, maxlevel=0, n=level(f);
248  for ( int i=1; i<=n; i++ )
249  {
250    if (degree(f,Variable(i)) >= max)
251    {
252      max= degree(f,Variable(i)); maxlevel= i;
253    }
254  }
255  return Variable(maxlevel);
256}
257
258///////////////////////////////////////////////////////////////
259// get_Terms: Split the polynomial in the containing terms.  //
260// getTerms: the real work is done here.                     //
261///////////////////////////////////////////////////////////////
262void
263getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result )
264{
265  if ( getNumVars(f) == 0 ) result.append(f*t);
266  else{
267    Variable x(level(f));
268    for ( CFIterator i=f; i.hasTerms(); i++ )
269      getTerms( i.coeff(), t*power(x,i.exp()), result);
270  }
271}
272CFList
273get_Terms( const CanonicalForm & f ){
274  CFList result,dummy,dummy2;
275  CFIterator i;
276  CFListIterator j;
277
278  if ( getNumVars(f) == 0 ) result.append(f);
279  else{
280    Variable _x(level(f));
281    for ( i=f; i.hasTerms(); i++ ){
282      getTerms(i.coeff(), 1, dummy);
283      for ( j=dummy; j.hasItem(); j++ )
284        result.append(j.getItem() * power(_x, i.exp()));
285
286      dummy= dummy2; // have to initalize new
287    }
288  }
289  return result;
290}
291
292
293///////////////////////////////////////////////////////////////
294// homogenize homogenizes f with Variable x                  //
295///////////////////////////////////////////////////////////////
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
377int 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
387CFFList factorize ( const CanonicalForm & f, bool issqrfree )
388{
389  if ( f.inCoeffDomain() )
390        return CFFList( f );
391#ifndef NOASSERT
392  Variable a;
393  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
394          ( const CanonicalForm & f, const Variable & alpha ) instead");
395#endif
396  //out_cf("factorize:",f,"==================================\n");
397  if (! f.isUnivariate() )
398  {
399    if ( singular_homog_flag && f.isHomogeneous())
400    {
401      Variable xn = get_max_degree_Variable(f);
402      int d_xn = degree(f,xn);
403      CFMap n;
404      CanonicalForm F = compress(f(1,xn),n);
405      CFFList Intermediatelist;
406      Intermediatelist = factorize(F);
407      CFFList Homoglist;
408      CFFListIterator j;
409      for ( j=Intermediatelist; j.hasItem(); j++ )
410      {
411        Homoglist.append(
412            CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
413      }
414      CFFList Unhomoglist;
415      CanonicalForm unhomogelem;
416      for ( j=Homoglist; j.hasItem(); j++ )
417      {
418        unhomogelem= homogenize(j.getItem().factor(),xn);
419        Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
420        d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
421      }
422      if ( d_xn != 0 ) // have to append xn^(d_xn)
423        Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
424      if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
425      return Unhomoglist;
426    }
427  }
428  CFFList F;
429  if ( getCharacteristic() > 0 )
430  {
431    if (f.isUnivariate())
432    {
433#ifdef HAVE_NTL
434#ifdef HAVE_FLINT
435      if (degree (f) < 300)
436      {
437        nmod_poly_t f1;
438        convertFacCF2nmod_poly_t (f1, f);
439        nmod_poly_factor_t result;
440        nmod_poly_factor_init (result);
441        mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
442        F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
443        nmod_poly_factor_clear (result);
444        nmod_poly_clear (f1);
445      }
446      else
447#endif
448      {
449        // USE NTL
450        if (getCharacteristic()!=2)
451        {
452          if (fac_NTL_char != getCharacteristic())
453          {
454            fac_NTL_char = getCharacteristic();
455            zz_p::init(getCharacteristic());
456          }
457
458          // convert to NTL
459          zz_pX f1=convertFacCF2NTLzzpX(f);
460          zz_p leadcoeff = LeadCoeff(f1);
461
462          //make monic
463          f1=f1 / LeadCoeff(f1);
464          // factorize
465          vec_pair_zz_pX_long factors;
466          CanZass(factors,f1);
467
468          F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
469          //test_cff(F,f);
470        }
471        else /*getCharacteristic()==2*/
472        {
473          // Specialcase characteristic==2
474          if (fac_NTL_char != 2)
475          {
476            fac_NTL_char = 2;
477            zz_p::init(2);
478          }
479          // convert to NTL using the faster conversion routine for characteristic 2
480          GF2X f1=convertFacCF2NTLGF2X(f);
481          // no make monic necessary in GF2
482          //factorize
483          vec_pair_GF2X_long factors;
484          CanZass(factors,f1);
485
486          // convert back to factory again using the faster conversion routine for vectors over GF2X
487          F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
488        }
489      }
490#else
491      // Use Factory without NTL
492      factoryError ("univariate factorization depends on NTL(missing)");
493      return CFFList (CFFactor (f, 1));
494#endif //HAVE_NTL
495    }
496    else
497    {
498      #ifdef HAVE_NTL
499      if (issqrfree)
500      {
501        CFList factors;
502        Variable alpha;
503        if (CFFactory::gettype() == GaloisFieldDomain)
504          factors= GFSqrfFactorize (f);
505        else if (hasFirstAlgVar (f, alpha))
506          factors= FqSqrfFactorize (f, alpha);
507        else
508          factors= FpSqrfFactorize (f);
509        for (CFListIterator i= factors; i.hasItem(); i++)
510          F.append (CFFactor (i.getItem(), 1));
511      }
512      else
513      {
514        Variable alpha;
515        if (CFFactory::gettype() == GaloisFieldDomain)
516          F= GFFactorize (f);
517        else if (hasFirstAlgVar (f, alpha))
518          F= FqFactorize (f, alpha);
519        else
520          F= FpFactorize (f);
521      }
522      #else
523      ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
524      factoryError ("multivariate factorization depends on NTL(missing)");
525      return CFFList (CFFactor (f, 1));
526      #endif
527    }
528  }
529  else
530  {
531    bool on_rational = isOn(SW_RATIONAL);
532    On(SW_RATIONAL);
533    CanonicalForm cd = bCommonDen( f );
534    CanonicalForm fz = f * cd;
535    Off(SW_RATIONAL);
536    if ( f.isUnivariate() )
537    {
538      #ifdef HAVE_NTL
539      //USE NTL
540      CanonicalForm ic=icontent(fz);
541      fz/=ic;
542      ZZ c;
543      vec_pair_ZZX_long factors;
544      //factorize the converted polynomial
545      factor(c,factors,convertFacCF2NTLZZX(fz));
546
547      //convert the result back to Factory
548      F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
549      if ( ! ic.isOne() )
550      {
551        if ( F.getFirst().factor().inCoeffDomain() )
552        {
553          CFFactor new_first( F.getFirst().factor() * ic );
554          F.removeFirst();
555          F.insert( new_first );
556        }
557        else
558          F.insert( CFFactor( ic ) );
559      }
560      else
561      {
562        if ( !F.getFirst().factor().inCoeffDomain() )
563        {
564          CFFactor new_first( 1 );
565          F.insert( new_first );
566        }
567      }
568      #else
569      factoryError ("univariate factorization over Z depends on NTL(missing)"); 
570      return CFFList (CFFactor (f, 1));
571      #endif
572    }
573    else
574    {
575      #ifdef HAVE_NTL
576      On (SW_RATIONAL);
577      if (issqrfree)
578      {
579        CFList factors;
580        factors= ratSqrfFactorize (fz);
581        for (CFListIterator i= factors; i.hasItem(); i++)
582          F.append (CFFactor (i.getItem(), 1));
583      }
584      else
585        F = ratFactorize (fz);
586      Off (SW_RATIONAL);
587      #else
588      factoryError ("multivariate factorization  depends on NTL(missing)");
589      return CFFList (CFFactor (f, 1));
590      #endif
591    }
592
593    if ( on_rational )
594      On(SW_RATIONAL);
595    if ( ! cd.isOne() )
596    {
597      if ( F.getFirst().factor().inCoeffDomain() )
598      {
599        CFFactor new_first( F.getFirst().factor() / cd );
600        F.removeFirst();
601        F.insert( new_first );
602      }
603      else
604      {
605        F.insert( CFFactor( 1/cd ) );
606      }
607    }
608  }
609
610  //out_cff(F);
611  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
612  return F;
613}
614
615CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
616{
617  if ( f.inCoeffDomain() )
618    return CFFList( f );
619  //out_cf("factorize:",f,"==================================\n");
620  //out_cf("mipo:",getMipo(alpha),"\n");
621
622  CFFList F;
623  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
624#ifndef NOASSERT
625  Variable beta;
626  if (hasFirstAlgVar(f, beta))
627    ASSERT (!hasFirstAlgVar (f, beta == alpha), "f has an algebraic variable that \
628    does not coincide with alpha");
629#endif
630  int ch=getCharacteristic();
631  if (f.isUnivariate()&& (ch>0))
632  {
633#ifdef HAVE_NTL
634    //USE NTL
635    if (ch>2)
636    {
637#if (HAVE_FLINT && __FLINT_VERSION_MINOR >= 4)
638      nmod_poly_t FLINTmipo, leadingCoeff;
639      fq_nmod_ctx_t fq_con;
640
641      nmod_poly_init (FLINTmipo, getCharacteristic());
642      nmod_poly_init (leadingCoeff, getCharacteristic());
643      convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
644
645      fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
646      fq_nmod_poly_t FLINTF;
647      convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
648      fq_nmod_poly_factor_t res;
649      fq_nmod_poly_factor_init (res, fq_con);
650      fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
651      F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
652      F.insert (CFFactor (Lc (f), 1));
653
654      fq_nmod_poly_factor_clear (res, fq_con);
655      fq_nmod_poly_clear (FLINTF, fq_con);
656      nmod_poly_clear (FLINTmipo);
657      nmod_poly_clear (leadingCoeff);
658      fq_nmod_ctx_clear (fq_con);
659#else
660      // First all cases with characteristic !=2
661      // set remainder
662      if (fac_NTL_char != getCharacteristic())
663      {
664        fac_NTL_char = getCharacteristic();
665        zz_p::init(getCharacteristic());
666      }
667
668      // set minimal polynomial in NTL
669      zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
670      zz_pE::init (minPo);
671
672      // convert to NTL
673      zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
674      zz_pE leadcoeff= LeadCoeff(f1);
675
676      //make monic
677      f1=f1 / leadcoeff;
678
679      // factorize using NTL
680      vec_pair_zz_pEX_long factors;
681      CanZass(factors,f1);
682
683      // return converted result
684      F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
685#endif
686    }
687    else if (/*getCharacteristic()*/ch==2)
688    {
689      // special case : GF2
690
691      // remainder is two ==> nothing to do
692
693      // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
694      GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
695      GF2E::init (minPo);
696
697      // convert to NTL again using the faster conversion routines
698      GF2EX f1;
699      if (isPurePoly(f))
700      {
701        GF2X f_tmp=convertFacCF2NTLGF2X(f);
702        f1=to_GF2EX(f_tmp);
703      }
704      else
705        f1=convertFacCF2NTLGF2EX(f,minPo);
706
707      // make monic (in Z/2(a))
708      GF2E f1_coef=LeadCoeff(f1);
709      MakeMonic(f1);
710
711      // factorize using NTL
712      vec_pair_GF2EX_long factors;
713      CanZass(factors,f1);
714
715      // return converted result
716      F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
717    }
718#else
719    factoryError ("univariate factorization  depends on NTL(missing)");
720    return CFFList (CFFactor (f, 1));
721#endif //HAVE_NTL
722  }
723  else if (ch>0)
724  {
725    #ifdef HAVE_NTL
726    F= FqFactorize (f, alpha);
727    #else
728    ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
729    factoryError ("multivariate factorization  depends on NTL(missing)");
730    return CFFList (CFFactor (f, 1));
731    #endif
732
733  }
734  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
735  {
736    F= AlgExtFactorize (f, alpha);
737  }
738  else //Q(a)[x1,...,xn]
739  {
740#ifdef HAVE_NTL
741    F= ratFactorize (f, alpha);
742#else
743    ASSERT( f.isUnivariate(), "multivariate factorization  depends on NTL(missing)" );
744    factoryError ("multivariate factorization  depends on NTL(missing)");
745    return CFFList (CFFactor (f, 1));
746#endif
747  }
748  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
749  return F;
750}
751
752CFFList sqrFree ( const CanonicalForm & f, bool sort )
753{
754//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
755    CFFList result;
756
757    if ( getCharacteristic() == 0 )
758        result = sqrFreeZ( f );
759    else
760    {
761        Variable alpha;
762        if (hasFirstAlgVar (f, alpha))
763          result = FqSqrf( f, alpha );
764        else
765          result= FpSqrf (f);
766    }
767    if (sort)
768    {
769      CFFactor buf= result.getFirst();
770      result.removeFirst();
771      result= sortCFFList (result);
772      result.insert (buf);
773    }
774    return result;
775}
776
Note: See TracBrowser for help on using the repository browser.