source: git/libfac/charset/alg_factor.cc @ 4a81ec

spielwiese
Last change on this file since 4a81ec was 4a81ec, checked in by Hans Schönemann <hannes@…>, 26 years ago
* hannes/michael: libfac-0.3.0 git-svn-id: file:///usr/local/Singular/svn/trunk@708 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 19.8 KB
Line 
1/* Copyright 1997 Michael Messollen. All rights reserved. */
2////////////////////////////////////////////////////////////
3// emacs edit mode for this file is -*- C++ -*-
4////////////////////////////////////////////////////////////
5static char * rcsid = "$Id: alg_factor.cc,v 1.2 1997-09-12 07:19:37 Singular Exp $";
6////////////////////////////////////////////////////////////
7// FACTORY - Includes
8#include <factory.h>
9// Factor - Includes
10#include <tmpl_inst.h>
11#include <Factor.h>
12#include <SqrFree.h>
13#include <helpstuff.h>
14// Charset - Includes
15#include "csutil.h"
16#include "charset.h"
17#include "reorder.h"
18#include "algfactor.h"
19// some CC's need this:
20#include "alg_factor.h"
21
22#ifdef ALGFACTORDEBUG
23#  define DEBUGOUTPUT
24#else
25#  undef DEBUGOUTPUT
26#endif
27
28#include "debug.h"
29#include "timing.h"
30TIMING_DEFINE_PRINT(newfactoras_time);
31
32////////////////////////////////////////////////////////////////////////
33// This implements the algorithm of Trager for factorization of
34// (multivariate) polynomials over algebraic extensions and so called
35// function field extensions.
36////////////////////////////////////////////////////////////////////////
37
38// // missing class: IntGenerator:
39bool IntGenerator::hasItems() const
40{
41    return 1;
42}
43
44CanonicalForm IntGenerator::item() const
45//int IntGenerator::item() const
46{
47  //return current; //CanonicalForm( current );
48  return mapinto(CanonicalForm( current ));
49}
50
51void IntGenerator::next()
52{
53    current++;
54}
55
56// replacement for factory's broken psr
57static CanonicalForm
58mypsr ( const CanonicalForm &rr, const CanonicalForm &vv, const Variable & x ){
59  CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue;
60  int dr, dv, d,n=0;
61
62
63  dr = degree( r, x );
64  dv = degree( v, x );
65  if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);}
66  else { l = 1; }
67  d= dr-dv+1;
68  while ( ( dv <= dr  ) && ( r != r.genZero()) ){
69    test = power(x,dr-dv)*v*LC(r,x);
70    if ( dr == 0 ) { r= CanonicalForm(0); }
71    else { r= r - LC(r,x)*power(x,dr); }
72    r= l*r -test;
73    dr= degree(r,x);
74    n+=1;
75  }
76  r= power(l, d-n)*r;
77  return r;
78}
79
80// replacement for factory's broken resultant
81static CanonicalForm
82resultante( const CanonicalForm & f, const CanonicalForm& g, const Variable & v ){
83  CanonicalForm h, beta, help, F, G;
84  int delta;
85
86  DEBOUTLN( cout, "resultante: called  f= ", f);
87  DEBOUTLN( cout, "resultante: called  g= ", g);
88  DEBOUTLN( cout, "resultante: called  v= ", v);
89  if ( f.mvar() < v || g.mvar() < v ){
90    DEBOUTMSG(cout, "resultante: f.mvar() < v || g.mvar() < v");
91    return 1;
92  }
93
94  if ( f.degree( v ) < 1 || g.degree( v ) < 1 ){ 
95    DEBOUTMSG(cout, "resultante: f.degree( v ) < 1 || g.degree( v ) < 1");
96    // If deg(F,v) == 0 , then resultante(F,G,v) = F^n, where n=deg(G,v)
97    if ( f.degree( v ) < 1 ) return power(f,degree(g,v));
98    else return power(g,degree(f,v));
99  }
100
101   if ( f.degree( v ) >= g.degree( v ) ) { F = f; G = g; }
102   else { G = f; F = g; }
103
104  h = CanonicalForm(1);
105  while ( G != G.genZero() ) {
106     delta= degree(F,v) -degree(G,v);
107     beta = power(CanonicalForm(-1), delta+1) * LC(F,v)* power(h, delta);
108     h= (h * power(LC(G,v), delta)) / power(h, delta);
109     help= G;
110     G= mypsr(F,G,v);
111     G= G/beta;
112     F=help;
113   }
114   if ( degree(F,v) != 0 ) F= CanonicalForm(0);
115   return F;
116}
117
118// sqr-free routine for algebraic extensions
119// we need it! Ex.: f=c^2+2*a*c-1; as=[a^2+1]; f=(c+a)^2
120static CFFList
121alg_sqrfree( const CanonicalForm & f ){
122  CFFList L;
123
124  L.append(CFFactor(f,1));
125  return L;
126}
127
128// Calculates a square free norm
129// Input: f(x, alpha) a square free polynomial over K(alpha),
130// alpha is defined by the minimal polynomial Palpha
131// K has more than S elements (S is defined in thesis; look getextension)
132static void
133sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha, 
134           CFGenerator & random, CanonicalForm & s,  CanonicalForm & g, 
135           CanonicalForm & R){ 
136  Variable y=PPalpha.mvar(),vf=f.mvar();
137  CanonicalForm temp, Palpha=PPalpha, t;
138  int sqfreetest=0;
139  CFFList testlist;
140  CFFListIterator i;
141 
142  DEBOUTLN(cout, "sqrf_norm_sub:      f= ", f);
143  DEBOUTLN(cout, "sqrf_norm_sub: Palpha= ", Palpha);
144  random.reset();   s=f.mvar()-random.item()*Palpha.mvar();   g=f;   
145  R= CanonicalForm(0);
146  DEBOUTLN(cout, "sqrf_norm_sub: random s= ", s);
147
148  // Norm, resultante taken with respect to y
149  while ( !sqfreetest ){
150    DEBOUTLN(cout, "sqrf_norm_sub: Palpha= ", Palpha);
151    R = resultante(Palpha, g, y); R= R* common_den(R);
152    DEBOUTLN(cout, "sqrf_norm_sub: R= ", R);
153    // sqfree check ; R is a polynomial in K[x]
154    if ( getCharacteristic() == 0 ){
155      temp= gcd(R, R.deriv(vf)); 
156      DEBOUTLN(cout, "sqrf_norm_sub: temp= ", temp);
157      if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; }
158      else { sqfreetest= 1; }
159      DEBOUTLN(cout, "sqrf_norm_sub: sqfreetest= ", sqfreetest);
160    }
161    else{ 
162      DEBOUTMSG(cout, "Starting SqrFreeTest(R)!");
163      // Look at SqrFreeTest!
164      // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 !
165      // for now we use this workaround with Factorize...
166      // ...but it should go away soon!!!!
167      testlist= Factorize(R);  testlist.removeFirst();
168      sqfreetest=1;
169      for ( i=testlist; i.hasItem(); i++)
170        if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0) { sqfreetest=0; break; }
171      DEBOUTLN(cout, "SqrFreeTest(R)= ", sqfreetest);
172    }
173    if ( ! sqfreetest ){
174      random.next();   
175      DEBOUTLN(cout, "sqrf_norm_sub generated new random item: ", random.item());
176      if ( getCharacteristic() == 0 ) t= CanonicalForm(mapinto(random.item()));
177      else t= CanonicalForm(random.item());
178      s= f.mvar()+t*Palpha.mvar(); // s defines backsubstitution
179      DEBOUTLN(cout, "sqrf_norm_sub: testing s= ", s); 
180      g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
181      DEBOUTLN(cout, "             gives g= ", g); 
182    }
183  }
184}
185
186static void
187sqrf_norm( const CanonicalForm & f, const CanonicalForm & PPalpha, 
188           const Variable & Extension, CanonicalForm & s,  CanonicalForm & g, 
189           CanonicalForm & R){ 
190 
191  DEBOUTLN(cout, "sqrf_norm:      f= ", f);
192  DEBOUTLN(cout, "sqrf_norm: Palpha= ", PPalpha);
193  if ( getCharacteristic() == 0 ) {
194    IntGenerator random; 
195    DEBOUTMSG(cout, "sqrf_norm: no extension, char=0");
196    sqrf_norm_sub(f,PPalpha, random, s,g,R);
197    DEBOUTLN(cout, "sqrf_norm:      f= ", f);
198    DEBOUTLN(cout, "sqrf_norm: Palpha= ", PPalpha);
199    DEBOUTLN(cout, "sqrf_norm:      s= ", s);
200    DEBOUTLN(cout, "sqrf_norm:      g= ", g);
201    DEBOUTLN(cout, "sqrf_norm:      R= ", R);
202  } 
203  else if ( degree(Extension) > 0 ){ // working over Extensions
204    DEBOUTLN(cout, "sqrf_norm: degree of extension is ", degree(Extension));
205    AlgExtGenerator random(Extension);
206    sqrf_norm_sub(f,PPalpha, random, s,g,R);
207  }
208  else{
209    FFGenerator random;
210    DEBOUTMSG(cout, "sqrf_norm: degree of extension is 0"); 
211    sqrf_norm_sub(f,PPalpha, random, s,g,R);
212  }
213}
214
215static Varlist
216Var_is_in_AS(const Varlist & uord, const CFList & Astar){
217  Varlist output;
218  CanonicalForm elem;
219  Variable x;
220
221  for ( VarlistIterator i=uord; i.hasItem(); i++){
222    x=i.getItem();
223    for ( CFListIterator j=Astar; j.hasItem(); j++ ){
224      elem= j.getItem();
225      if ( degree(elem,x) > 0 ){ // x actually occures in Astar
226        output.append(x);
227        break;
228      }
229    }
230  }
231  return output;
232}
233
234// Look if Minimalpolynomials in Astar define seperable Extensions
235// Must be a power of p: i.e. y^{p^e}-x
236static int
237inseperable(const CFList & Astar){
238  CanonicalForm elem;
239  int Counter= 1;
240
241  if ( Astar.length() == 0 ) return 0;
242  for ( CFListIterator i=Astar; i.hasItem(); i++){
243    elem= i.getItem();
244    if ( elem.deriv() == elem.genZero() ) return Counter;
245    else Counter += 1;
246  }
247  return 0;
248}
249
250// calculate gcd of f and g in char=0
251static CanonicalForm
252gcd0( CanonicalForm f, CanonicalForm g ){
253  int charac= getCharacteristic();
254  setCharacteristic(0); Off(SW_RATIONAL);
255  CanonicalForm ff= mapinto(f), gg= mapinto(g);
256  CanonicalForm result= gcd(ff,gg);
257  setCharacteristic(charac); On(SW_RATIONAL);
258  return mapinto(result);
259}
260
261// calculate big enough extension for finite fields
262// Idea: first calculate k, such that q^k > S (->thesis, -> getextension)
263// Second, search k with gcd(k,m_i)=1, where m_i is the degree of the i'th
264// minimal polynomial. Then the minpoly f_i remains irrd. over q^k and we
265// have enough elements to plug in.
266static int
267getextension( IntList & degreelist, int n){
268  int charac= getCharacteristic();
269  setCharacteristic(0); // need it for k !
270  int k=1, m=1, length=degreelist.length();
271  IntListIterator i;
272
273  for (i=degreelist; i.hasItem(); i++) m= m*i.getItem();
274  int q=charac;
275  while (q <= ((n*m)*(n*m)/2)) { k= k+1; q= q*charac;}
276  int l=0;
277  do {
278    for (i=degreelist; i.hasItem(); i++){
279      l= l+1;
280      if ( gcd0(k,i.getItem()) == 1){
281        DEBOUTLN(cout, "getextension: gcd == 1, l=",l);
282        if ( l==length ){ setCharacteristic(charac);  return k; }
283      }
284      else { DEBOUTMSG(cout, "getextension: Next iteration"); break; }
285    }
286    k= k+1; l=0;
287  }
288  while ( 1 );
289}
290
291// calculate a "primitive element"
292// K must have more than S elements (->thesis, -> getextension)
293static CFList 
294simpleextension(const CFList & Astar, const Variable & Extension, 
295                CanonicalForm & R){
296  CFList Returnlist, Bstar=Astar;
297  CanonicalForm s, g;
298
299  DEBOUTLN(cout, "simpleextension: Astar= ", Astar);
300  DEBOUTLN(cout, "simpleextension:     R= ", R);
301  if ( Astar.length() == 1 ){ R= Astar.getFirst();}
302  else{
303    R=Bstar.getFirst(); Bstar.removeFirst();
304    for ( CFListIterator i=Bstar; i.hasItem(); i++){
305      DEBOUTLN(cout, "simpleextension: f(x)= ", i.getItem());
306      DEBOUTLN(cout, "simpleextension: P(x)= ", R);
307      sqrf_norm(i.getItem(), R, Extension, s, g, R);
308      // spielt die Repraesentation eine Rolle?
309      // muessen wir die Nachfolger aendern, wenn s != 0 ?
310      DEBOUTLN(cout, "simpleextension: g= ", g);
311      if ( s != 0 ) DEBOUTLN(cout, "simpleextension: s= ", s);
312      else DEBOUTLN(cout, "simpleextension: s= ", s);
313      DEBOUTLN(cout, "simpleextension: R= ", R);
314      Returnlist.insert(s);
315    }
316  }
317
318  return Returnlist;
319}
320
321// the heart of the algorithm: the one from Trager
322static CFFList
323alg_factor( const CanonicalForm & f, const CFList & Astar, const Variable & vminpoly, const Varlist & oldord, const CFList & as){
324  CFFList L, Factorlist;
325  CanonicalForm R, Rstar, s, g, h;
326  CFList substlist;
327
328  DEBINCLEVEL(cout,"alg_factor");
329  substlist= simpleextension(Astar, vminpoly, Rstar);
330  DEBOUTLN(cout, "alg_factor: substlist= ", substlist);
331  DEBOUTLN(cout, "alg_factor: minpoly Rstar= ", Rstar); 
332 
333  sqrf_norm(f, Rstar, vminpoly, s, g, R );
334  DEBOUTLN(cout, "alg_factor: g= ", g);
335  DEBOUTLN(cout, "alg_factor: s= ", s);
336  DEBOUTLN(cout, "alg_factor: R= ", R);
337  Off(SW_RATIONAL);
338  Factorlist = Factorize(R); 
339  On(SW_RATIONAL);
340  DEBOUTLN(cout, "alg_factor: Factorize(R)= ", Factorlist);
341  if ( Factorlist.length() == 2 && Factorlist.getLast().exp()== 1){ // irreduzibel (first entry is a constant)
342    L.append(CFFactor(f,1));
343  }
344  else{
345    DEBOUTLN(cout, "alg_factor: g= ", g);
346    CanonicalForm gnew= g(s,s.mvar());
347    DEBOUTLN(cout, "alg_factor: gnew= ", gnew);
348    g=gnew;
349    for ( CFFListIterator i=Factorlist; i.hasItem(); i++){
350      CanonicalForm fnew=i.getItem().factor();
351      fnew= fnew(s,s.mvar());
352      DEBOUTLN(cout, "alg_factor: fnew= ", fnew);
353      DEBOUTLN(cout, "alg_factor: substlist= ", substlist);
354      for ( CFListIterator ii=substlist; ii.hasItem(); ii++){
355        DEBOUTLN(cout, "alg_factor: item= ", ii.getItem());
356        fnew= fnew(ii.getItem(), ii.getItem().mvar());
357        DEBOUTLN(cout, "alg_factor: fnew= ", fnew);
358      }
359      if (degree(i.getItem().factor()) > 0 ){
360        // undo linear transformation!!!! and then gcd!
361        //cout << "algcd(" << g << "," << i.getItem().factor()(s,s.mvar()) << ",as" << as << ")" << endl;
362        h= algcd(g,fnew, as, oldord);
363        DEBOUTLN(cout, "  alg_factor: h= ", h);
364        DEBOUTLN(cout, "  alg_factor: oldord= ", oldord);
365        if ( degree(h) > 0 ){ //otherwise it's a constant
366          g= divide(g, h,as);
367          DEBOUTLN(cout, "alg_factor: g/h= ", g);
368          DEBOUTLN(cout, "alg_factor: s= ", s);
369          DEBOUTLN(cout, "alg_factor: substlist= ", substlist);
370          L.append(CFFactor(h,1));
371        }
372      }
373    }
374    // we are not interested in a
375    // constant (over K_r, which can be a polynomial!)
376    if (degree(g, f.mvar())>0){ L.append(CFFactor(g,1)); }
377  }
378  DEBOUTLN(cout, "alg_factor: L= ", L);
379  DEBDECLEVEL(cout,"alg_factor");
380  return L;
381}
382
383static CFFList
384endler( const CanonicalForm & f, const CFList & AS, const Varlist & uord ){
385  CanonicalForm F=f, g, q,r;
386  CFFList Output;
387  CFList One, Two, asnew, as=AS;
388  CFListIterator i,ii;
389  VarlistIterator j;
390  Variable vg;
391 
392  for (i=as; i.hasItem(); i++){
393    g= i.getItem();
394    if (g.deriv() == 0 ){
395      DEBOUTLN(cout, "Inseperable extension detected: ", g);
396      for (j=uord; j.hasItem(); j++){
397        if ( degree(g,j.getItem()) > 0 ) vg= j.getItem();
398      }
399      // Now we have the highest transzendental in vg;
400      DEBOUTLN(cout, "Transzendental is ", vg);
401      CanonicalForm gg=-1*g[0];
402      divrem(gg,vg,q,r); r= gg-q*vg;   gg= gg-r;
403      //DEBOUTLN(cout, "q= ", q); DEBOUTLN(cout, "r= ", r);
404      DEBOUTLN(cout, "  that is ", gg);
405      DEBOUTLN(cout, "  maps to ", g+gg);
406      One.insert(gg); Two.insert(g+gg);
407      // Now transform all remaining polys in as:
408      int x=0;
409      for (ii=i; ii.hasItem(); ii++){
410        if ( x != 0 ){
411          divrem(ii.getItem(), gg, q,r);
412//        cout << ii.getItem() << " divided by " << gg << endl;
413          DEBOUTLN(cout, "q= ", q); DEBOUTLN(cout, "r= ", r);
414          ii.append(ii.getItem()+q*g); ii.remove(1);
415          DEBOUTLN(cout, "as= ", as);
416        }
417        x+= 1;
418      }
419      // Now transform F:
420      divrem(F, gg, q,r);
421      F= F+q*g; 
422      DEBOUTLN(cout, "new F= ", F);
423    }
424    else{ asnew.append(i.getItem());  }// just the identity
425  }
426  // factor F with minimal polys given in asnew:
427  DEBOUTLN(cout, "Factor F=  ", F);
428  DEBOUTLN(cout, "  with as= ", asnew);
429  int success=0;
430  CFFList factorlist= newcfactor(F,asnew, success);
431  DEBOUTLN(cout, "  gives =  ", factorlist);
432  DEBOUTLN(cout, "One= ", One);
433  DEBOUTLN(cout, "Two= ", Two);
434
435  // Transform back:
436  for ( CFFListIterator k=factorlist; k.hasItem(); k++){
437    CanonicalForm factor= k.getItem().factor();
438    ii=One;
439    for (i=Two; i.hasItem(); i++){
440      DEBOUTLN(cout, "Mapping ", i.getItem());
441      DEBOUTLN(cout, "     to ", ii.getItem());
442      DEBOUTLN(cout, "     in ", factor);
443      divrem(factor,i.getItem(),q,r); r=factor -q*i.getItem();
444      DEBOUTLN(cout, "q= ", q); DEBOUTLN(cout, "r= ", r);
445      factor= ii.getItem()*q +r; //
446      ii++;
447    }
448    Output.append(CFFactor(factor,k.getItem().exp()));
449  }
450
451  return Output;
452}
453
454
455// 1) prepares data
456// 2) for char=p we distinguish 3 cases:
457//           no transcendentals, seperable and inseperable extensions
458CFFList
459newfactoras( const CanonicalForm & f, const CFList & as, int success){
460  Variable vf=f.mvar();
461  CFListIterator i;
462  CFFListIterator jj;
463  CFList reduceresult;
464  CFFList result;
465 
466  success=1;
467  DEBINCLEVEL(cout, "newfactoras");
468  DEBOUTMSG(cerr, rcsid);
469  DEBOUTLN(cout, "newfactoras called with f= ", f);
470  DEBOUTLN(cout, "               content(f)= ", content(f));
471  DEBOUTLN(cout, "                       as= ", as);
472  DEBOUTLN(cout, "newfactoras: cls(vf)= ", cls(vf));
473  DEBOUTLN(cout, "newfactoras: cls(as.getLast())= ", cls(as.getLast()));
474  DEBOUTLN(cout, "newfactoras: degree(f,vf)= ", degree(f,vf));
475
476// F1: [Test trivial cases]
477// 1) first trivial cases:
478  if ( (cls(vf) <= cls(as.getLast())) ||  degree(f,vf)<=1 ){
479// ||( (as.length()==1) && (degree(f,vf)==3) && (degree(as.getFirst()==2)) )
480    DEBDECLEVEL(cout,"newfactoras"); 
481    return CFFList(CFFactor(f,1));
482  }
483
484// 2) List of variables:
485// 2a) Setup list of those polys in AS having degree(AS[i], AS[i].mvar()) > 1
486// 2b) Setup variableordering
487  CFList Astar;
488  Variable x;
489  CanonicalForm elem;
490  Varlist ord, uord,oldord;
491  for ( int ii=1; ii< level(vf) ; ii++ ) { uord.append(Variable(ii));  }
492  oldord= uord; oldord.append(vf);
493
494  for ( i=as; i.hasItem(); i++ ){
495    elem= i.getItem();
496    x= elem.mvar();
497    if ( degree(elem,x) > 1){ // otherwise it's not an extension
498      //if ( degree(f,x) > 0 ){ // does it occure in f? RICHTIG?
499        Astar.append(elem);
500        ord.append(x);
501        //}
502    }
503  }
504  uord= Difference(uord,ord);
505  DEBOUTLN(cout, "Astar is: ", Astar);
506  DEBOUTLN(cout, "ord is: ", ord);
507  DEBOUTLN(cout, "uord is: ", uord);
508
509// 3) second trivial cases: we already prooved irr. of f over no extensions
510  if ( Astar.length() == 0 ){ 
511    DEBDECLEVEL(cout,"newfactoras"); 
512    return CFFList(CFFactor(f,1)); 
513  }
514
515// 4) Try to obtain a partial factorization using prop2 and prop3
516//    Use with caution! We have to proof these propositions first!
517  // Not yet implemented
518
519// 5) Look if elements in uord actually occure in any of the minimal
520//    polynomials. If no element of uord occures in any of the minimal
521//   polynomials, we don't have transzendentals.
522  Varlist newuord=Var_is_in_AS(uord,Astar);
523  DEBOUTLN(cout, "newuord is: ", newuord);
524
525  CFFList Factorlist;
526  Varlist gcdord= Union(ord,newuord); gcdord.append(f.mvar());
527  // This is for now. we need alg_sqrfree implemented!
528  CanonicalForm Fgcd= algcd(f,f.deriv(),Astar,gcdord);
529  if ( Fgcd == 0 ) DEBOUTMSG(cerr, "WARNING: p'th root ?");
530  if ( degree(Fgcd, f.mvar()) > 0 ){
531    DEBOUTLN(cout, "Nontrivial GCD found of ", f);
532    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
533    DEBOUTLN(cout, "  split into ", Fgcd);
534    DEBOUTLN(cout, "         and ", Ggcd);
535    Fgcd= pp(Fgcd); Ggcd= pp(Ggcd);
536    DEBDECLEVEL(cout,"newfactoras");
537    return myUnion(newfactoras(Fgcd,as,success) , newfactoras(Ggcd,as,success));
538  }
539  if ( getCharacteristic() > 0 ){
540
541    // First look for extension!
542    IntList degreelist;
543    Variable vminpoly;
544    for (i=Astar; i.hasItem(); i++){degreelist.append(degree(i.getItem()));}
545    int extdeg= getextension(degreelist, degree(f));
546    DEBOUTLN(cout, "Extension needed of degree ", extdeg);
547
548    // Now the real stuff!
549    if ( newuord.length() == 0 ){ // no transzendentals
550      DEBOUTMSG(cout, "No transzendentals!");
551      if ( extdeg > 1 ){
552        CanonicalForm MIPO= generate_mipo( extdeg, vminpoly);
553        DEBOUTLN(cout, "Minpoly produced ", MIPO);
554        vminpoly= rootOf(MIPO);
555      }
556      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
557      DEBDECLEVEL(cout,"newfactoras");
558      return Factorlist;
559    }
560    else if ( inseperable(Astar) > 0 ){ // Look if extensions are seperable
561      // a) Use Endler
562      DEBOUTMSG(cout, "Inseperable extensions! Using Endler!");
563      CFFList templist= endler(f,Astar, newuord);
564      DEBOUTLN(cout, "Endler gives: ", templist);
565      return templist;
566    }
567    else{ // we are on the save side: Use trager
568      DEBOUTMSG(cout, "Only seperable extensions!");
569      if (extdeg > 1 ){
570        CanonicalForm MIPO=generate_mipo(extdeg, vminpoly );
571        vminpoly= rootOf(MIPO);
572        DEBOUTLN(cout, "Minpoly generated: ", MIPO);
573        DEBOUTLN(cout, "vminpoly= ", vminpoly);
574        DEBOUTLN(cout, "degree(vminpoly)= ", degree(vminpoly));
575      }
576      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
577      DEBDECLEVEL(cout,"newfactoras");
578      return Factorlist;
579      ;
580    }
581  }
582  else{ // char=0 apply trager directly
583    DEBOUTMSG(cout, "Char=0! Apply Trager!");
584    Variable vminpoly;
585    Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
586      DEBDECLEVEL(cout,"newfactoras");
587      return Factorlist;
588    ;
589  }
590
591  DEBDECLEVEL(cout,"newfactoras"); 
592  return CFFList(CFFactor(f,1)); 
593}
594
595CFFList
596newcfactor(const CanonicalForm & f, const CFList & as, int success ){
597  Off(SW_RATIONAL);
598  CFFList Output, output, Factors=Factorize(f); On(SW_RATIONAL);
599  Factors.removeFirst();
600
601  if ( as.length() == 0 ){ success=1; return Factors;}
602  if ( cls(f) <= cls(as.getLast()) ) { success=1; return Factors;}
603
604  success=1;
605  for ( CFFListIterator i=Factors; i.hasItem(); i++ ){
606    output=newfactoras(i.getItem().factor(),as, success);
607    for ( CFFListIterator j=output; j.hasItem(); j++)
608      Output = myappend(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp()));
609  }
610  return Output;
611}
612
613/*
614$Log: not supported by cvs2svn $
615*/
616
Note: See TracBrowser for help on using the repository browser.