source: git/libfac/factor/Factor.cc @ d77a70

spielwiese
Last change on this file since d77a70 was d77a70, checked in by Hans Schoenemann <hannes@…>, 13 years ago
experimenatl stuff removed git-svn-id: file:///usr/local/Singular/svn/trunk@13653 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 41.7 KB
Line 
1///////////////////////////////////////////////////////////////////////////////
2/* $Id$ */
3static const char * errmsg = "\nYou found a bug!\nPlease inform singular@mathematik.uni-kl.de\nPlease include above information and your input (the ideal/polynomial and characteristic) in your bug-report.\nThank you.";
4///////////////////////////////////////////////////////////////////////////////
5// FACTORY - Includes
6#include <factory.h>
7#ifndef NOSTREAMIO
8#ifdef HAVE_IOSTREAM
9#include <iostream>
10#define CERR std::cerr
11#define CIN std::cin
12#elif defined(HAVE_IOSTREAM_H)
13#include <iostream.h>
14#define CERR cerr
15#define CIN cin
16#endif
17#endif
18// Factor - Includes
19#include "tmpl_inst.h"
20#include "SqrFree.h"
21#include "helpstuff.h"
22#include "MVMultiHensel.h"
23#include "Truefactor.h"
24#include "homogfactor.h"
25#include "interrupt.h"
26// some CC's need this:
27#include "Factor.h"
28
29#include "alg_factor.h"
30void out_cf(char *s1,const CanonicalForm &f,char *s2);
31void out_cff(CFFList &L);
32
33
34#ifdef FACTORDEBUG
35#  define DEBUGOUTPUT
36#else
37#  undef DEBUGOUTPUT
38#endif
39
40#include "debug.h"
41#include "timing.h"
42TIMING_DEFINE_PRINT(factorize_time);
43TIMING_DEFINE_PRINT(sqrfree_time);
44TIMING_DEFINE_PRINT(discr_time);
45TIMING_DEFINE_PRINT(evaluate_time);
46TIMING_DEFINE_PRINT(hensel_time);
47TIMING_DEFINE_PRINT(truefactor_time);
48
49/*
50* a wrapper for factorize over algebraic extensions:
51* does a sanity check and, if nec., a conversion
52* before calling factorize(f,alpha)
53* ( in factorize, alpha.level() must be < 0 )
54*/
55CFFList factorize2 ( const CanonicalForm & f,
56                     const Variable & alpha, const CanonicalForm & mipo )
57{
58  if (alpha.level() <0)
59  {
60    if (f.isUnivariate())
61      return factorize(f,alpha);
62    else
63    {
64      return Factorize(f,mipo);
65    }
66  }
67  else
68  {
69    bool repl=(f.mvar() != alpha);
70    //out_cf("f2 - factor:",f,"\n");
71    //out_cf("f2 - ext:",alpha,"\n");
72    //out_cf("f2 - mipo:",mipo,"\n");
73    Variable X=rootOf(mipo);
74    CanonicalForm F=f;
75    if (repl) F=replacevar(f,alpha,X);
76    //out_cf("call - factor:",F,"\n");
77    //out_cf("call - ext:",X,"\n");
78    //out_cf("call - mipo:",getMipo(X,'A'),"\n");
79    CFFList L=factorize(F,X);
80    CFFListIterator i=L;
81    if (repl)
82    {
83      CFFList Outputlist;
84      for(;i.hasItem(); i++ )
85      {
86        Outputlist.append(CFFactor(
87        replacevar(i.getItem().factor(),X,alpha),
88        i.getItem().exp()));
89      }
90      return Outputlist;
91    }
92    else return L;
93  }
94}
95///////////////////////////////////////////////////////////////
96// Choose a main variable if the user didn`t wish a          //
97// special one. Returns level of main variable.              //
98///////////////////////////////////////////////////////////////
99static int
100choose_main_variable( const CanonicalForm & f, int Mainvar=0){
101  CanonicalForm remlc, newlc;
102  int n= level(f), mainvar= Mainvar;
103
104  if (mainvar != 0) return mainvar ; // We force use of the wished mainvar
105  remlc= LC(f,n); mainvar = n;
106  if ( totaldegree(remlc)==0 ){ remlc=f.genOne() ; }
107  DEBOUTLN(CERR, "remlc= " , remlc);
108  for ( int i=n-1; i>=1; i-- )
109  {
110    newlc= LC(f,i);
111    if ( totaldegree(newlc)==0 ){ newlc=f.genOne() ; }
112    DEBOUTLN(CERR, "newlc= " , newlc);
113    if ( (remlc.isOne()) && (newlc.isOne()) ){ // take care of the degrees
114      if ( degree(f,i) < degree(f,mainvar) ){
115        remlc= newlc;
116        mainvar= i;
117      }
118    }
119    else  if ( (! remlc.isOne() ) && ( newlc.isOne() ) ){
120      remlc= newlc;
121      mainvar= i;
122    }
123  }
124  return mainvar;
125}
126
127///////////////////////////////////////////////////////////////
128// Check if the derivative is nonzero for oldmainvar.        //
129// Returns the level of the choosen main variable.           //
130///////////////////////////////////////////////////////////////
131static int
132necessary_condition( const CanonicalForm & F, int oldmainvar){
133  CanonicalForm g;
134  int n=level(F);
135
136  g= swapvar(F,oldmainvar,n);
137  g= g.deriv();
138  if ( g.isZero() )
139  {
140    for ( int i=n; i>=1; i-- )
141    {
142      g= swapvar(F,i,n);
143      g= g.deriv();
144      if ( ! g.isZero() ) return i;
145    }
146  }
147  return oldmainvar;
148}
149
150///////////////////////////////////////////////////////////////
151// Make F monic. Return monic polynomial.                    //
152///////////////////////////////////////////////////////////////
153static CanonicalForm
154make_monic( const CanonicalForm & F, const CanonicalForm & lt)
155{
156  CanonicalForm intermediatpoly,f;
157  Variable x(level(F));
158
159  if ( degree(lt) == 0 ) f= 1/lt * F ;
160  else
161  {
162    intermediatpoly= power(lt,degree(F)-1);
163    for ( int i=0; i<=degree(F); i++ )
164      if ( ! F[i].isZero())
165        f+= (F[i] * intermediatpoly*power(x,i))/power(lt,i);
166  }
167  return f;
168}
169
170///////////////////////////////////////////////////////////////
171// Decide whether num/denum (num,denum both from the         //
172// FiniteFielddomain)  lies in the RationalDomain.           //
173// If false, return num/denum else return the zero poly from //
174// the FiniteFielddomain.                                    //
175///////////////////////////////////////////////////////////////
176static CanonicalForm
177is_rational( const CanonicalForm & num, const CanonicalForm & denum ){
178  CanonicalForm a, b;
179  int retvalue;
180
181  retvalue= mydivremt(num,denum,a,b);
182  if ( retvalue && b == num.genZero() ) // num/denum from FFdomain
183    return a;
184  else // num/denum is rational
185    return num.genZero();
186}
187
188///////////////////////////////////////////////////////////////
189// lt_is_product returns 1 iff lt is a product, 0 iff lt is  //
190// a sum.                                                    //
191///////////////////////////////////////////////////////////////
192static int
193lt_is_product( const CanonicalForm & lt ){
194  CFList result;
195
196  result= get_Terms(lt);
197  if ( result.length() > 1 ) return 0;
198  else return 1;
199}
200
201///////////////////////////////////////////////////////////////
202// Reverse the make_monic transformation.                    //
203// Return the list of factors.                               //
204///////////////////////////////////////////////////////////////
205static CFFList
206not_monic( const CFFList & TheList, const CanonicalForm & ltt, const CanonicalForm & F, int levelF)
207{
208  CFFList Returnlist,IntermediateList;
209  CFFListIterator i;
210  CanonicalForm intermediate,lt= ltt,savelc;
211  CanonicalForm numerator,denumerator,test,a,b;
212  Variable x(level(F));
213  int test1;
214
215  if ( lt.isOne() ) return TheList; // the poly was already monic
216  if ( TheList.length() <= 1 ) // only one factor to substitute back
217  {
218    if ( totaldegree(lt) == 0 ) // lt is type numeric
219      Returnlist.append( CFFactor(lt*TheList.getFirst().factor(),
220                                  TheList.getFirst().exp()) );
221    else
222    {
223      intermediate = F(x*lt, levelF)/power(lt,degree(F,levelF)-1);
224      Returnlist.append(CFFactor(intermediate,TheList.getFirst().exp()));
225    }
226  }
227  else // more then one factor
228  {
229    IntermediateList= TheList;
230    if ( totaldegree(lt) == 0 ){ // lt is type numeric;(SqrFree-use, see above)
231      Returnlist.append( CFFactor(lt*IntermediateList.getFirst().factor()
232                                  , IntermediateList.getFirst().exp()) );
233      IntermediateList.removeFirst();
234      Returnlist= Union(Returnlist,IntermediateList);
235    }
236    else // lt is a) a product or b) a sum of terms
237    {
238      if ( lt_is_product(lt) ) // case a)
239      {
240        DEBOUTLN(CERR, "lt_is_product: ", lt);
241        savelc= content(lt) ; // can we simplify to savelc= lc(lt); ?
242        while ( getNumVars(savelc) != 0 )
243          savelc= content(savelc);
244        for ( i=TheList; i.hasItem();i++ )
245        {
246          numerator= i.getItem().factor();
247          numerator= numerator(x*lt,levelF); // x <- x*lt
248          denumerator= power(lt,degree(F,levelF)-1); // == lt^(1-degree(F,x)
249          while (numerator.genZero() == is_rational(numerator, denumerator))
250            numerator*= lt;
251          intermediate= is_rational(numerator,denumerator);
252
253          Returnlist.append( CFFactor(lc(content(intermediate))*intermediate/content(intermediate), i.getItem().exp() ) );
254        }
255        // Now we add a test. If product(factors)/F is a multiple of
256        // savelc, we have to add 1/multiplicity to the factors
257        IntermediateList= Returnlist;
258        intermediate= 1;
259        for ( CFFListIterator j=IntermediateList; j.hasItem(); j++)
260          intermediate*= j.getItem().factor();
261        test1= mydivremt( intermediate,F,a,b);
262        if ( test1 && b == intermediate.genZero() ) // Yupp!
263        {
264          IntermediateList.append(CFFactor(1/a,1));
265          Returnlist= IntermediateList;
266        }
267        else { Returnlist= IntermediateList; }
268      }
269      else // case b)
270      {
271        DEBOUTLN(CERR, "lt_is_sum: ", lt);
272        CanonicalForm save_denumerator= 1;
273        for ( i=TheList; i.hasItem(); i++ )
274        {
275          numerator= i.getItem().factor();
276          numerator= numerator(x*lt,levelF); // x <- x*lt
277          denumerator= power(lt,degree(numerator,levelF)); // == lt^(-degree(numerator,x)
278          test= content(numerator,x);
279          test1= mydivremt(denumerator,test,a,b);
280          if ( test1 && b == numerator.genZero() ) // Yupp!
281          {
282            save_denumerator*= a;
283            Returnlist.append(CFFactor(numerator/test ,1));
284          }
285          else
286          {
287            factoryError("libfac: ERROR: not_monic1: case lt is a sum.");
288          }
289        }
290        // Now we add a test if we did the right thing:
291        // save_denumerator should be a multiple of the leading coeff
292        test1= mydivremt(save_denumerator,lt,a,b);
293        if ( test1 && b == save_denumerator.genZero() ) // Yupp!
294          // We have to multiply one of the factors with
295          // the multiplicity of the save_denumerator <-> lc
296          // the following will do what we want
297          Returnlist= myUnion( CFFList(CFFactor(1/a,1)),Returnlist) ;
298        else
299        {
300          factoryError("libfac: ERROR: not_monic2: case lt is a sum.");
301        }
302      }
303    }
304  }
305  DEBOUTLN(CERR,"Returnlist: ", Returnlist);
306  return Returnlist;
307}
308
309///////////////////////////////////////////////////////////////
310// Substitute the (Variable,Value)-Pair(s) from Substitution-//
311// list into the polynomial F. Returns the resulting poly.   //
312///////////////////////////////////////////////////////////////
313static CanonicalForm
314substitutePoly( const CanonicalForm & F, const SFormList & Substitutionlist){
315  CanonicalForm f= F;
316
317  for ( SFormListIterator i=Substitutionlist; i.hasItem(); i++ )
318    f= f(i.getItem().exp(),level(i.getItem().factor()));
319  return f;
320}
321
322///////////////////////////////////////////////////////////////
323// Find specialization values for the poly F. Returns 0 if   //
324// procedure failed, 1 otherwise. On success Substitutionlist//
325// holds (Variable,Value)-pairs. On failure we only have a   //
326// partitial list.                                           //
327///////////////////////////////////////////////////////////////
328//      *** This is the version with extensions ***          //
329///////////////////////////////////////////////////////////////
330
331///////////////////////////////////////////////////////////////
332// is CF g ok?                                               //
333///////////////////////////////////////////////////////////////
334static int
335various_tests( const CanonicalForm & g, int deg, int vars_left)
336{
337  CFMap m;
338
339  if ( degree(g) == deg ) // degrees match
340    if ( level(compress(g,m)) == (vars_left) ) // exactly one variable less
341      if ( SqrFreeTest(g,1) ) // poly is sqrfree
342        if ( gcd(g,g.deriv()).isOne() ) // Discriminante != 0
343           return 1;
344  return 0;
345}
346
347///////////////////////////////////////////////////////////////
348// specialize one variable over the given field.             //
349///////////////////////////////////////////////////////////////
350// substitutes in poly f of degree deg with former
351// former_nr_of_variables variables the variable nr_of_variable ;
352// this is done in the field of Char getCharacteristic() and
353// Extension given by Extgenerator.
354///////////////////////////////////////////////////////////////
355static int
356specialize_variable( CanonicalForm & f, int deg, SFormList & Substitutionlist, int nr_of_variable,
357                     int former_nr_of_variables, CFGenerator & Extgenerator ){
358  CanonicalForm g;
359  Variable x(nr_of_variable);
360
361  DEBOUTLN(CERR, "specialize_variable: called with: ", f);
362  for ( Extgenerator.reset(); Extgenerator.hasItems(); Extgenerator.next() ){
363    DEBOUTLN(CERR, "  specialize_variable: trying:  ", Extgenerator.item());
364    g= f( Extgenerator.item(), x );
365    DEBOUTLN(CERR, "  specialize_variable: resulting g= ", g);
366    if ( various_tests(g,deg,former_nr_of_variables - nr_of_variable ) ){
367      Substitutionlist.insert(SForm(x,Extgenerator.item())); // append (Var,value) pair
368      f= g;
369      return 1;
370    }
371  }
372  return 0;
373}
374static int
375specialize_agvariable( CanonicalForm & f, int deg, SFormList & Substitutionlist, int nr_of_variable,
376                     int former_nr_of_variables, AlgExtGenerator & Extgenerator ){
377  CanonicalForm g;
378  Variable x(nr_of_variable);
379
380  DEBOUTLN(CERR, "specialize_variable: called with: ", f);
381  for ( Extgenerator.reset(); Extgenerator.hasItems(); Extgenerator.next() ){
382    DEBOUTLN(CERR, "  specialize_variable: trying:  ", Extgenerator.item());
383    g= f( Extgenerator.item(), x );
384    DEBOUTLN(CERR, "  specialize_variable: resulting g= ", g);
385    if ( various_tests(g,deg,former_nr_of_variables - nr_of_variable ) ){
386      Substitutionlist.insert(SForm(x,Extgenerator.item())); // append (Var,value) pair
387      f= g;
388      return 1;
389    }
390  }
391  return 0;
392}
393
394///////////////////////////////////////////////////////////////
395// generate a minpoly of degree degree_of_Extension in the   //
396// field getCharacteristik()^Extension.                      //
397///////////////////////////////////////////////////////////////
398CanonicalForm
399generate_mipo( int degree_of_Extension , const Variable & Extension ){
400  FFRandom gen;
401  if ( degree(Extension) > 0 ) GFRandom gen;
402  else {
403    if ( degree(Extension) == 0 ) FFRandom gen;
404    else
405    {
406      factoryError("libfac: evaluate: Extension not inFF() or inGF() !");
407    }
408  }
409  return find_irreducible( degree_of_Extension, gen, Variable(1) );
410}
411
412///////////////////////////////////////////////////////////////
413// Try to find a specialization for f over the field of char //
414// f.getCharacteristic() and (possible) extension defined by //
415// the variable Extension .                                  //
416// Returns 1 iff specialisation was found, 0 otherwise.      //
417// If 0 is returned there are variables left to substitute.  //
418// We check if Substitutionlist.length() > 0, i.e. we        //
419// previously tried to find specialization values for some   //
420// values. We take them and work with the resulting poly.    //
421///////////////////////////////////////////////////////////////
422static int
423try_specializePoly(const CanonicalForm & f, const Variable & Extension, int deg, SFormList & Substitutionlist, int ii,int j)
424{
425  int ok,i= ii;
426  CanonicalForm ff= f;
427
428  if ( Substitutionlist.length() > 0 ){ // we formerly tried to specialize
429    ff= substitutePoly(f,Substitutionlist); // substitute found values
430    i= Substitutionlist.length() + 1;
431  }
432
433  if ( degree(Extension) > 0 )
434  { // working over Extensions
435    DEBOUTLN(CERR, "try_specializePoly: working over Extensions: ", Extension);
436    if (Extension.level() > 0)
437    {
438    //  AlgExtGenerator g(Extension,minpoly );
439    //  for ( int k=i ; k<j ; k++ ) // try to find specialization for all
440    //  {                           // variables (# = k ) beginning with the
441    //                             // starting value i
442    //    ok= specialize_agvariable( ff, deg, Substitutionlist, k, j, g );
443    //    if ( ! ok ) return 0; // we failed
444    //  }
445      #ifndef NDEBUG
446        //printf("libfac: try_specializePoly: extension level >0\n");
447      #endif
448      return 0; // we failed
449    }
450    else
451    {
452      AlgExtGenerator g(Extension);
453      for ( int k=i ; k<j ; k++ ) // try to find specialization for all
454      {                           // variables (# = k ) beginning with the
455                                 // starting value i
456        ok= specialize_agvariable( ff, deg, Substitutionlist, k, j, g );
457        if ( ! ok ) return 0; // we failed
458      }
459    }
460  }
461  else{ // working over the ground-field
462    FFGenerator g;
463    DEBOUTMSG(CERR, "try_specializePoly: working over the ground-field.");
464    for ( int k=i ; k<j ; k++ ){
465      ok= specialize_variable( ff, deg, Substitutionlist, k, j, g );
466      if ( ! ok ) return 0; // we failed
467    }
468  }
469  return 1;
470}
471
472static int
473specializePoly(const CanonicalForm & f, Variable & Extension, int deg, SFormList & Substitutionlist, int i,int j){
474  Variable minpoly= Extension;
475  int ok,extended= degree(Extension), working_over_extension;
476
477  // Remember if we are working over an extension-field
478  if ( extended >= 2 )    { working_over_extension = 1; }
479  else                    { working_over_extension = 0; extended = 1; }
480  // First try:
481  ok = try_specializePoly(f,minpoly,deg,Substitutionlist,i,j);
482  while ( ! ok ){ // we have to extend!
483    extended+= 1;
484    if ( ! working_over_extension ){
485      minpoly= rootOf(generate_mipo( extended,Extension ));
486      Extension= minpoly;
487      ok= try_specializePoly(f,minpoly,deg,Substitutionlist,i,j);
488    }
489    else
490    {
491      factoryError("libfac: spezializePoly ERROR: Working over given extension-field not yet implemented!");
492      return 0;
493    }
494  }
495  return 1;
496}
497
498
499// This is a procedure to play with: lot's of parameters!
500// returns: 0  iff no success (possibly because Extension isn't great enough
501//          >0 iff g (univariate) splits into n factors;
502// if n>0 BestEvaluationpoint contains the choice of values for the variables
503//
504// tries to find at least maxtries evaluation points
505// if g factored sametries into the same number of poly's the procedure stops
506// if we tried failtries evaluations not found valid, we stop. Perhaps
507// Extension isn't big enough!
508static int
509evaluate( int maxtries, int sametries, int failtries, const CanonicalForm &f , const Variable & Extension, const CanonicalForm &mipo, SFormList & BestEvaluationpoint, CFFList & BestFactorisation ){
510  int minfactors=degree(f),degf=degree(f),n=level(f.mvar())-1;
511  SFormList minEvaluation;
512  CFFList minFactorisation;
513  int samefactors=0, failedfactor=0, tried=0;
514  FFRandom gen;
515  CFFList unilist;
516
517  if ( degree(Extension) >0 ) GFRandom gen;
518  else
519  {
520    if ( degree(Extension) == 0 ) FFRandom gen;
521    else
522    {
523      factoryError("libfac: evaluate: Extension not inFF() or inGF() !");
524    }
525  }
526  REvaluation k(1,n,gen);
527  k.nextpoint();
528  for ( int i=1; i<=maxtries ; i++)
529  {
530    // k.nextpoint();
531    SFormList Substitutionlist;
532    for ( int j=1; j<=n; j++ )
533     Substitutionlist.insert(SForm(Variable(j),k[j]));
534    k.nextpoint();
535    CanonicalForm g=substitutePoly(f,Substitutionlist);
536    if ( various_tests(g, degf,1) )
537    { // found a valid point
538      failedfactor = 0; tried += 1;
539      if ( degree(Extension) == 0   )
540        unilist = factorize(g,1); // poly is sqr-free!
541      else
542      {
543        unilist = factorize2(g,Extension,mipo);
544      }
545      if (unilist.length() <= minfactors )
546      {
547        minfactors=unilist.length();
548        minEvaluation=Substitutionlist;
549        minFactorisation=unilist;
550      }
551      else samefactors +=1;
552
553      if (unilist.length() == 1 ) // wow! we found f is irreducible!
554      {
555        BestEvaluationpoint=minEvaluation;
556        BestFactorisation=minFactorisation;
557        return 1;
558      }
559
560      if ( samefactors >= sametries ) // now we stop ( maybe polynomial *has*
561                                      // minfactors factors? )
562      {
563        BestEvaluationpoint=minEvaluation;
564        BestFactorisation=minFactorisation;
565        return minfactors;
566      }
567
568    }
569    else
570      failedfactor += 1;
571
572    if ( failedfactor >= failtries ) // now we stop ( perhaps Extension isn't
573                                     // big enough )
574    {
575      if ( tried == 0 )
576        return 0;
577      else
578      {
579        BestEvaluationpoint=minEvaluation;
580        BestFactorisation=minFactorisation;
581        return minfactors;
582      }
583    }
584  }
585  BestEvaluationpoint=minEvaluation;
586  BestFactorisation=minFactorisation;
587  return minfactors;
588}
589
590///////////////////////////////////////////////////////////////
591// A factorization routine for a sqrfree polynomial.         //
592// Returns the list of factors.                              //
593///////////////////////////////////////////////////////////////
594CFFList
595Factorized( const CanonicalForm & F, const CanonicalForm & alpha, int Mainvar)
596{
597  CanonicalForm f,lt,ff,ffuni;
598  Variable Extension=alpha.mvar();
599  CFFList Outputlist,UnivariateFactorlist,Outputlist2;
600  SFormList Substitutionlist, Evaluationpoint;
601  CFFactor copy;
602  int mainvar=Mainvar,success,oldmainvar;
603  CFMap m;
604
605  // INTERRUPTHANDLER
606  if ( interrupt_handle() ) return CFFList() ;
607  // INTERRUPTHANDLER
608
609  if (F.inCoeffDomain()) {  return CFFList(CFFactor(F,1)); }
610  if ( F.isUnivariate() ) // could have lost one Variable elsewhere
611  {
612    if ( degree(Extension) == 0 )
613    {
614      TIMING_START(evaluate_time);
615      Outputlist = factorize(F,1); // poly is sqr-free
616      TIMING_END(evaluate_time);
617      return Outputlist;
618    }
619    else
620    {
621      if (Extension.level()<0)
622      DEBOUTLN(CERR, "Univ. Factorization over extension of degree ",
623               degree(getMipo(Extension,'x')) );
624      else
625      DEBOUTLN(CERR, "Univ. Factorization over extension of level ??",
626                Extension.level());
627      TIMING_START(evaluate_time);
628     #if 1
629     Outputlist = factorize2(F,Extension,alpha);
630     #else
631      Variable X;
632      CanonicalForm mipo=getMipo(Extension,X);
633      CFList as(mipo);
634      Outputlist = newfactoras( F, as, 1);
635     #endif
636      TIMING_END(evaluate_time);
637      return Outputlist;
638    }
639  }
640
641  if ( Mainvar ) oldmainvar=Mainvar; else oldmainvar=level(F);
642  // First choose a main variable; this may be revisted in the next step
643  mainvar = choose_main_variable(F);
644  // Let`s look if @f/@mainvar is nonzero
645  mainvar = necessary_condition(F,mainvar);
646  // Now we have definetly choosen a main variable
647  // swap poly such that the mainvar has highest level
648  f=swapvar(F,mainvar,level(F));
649
650  // INTERRUPTHANDLER
651  if ( interrupt_handle() ) return CFFList() ;
652  // INTERRUPTHANDLER
653
654  if ( oldmainvar != mainvar ){
655    DEBOUTSL(CERR); DEBOUT(CERR,"Swapped poly ", F);
656    DEBOUT(CERR, " in ", f); DEBOUTNL(CERR);
657    DEBOUTSL(CERR); DEBOUT(CERR,"Swapped  ", oldmainvar );
658    DEBOUT(CERR, " <-- ", mainvar ); DEBOUT(CERR, "  Mainvar= ", f.mvar());
659    DEBOUTNL(CERR);
660    ff = f.deriv();
661    TIMING_START(discr_time);
662    ffuni = gcd(f,ff);
663    TIMING_END(discr_time);
664    if ( !(ffuni.isOne()) ){ //discriminante nonzero: split poly
665      DEBOUTLN(CERR,"Nontrivial GCD of f= ", f);
666      DEBOUTLN(CERR,"             and @f= ", ff);
667      DEBOUTLN(CERR,"          GCD(f,@f)= ", ffuni);
668      ff=f/ffuni;
669      CFFList Outputlist_a, Outputlist_b;
670      Outputlist_a = Factorized(ff,alpha);
671      DEBOUTLN(CERR, "Outputlist_a = ", Outputlist_a);
672      Outputlist_b = Factorized(ffuni,alpha);
673      DEBOUTLN(CERR, "Outputlist_b = ", Outputlist_b);
674      Outputlist = myUnion(Outputlist_a, Outputlist_b);
675      // have to back-swapvar the factors....
676      for ( CFFListIterator i=Outputlist; i.hasItem(); i++ ){
677        copy=i.getItem();
678        Outputlist2.append(CFFactor(swapvar(copy.factor(),oldmainvar,mainvar),copy.exp()));
679      }
680      DEBOUTLN(CERR, "Outputlist2 (a+b swapped) (to return) = ", Outputlist2);
681      return Outputlist2;
682    }
683  }
684
685  // Check special cases
686  for ( int i=1; i<=level(F); i++)
687  {
688    if ( degree(f,Variable(i) ) == 1 )
689    //test trivial case; only true iff F is primitiv w.r.t every variable; else check (if F=ax+b) gcd(a,b)=1 ?
690    {
691      DEBOUTLN(CERR, "Trivial case: ", F);
692      Outputlist.append(CFFactor(F,1));
693      return Outputlist;
694    }
695  }
696
697  // Look at the leading term:
698  lt = LC(f);
699  DEBOUTLN(CERR, "Leading term: ", lt);
700  //if ( lt != f.genOne() )
701  if ( !lt.isOne() )
702  {
703    // make the polynomial monic in the main variable
704    ff = make_monic(f,lt); ffuni = ff;
705    DEBOUTLN(CERR, "make_monic returned: ", ff);
706  }
707  else{ ff= f; ffuni= ff; }
708
709  TIMING_START(evaluate_time);
710  success=evaluate(min(10,max(degree(ff), 5)), min(degree(ff),3), min(degree(ff),3), ff, Extension, alpha, Substitutionlist,UnivariateFactorlist);
711  DEBOUTLN(CERR,  "Returned from evaluate: success: ", success);
712  for ( SFormListIterator ii=Substitutionlist; ii.hasItem(); ii++ )
713  {
714    DEBOUTLN(CERR, "Substituting ", ii.getItem().factor());
715    DEBOUTLN(CERR, "       with value: ", ii.getItem().exp());
716  }
717
718  if ( success==0 ) // evalute wasn't successfull
719  {
720    success= specializePoly(ffuni,Extension,degree(ff),Substitutionlist,1,getNumVars(compress(ff,m)));
721    DEBOUTLN(CERR,  "Returned from specializePoly: success: ", success);
722    if (success == 0 ) // No spezialisation could be found
723    {
724      factoryError("libfac: Factorize: ERROR: Not able to find a valid specialization!");
725      Outputlist.append(CFFactor(F,1));
726      return Outputlist;
727    }
728
729    // INTERRUPTHANDLER
730    if ( interrupt_handle() ) return CFFList() ;
731    // INTERRUPTHANDLER
732
733    ffuni = substitutePoly(ff,Substitutionlist);
734    // We now have an univariat poly; factorize that
735    if ( degree(Extension) == 0   )
736    {
737      DEBOUTMSG(CERR, "Univ. Factorization over the ground field");
738      UnivariateFactorlist = factorize(ffuni,1); // univ. poly is sqr-free!
739    }
740    else
741    {
742      DEBOUTLN(CERR, "Univ. Factorization over extension of degree ",
743               degree(getMipo(Extension,'x')) );
744     #if 1
745      UnivariateFactorlist = factorize2(ffuni,Extension,alpha);
746     #else
747      Variable X;
748      CanonicalForm mipo=getMipo(Extension,X);
749      CFList as(mipo);
750      UnivariateFactorlist = newfactoras( ffuni, as, 1);
751     #endif
752    }
753  }
754  else
755  {
756    ffuni = substitutePoly(ff,Substitutionlist);
757  }
758    TIMING_END(evaluate_time);
759  if (UnivariateFactorlist.length() == 1)
760  { // poly is irreduzibel
761    DEBOUTLN(CERR, "Univ. poly is irreduzible: ", UnivariateFactorlist);
762    Outputlist.append(CFFactor(F,1));
763    return Outputlist;
764  }
765  else
766  { // we have factors
767    DEBOUTSL(CERR);
768    DEBOUT(CERR, "Univariate poly has " , UnivariateFactorlist.length());
769    DEBOUT(CERR, " factors:  ", ffuni);
770    DEBOUT(CERR, " = ", UnivariateFactorlist); DEBOUTNL(CERR);
771
772    // INTERRUPTHANDLER
773    if ( interrupt_handle() ) return CFFList() ;
774    // INTERRUPTHANDLER
775
776    TIMING_START(hensel_time);
777    Outputlist = MultiHensel(ff,UnivariateFactorlist,Substitutionlist, alpha);
778    DEBOUTLN(CERR, "Outputlist after MultiHensel: ", Outputlist);
779    TIMING_END(hensel_time);
780
781    // INTERRUPTHANDLER
782    if ( interrupt_handle() ) return CFFList() ;
783    // INTERRUPTHANDLER
784
785    TIMING_START(truefactor_time);
786    Outputlist = Truefactors(ff, level(ff), Substitutionlist, Outputlist);
787    DEBOUTLN(CERR, "Outputlist after Truefactors: ", Outputlist);
788    TIMING_END(truefactor_time);
789
790    // INTERRUPTHANDLER
791    if ( interrupt_handle() ) return CFFList() ;
792    // INTERRUPTHANDLER
793
794    //if ( lt != f.genOne() )
795    if ( !lt.isOne() )
796    {
797      Outputlist = not_monic(Outputlist,lt,ff,level(ff));
798      DEBOUTLN(CERR, "not_monic returned: ", Outputlist);
799    }
800
801    // have to back-swapvar the factors....
802    for ( CFFListIterator i=Outputlist; i.hasItem(); i++ )
803    {
804      copy=i.getItem();
805      Outputlist2.append(CFFactor(swapvar(copy.factor(),oldmainvar,mainvar),copy.exp()));
806    }
807
808    return Outputlist2;
809  }
810}
811
812int cmpCF( const CFFactor & f, const CFFactor & g );
813
814///////////////////////////////////////////////////////////////
815// The user front-end for a uni/multivariate factorization   //
816// routine. F needs not to be SqrFree.                       //
817// Option of * choosing a  main variable (n.y.i.)            //
818//           * choosing an algebraic extension (n.y.u.)      //
819//           * ensuring poly is sqrfree (n.y.i.)             //
820// use Factorize(F,alpha,is_SqrFree) if not over Zp[x]/Q[x]  //
821///////////////////////////////////////////////////////////////
822int find_mvar(const CanonicalForm &f);
823CFFList Factorize(const CanonicalForm & F, int is_SqrFree )
824{
825  //out_cf("Factorize ",F,"\n");
826  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
827  ListIterator<CFFactor> i,j;
828  CanonicalForm g=1,unit=1,r=1;
829  Variable minpoly; // dummy
830  int exp;
831  CFMap m;
832
833  // INTERRUPTHANDLER
834  if ( interrupt_handle() ) return CFFList() ;
835  // INTERRUPTHANDLER
836
837  DEBINCLEVEL(CERR, "Factorize");
838  DEBOUTLN(CERR, "Called with F= ", F);
839  if (( getCharacteristic() == 0 ) || (F.isUnivariate()))
840  { // char == 0
841    TIMING_START(factorize_time);
842    //CERR << "Factoring in char=0 of " << F << " = " << Outputlist << "\n";
843    Outputlist= factorize(F);
844    // Factorization in char=0 doesn't sometimes return at least two elements!!!
845    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
846      Outputlist.insert(CFFactor(1,1));
847    //CERR << "  Factorize in char=0: returning with: " << Outputlist << "\n";
848    TIMING_END(factorize_time);
849    DEBDECLEVEL(CERR, "Factorize");
850    TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
851    return Outputlist;
852  }
853  TIMING_START(factorize_time);
854  // search an "optimal" main variavble
855  int mv=F.level();
856  if ((mv != LEVELBASE) /* && (! F.isUnivariate()) */)
857  {
858     mv=find_mvar(F);
859     if (mv!=F.level())
860     {
861       swapvar(F,Variable(mv),F.mvar());
862     }
863  }
864
865  ///////
866  // Maybe it`s better to add a sqrfree-test before?
867  // (If gcd is fast...)
868  ///////
869  //  if ( ! SqrFreeTest(F) ){
870  if ( ! is_SqrFree )
871  {
872    TIMING_START(sqrfree_time);
873    SqrFreeList = SqrFreeMV(F) ; // first sqrfree the polynomial
874    // don't use sqrFree(F), factory's internal sqrFree for multiv.
875    // Polynomials; it's wrong!! Ex.: char=p   f= x^p*(y+1);
876    // SqrFreeMV(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
877    TIMING_END(sqrfree_time);
878
879    // INTERRUPTHANDLER
880    if ( interrupt_handle() ) return CFFList() ;
881    // INTERRUPTHANDLER
882
883  }
884  else
885    SqrFreeList.append(CFFactor(F,1));
886
887  DEBOUTLN(CERR, "SqrFreeMV= ", SqrFreeList);
888  for ( i=SqrFreeList; i.hasItem(); i++ )
889  {
890    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
891    // We need a compress on each list item ! Maybe we have less variables!
892    g =compress(i.getItem().factor(),m);
893    exp = i.getItem().exp();
894    if ( getNumVars(g) ==0 ) // a constant; Exp==1
895      Outputlist.append( CFFactor(g,1) ) ;
896    else// a real polynomial
897      if ( g.isUnivariate() )
898      {
899        //out_cf("univ. poly: ",g,"\n");
900        Intermediatelist=factorize(g,1); // poly is sqr-free!
901        for ( j=Intermediatelist; j.hasItem(); j++ )
902          //Normally j.getItem().exp() should be 1
903          Outputlist.append( CFFactor( m(j.getItem().factor()),exp*j.getItem().exp()));
904      }
905      else
906      { // multivariate polynomial
907        if ( g.isHomogeneous() )
908        {
909          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
910          // Now we can substitute one variable to 1, factorize and then
911          // look on the resulting factors and their monomials for
912          // backsubstitution of the substituted variable.
913          Intermediatelist = HomogFactor(g, minpoly, 0);
914        }
915        else // not homogeneous
916          Intermediatelist = Factorized(g, minpoly, 0);
917
918        // INTERRUPTHANDLER
919        if ( interrupt_handle() ) return CFFList() ;
920        // INTERRUPTHANDLER
921
922        for ( j=Intermediatelist; j.hasItem(); j++ )
923          //Normally j.getItem().exp() should be 1
924          Outputlist= myappend( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
925      }
926  }
927  g=1; unit=1;
928  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
929  for ( i=Outputlist; i.hasItem(); i++ )
930    if ( level(i.getItem().factor()) > 0 )
931    {
932      unit = lc(i.getItem().factor());
933      if ( getNumVars(unit) == 0 )
934      { // a constant; possibly 1
935        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
936        g *=power(i.getItem().factor()/unit,i.getItem().exp());
937      }
938      else
939      {
940        Outputlist2.append(i.getItem());
941        g *=power(i.getItem().factor(),i.getItem().exp());
942      }
943    }
944
945  r=F/g;
946  Outputlist2.insert(CFFactor(r,1));
947
948  if ((mv!=F.level()) && (! F.isUnivariate() ))
949  {
950    CFFListIterator J=Outputlist2;
951    for ( ; J.hasItem(); J++)
952    {
953      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
954    }
955    swapvar(F,Variable(mv),F.mvar());
956  }
957  DEBDECLEVEL(CERR, "Factorize");
958  TIMING_END(factorize_time);
959
960  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
961  TIMING_PRINT(discr_time, "time used for discriminante   : ");
962  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
963  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
964  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
965  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
966
967  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
968
969  return Outputlist2;
970}
971
972///////////////////////////////////////////////////////////////
973// The user front-end for a uni/multivariate factorization   //
974// routine. F needs not to be SqrFree.                       //
975// Option of * choosing a  main variable (n.y.i.)            //
976//           * choosing an algebraic extension (n.y.u.)      //
977//           * ensuring poly is sqrfree (n.y.i.)             //
978///////////////////////////////////////////////////////////////
979static bool fdivides2(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &minpoly)
980{
981  if (!minpoly.isZero())
982  {
983  #if 0
984    Variable Alpha=minpoly.mvar();
985    Variable X=rootOf(minpoly);
986    CanonicalForm rF=replacevar(F,Alpha,X);
987    CanonicalForm rG=replacevar(G,Alpha,X);
988    return fdivides(rF,rG);;
989  #else
990    if (degree(F,F.mvar()) > degree(G,F.mvar())) return false;
991    return true;
992    //CanonicalForm a,b;
993    //mydivrem(G,F,a,b);
994    //if (b.isZero()) return true;
995    //else return false;
996  #endif
997  }
998  else
999   return fdivides(F,G);
1000}
1001CFFList Factorize2(CanonicalForm F, const CanonicalForm & minpoly )
1002{
1003#ifndef NDEBUG
1004  //printf("start Factorize2(int_flag=%d)\n",libfac_interruptflag);
1005#endif
1006  CFFList G,H;
1007  CanonicalForm fac;
1008  int d,e;
1009  ListIterator<CFFactor> i,k;
1010  libfac_interruptflag=0;
1011  CFFList iF=Factorize(F,minpoly);
1012  if ((libfac_interruptflag==0)&&(!iF.isEmpty()))
1013    H=iF;
1014  else
1015  {
1016#ifndef NDEBUG
1017    //printf("variant 2(int_flag=%d)\n",libfac_interruptflag);
1018#endif
1019    libfac_interruptflag=0;
1020    iF=Factorize(F);
1021    if (libfac_interruptflag==0)
1022    {
1023      i = iF;
1024      while( i.hasItem())
1025      {
1026        d = i.getItem().exp();
1027        fac = i.getItem().factor();
1028        if (fdivides(fac,F))
1029        {
1030          if ((getNumVars(fac)==0)||(fac.degree()<=1))
1031          {
1032#ifndef NOSTREAMIO
1033#ifndef NDEBUG
1034            //printf("append trivial factor\n");
1035#endif
1036#endif
1037            H.append( CFFactor( fac, d));
1038            do {F/=fac; d--; } while (d>0);
1039          }
1040          else
1041          {
1042            G = Factorize( fac, minpoly);
1043            if (libfac_interruptflag!=0)
1044            {
1045              libfac_interruptflag=0;
1046              k = G;
1047              while( k.hasItem())
1048              {
1049                fac = k.getItem().factor();
1050                int dd = k.getItem().exp()*d;
1051                e=0;
1052                while ((!fac.isZero())&& fdivides2(fac,F,minpoly) && (dd>0))
1053                {
1054#ifndef NOSTREAMIO
1055#ifndef NDEBUG
1056                  //out_cf("factor:",fac,"\n");
1057#endif
1058#endif
1059                  e++;dd--;
1060                  F/=fac;
1061                }
1062                if (e>0) H.append( CFFactor( fac , e ) );
1063                ++k;
1064              }
1065            }
1066          }
1067        }
1068        ++i;
1069      }
1070    }
1071  }
1072  //Outputlist = newfactoras( F, as, 1);
1073  if((isOn(SW_USE_NTL_SORT))&&(!H.isEmpty())) H.sort(cmpCF);
1074#ifndef NDEBUG
1075  //printf("end Factorize2(%d)\n",libfac_interruptflag);
1076#endif
1077  return H;
1078}
1079
1080CFFList
1081Factorize(const CanonicalForm & F, const CanonicalForm & minpoly, int is_SqrFree )
1082{
1083  //out_cf("Factorize: F=",F,"\n");
1084  //out_cf("           minpoly:",minpoly,"\n");
1085  CFFList Outputlist,SqrFreeList,Intermediatelist,Outputlist2;
1086  ListIterator<CFFactor> i,j;
1087  CanonicalForm g=1,unit=1,r=1;
1088  //Variable minpoly; // reserved (-> Factorisation over algebraic Extensions)
1089  int exp;
1090  CFMap m;
1091
1092  // INTERRUPTHANDLER
1093  if ( interrupt_handle() ) return CFFList() ;
1094  // INTERRUPTHANDLER
1095
1096  DEBINCLEVEL(CERR, "Factorize");
1097  DEBOUTLN(CERR, "Called with F= ", F);
1098  if ( getCharacteristic() == 0 )
1099  { // char == 0
1100    TIMING_START(factorize_time);
1101    //CERR << "Factoring in char=0 of " << F << " = " << Outputlist << "\n";
1102    #if 0
1103    // SHOULD: Outputlist= factorize(F,minpoly);
1104    Outputlist= factorize(F);
1105    #else
1106    if (!minpoly.isZero())
1107    {
1108      if ( F.isHomogeneous() )
1109      {
1110        DEBOUTLN(CERR, "Poly is homogeneous! : ", F);
1111        // Now we can substitute one variable to 1, factorize and then
1112        // look on the resulting factors and their monomials for
1113        // backsubstitution of the substituted variable.
1114        Outputlist=HomogFactor(F, minpoly, 0);
1115      }
1116      else
1117      {
1118        CFList as(minpoly);
1119        //CFFList sqF=sqrFree(F); // sqrFreeZ
1120        CFFList sqF=SqrFreeMV(F,minpoly);
1121        if (sqF.isEmpty()) sqF=sqrFree(F);
1122        CFFList G,H;
1123        CanonicalForm fac;
1124        int d;
1125        ListIterator<CFFactor> i,k;
1126        for ( i = sqF; i.hasItem(); ++i )
1127        {
1128          d = i.getItem().exp();
1129          fac = i.getItem().factor();
1130          int success=1;
1131          G = newfactoras( fac, as, success);
1132          for ( k = G; k.hasItem(); ++k )
1133          {
1134            fac = k.getItem().factor();
1135            int dd = k.getItem().exp();
1136            H.append( CFFactor( fac , d*dd ) );
1137          }
1138        }
1139        //Outputlist = newfactoras( F, as, 1);
1140        Outputlist = H;
1141      }
1142    }
1143    else // minpoly==0
1144      Outputlist=factorize(F);
1145    #endif
1146    // Factorization in char=0 doesn't sometimes return at least two elements!!!
1147    if ( getNumVars(Outputlist.getFirst().factor()) != 0 )
1148      Outputlist.insert(CFFactor(1,1));
1149    //CERR << "  Factorize in char=0: returning with: " << Outputlist << "\n";
1150    TIMING_END(factorize_time);
1151    DEBDECLEVEL(CERR, "Factorize");
1152    TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1153    //out_cff(Outputlist);
1154    return Outputlist;
1155  }
1156  TIMING_START(factorize_time);
1157  // search an "optimal" main variavble
1158  int mv=F.level();
1159  if (mv != LEVELBASE && ! F.isUnivariate() )
1160  {
1161     mv=find_mvar(F);
1162     if (mv!=F.level())
1163     {
1164       swapvar(F,Variable(mv),F.mvar());
1165     }
1166  }
1167
1168  ///////
1169  // Maybe it`s better to add a sqrfree-test before?
1170  // (If gcd is fast...)
1171  ///////
1172  //  if ( ! SqrFreeTest(F) ){
1173  if ( ! is_SqrFree )
1174  {
1175    TIMING_START(sqrfree_time);
1176    SqrFreeList = SqrFreeMV(F, minpoly) ; // first sqrfree the polynomial
1177    // don't use sqrFree(F), factory's internal sqrFree for multiv.
1178    // Polynomials; it's wrong!! Ex.: char=p   f= x^p*(y+1);
1179    // SqrFreeMV(f)= ( y+1, (x)^p ), sqrFree(f)= ( y+1 ) .
1180    TIMING_END(sqrfree_time);
1181
1182    // INTERRUPTHANDLER
1183    if ( interrupt_handle() ) return CFFList() ;
1184    // INTERRUPTHANDLER
1185
1186  }
1187  else
1188    SqrFreeList.append(CFFactor(F,1));
1189  DEBOUTLN(CERR, "SqrFreeMV= ", SqrFreeList);
1190  for ( i=SqrFreeList; i.hasItem(); i++ )
1191  {
1192    DEBOUTLN(CERR, "Factor under consideration: ", i.getItem().factor());
1193    // We need a compress on each list item ! Maybe we have less variables!
1194    g =compress(i.getItem().factor(),m);
1195    exp = i.getItem().exp();
1196    if ( getNumVars(g) ==0 ) // a constant; Exp==1
1197      Outputlist.append( CFFactor(g,1) ) ;
1198    else// a real polynomial
1199    {
1200      if ( g.isUnivariate() )
1201      {
1202        Variable alpha=rootOf(minpoly);
1203        Intermediatelist=factorize2(g,alpha,minpoly); // poly is sqr-free!
1204        for ( j=Intermediatelist; j.hasItem(); j++ )
1205          //Normally j.getItem().exp() should be 1
1206          Outputlist.append(
1207           CFFactor( m(replacevar(j.getItem().factor(),alpha,minpoly.mvar())),
1208             exp*j.getItem().exp()));
1209      }
1210      else // multivariate polynomial
1211      {
1212        if ( g.isHomogeneous() )
1213        {
1214          DEBOUTLN(CERR, "Poly is homogeneous! : ", g);
1215          // Now we can substitute one variable to 1, factorize and then
1216          // look on the resulting factors and their monomials for
1217          // backsubstitution of the substituted variable.
1218          Intermediatelist = HomogFactor(g, minpoly, 0);
1219        }
1220        else // not homogeneous
1221          Intermediatelist = Factorized(g, minpoly, 0);
1222
1223        // INTERRUPTHANDLER
1224        if ( interrupt_handle() ) return CFFList() ;
1225        // INTERRUPTHANDLER
1226
1227        for ( j=Intermediatelist; j.hasItem(); j++ )
1228          //Normally j.getItem().exp() should be 1
1229          Outputlist= myappend( Outputlist, CFFactor(m(j.getItem().factor()),exp*j.getItem().exp()));
1230      }
1231    }
1232  }
1233  g=1; unit=1;
1234  DEBOUTLN(CERR, "Outputlist is ", Outputlist);
1235  for ( i=Outputlist; i.hasItem(); i++ )
1236    if ( level(i.getItem().factor()) > 0 )
1237    {
1238      unit = lc(i.getItem().factor());
1239      if ( getNumVars(unit) == 0 ){ // a constant; possibly 1
1240        Outputlist2.append(CFFactor(i.getItem().factor()/unit , i.getItem().exp()));
1241        g *=power(i.getItem().factor()/unit,i.getItem().exp());
1242      }
1243      else
1244      {
1245        Outputlist2.append(i.getItem());
1246        g *=power(i.getItem().factor(),i.getItem().exp());
1247      }
1248    }
1249
1250  r=F/g;
1251  Outputlist2.insert(CFFactor(r,1));
1252
1253  if ((mv!=F.level()) && (! F.isUnivariate() ))
1254  {
1255    CFFListIterator J=Outputlist2;
1256    for ( ; J.hasItem(); J++)
1257    {
1258      swapvar(J.getItem().factor(),Variable(mv),F.mvar());
1259    }
1260    swapvar(F,Variable(mv),F.mvar());
1261  }
1262
1263  DEBDECLEVEL(CERR, "Factorize");
1264  TIMING_END(factorize_time);
1265
1266  TIMING_PRINT(sqrfree_time, "\ntime used for sqrfree   : ");
1267  TIMING_PRINT(discr_time, "time used for discriminante   : ");
1268  TIMING_PRINT(evaluate_time, "time used for evaluation and univ. factorization  : ");
1269  TIMING_PRINT(hensel_time, "time used for hensel-lift   : ");
1270  TIMING_PRINT(truefactor_time, "time used for truefactors   : ");
1271  TIMING_PRINT(factorize_time, "\ntime used for factorization   : ");
1272
1273  if(isOn(SW_USE_NTL_SORT)) Outputlist2.sort(cmpCF);
1274
1275  //out_cff(Outputlist2);
1276  return Outputlist2;
1277}
1278
Note: See TracBrowser for help on using the repository browser.