source: git/factory/libfac/charset/alg_factor.cc @ 688504

fieker-DuValspielwiese
Last change on this file since 688504 was 688504, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: deleted unused mypsr
  • Property mode set to 100644
File size: 23.2 KB
Line 
1////////////////////////////////////////////////////////////
2// emacs edit mode for this file is -*- C++ -*-
3////////////////////////////////////////////////////////////
4
5// FACTORY - Includes
6#include <factory.h>
7// Factor - Includes
8#include <tmpl_inst.h>
9#include <Factor.h>
10#include <SqrFree.h>
11#include <helpstuff.h>
12// Charset - Includes
13#include "csutil.h"
14#include "charset.h"
15#include "reorder.h"
16#include "algfactor.h"
17// some CC's need this:
18#include "alg_factor.h"
19
20void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
21
22#ifdef ALGFACTORDEBUG
23#  define DEBUGOUTPUT
24#else
25#  undef DEBUGOUTPUT
26#endif
27
28#include <libfac/factor/debug.h>
29
30static Varlist
31Var_is_in_AS(const Varlist & uord, const CFList & Astar);
32
33int getAlgVar(const CanonicalForm &f, Variable &X)
34{
35  if (f.inBaseDomain()) return 0;
36  if (f.inCoeffDomain())
37  {
38    if (f.level()!=0)
39    {
40      X= f.mvar();
41      return 1;
42    }
43    return getAlgVar(f.LC(),X);
44  }
45  if (f.inPolyDomain())
46  {
47    if (getAlgVar(f.LC(),X)) return 1;
48    for( CFIterator i=f; i.hasTerms(); i++)
49    {
50      if (getAlgVar(i.coeff(),X)) return 1;
51    }
52  }
53  return 0;
54}
55
56////////////////////////////////////////////////////////////////////////
57// This implements the algorithm of Trager for factorization of
58// (multivariate) polynomials over algebraic extensions and so called
59// function field extensions.
60////////////////////////////////////////////////////////////////////////
61
62// // missing class: IntGenerator:
63bool IntGenerator::hasItems() const
64{
65    return 1;
66}
67
68CanonicalForm IntGenerator::item() const
69//int IntGenerator::item() const
70{
71  //return current; //CanonicalForm( current );
72  return mapinto(CanonicalForm( current ));
73}
74
75void IntGenerator::next()
76{
77    current++;
78}
79
80// replacement for factory's broken resultant
81static CanonicalForm
82resultante( const CanonicalForm & f, const CanonicalForm& g, const Variable & v )
83{
84  bool on_rational = isOn(SW_RATIONAL);
85  On(SW_RATIONAL);
86  CanonicalForm cd = bCommonDen( f );
87  CanonicalForm fz = f * cd;
88  cd = bCommonDen( g );
89  CanonicalForm gz = g * cd;
90  if (!on_rational)  Off(SW_RATIONAL);
91
92  return resultant(fz,gz,v);
93}
94
95// sqr-free routine for algebraic extensions
96// we need it! Ex.: f=c^2+2*a*c-1; as=[a^2+1]; f=(c+a)^2
97//static CFFList alg_sqrfree( const CanonicalForm & f )
98//{
99//  CFFList L;
100//
101//  L.append(CFFactor(f,1));
102//  return L;
103//}
104
105// Calculates a square free norm
106// Input: f(x, alpha) a square free polynomial over K(alpha),
107// alpha is defined by the minimal polynomial Palpha
108// K has more than S elements (S is defined in thesis; look getextension)
109static void
110sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
111           CFGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
112           CanonicalForm & R)
113{
114  Variable y=PPalpha.mvar(),vf=f.mvar();
115  CanonicalForm temp, Palpha=PPalpha, t;
116  int sqfreetest=0;
117  CFFList testlist;
118  CFFListIterator i;
119
120  DEBOUTLN(CERR, "sqrf_norm_sub:      f= ", f);
121  DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
122  myrandom.reset();   s=f.mvar()-myrandom.item()*Palpha.mvar();   g=f;
123  R= CanonicalForm(0);
124  DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s);
125
126  // Norm, resultante taken with respect to y
127  while ( !sqfreetest )
128  {
129    DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
130    R = resultante(Palpha, g, y); R= R* bCommonDen(R);
131    DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R);
132    // sqfree check ; R is a polynomial in K[x]
133    if ( getCharacteristic() == 0 )
134    {
135      temp= gcd(R, R.deriv(vf));
136      DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp);
137      if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; }
138      else { sqfreetest= 1; }
139      DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest);
140    }
141    else
142    {
143      DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!");
144      // Look at SqrFreeTest!
145      // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 !
146      // for now we use this workaround with Factorize...
147      // ...but it should go away soon!!!!
148      Variable X;
149      if (getAlgVar(R,X))
150      {
151          testlist=factorize( R, X );
152      }
153      else
154        testlist= Factorize(R);
155      DEBOUTLN(CERR, "testlist= ", testlist);
156      testlist.removeFirst();
157      sqfreetest=1;
158      for ( i=testlist; i.hasItem(); i++)
159        if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0) { sqfreetest=0; break; }
160      DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest);
161    }
162    if ( ! sqfreetest )
163    {
164      myrandom.next();
165      DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item());
166      if ( getCharacteristic() == 0 ) t= CanonicalForm(mapinto(myrandom.item()));
167      else t= CanonicalForm(myrandom.item());
168      s= f.mvar()+t*Palpha.mvar(); // s defines backsubstitution
169      DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s);
170      g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
171      DEBOUTLN(CERR, "             gives g= ", g);
172    }
173  }
174}
175static void
176sqrf_agnorm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
177           AlgExtGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
178           CanonicalForm & R)
179{
180  Variable y=PPalpha.mvar(),vf=f.mvar();
181  CanonicalForm temp, Palpha=PPalpha, t;
182  int sqfreetest=0;
183  CFFList testlist;
184  CFFListIterator i;
185
186  DEBOUTLN(CERR, "sqrf_norm_sub:      f= ", f);
187  DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
188  myrandom.reset();   s=f.mvar()-myrandom.item()*Palpha.mvar();   g=f;
189  R= CanonicalForm(0);
190  DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s);
191
192  // Norm, resultante taken with respect to y
193  while ( !sqfreetest )
194  {
195    DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
196    R = resultante(Palpha, g, y); R= R* bCommonDen(R);
197    DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R);
198    // sqfree check ; R is a polynomial in K[x]
199    if ( getCharacteristic() == 0 )
200    {
201      temp= gcd(R, R.deriv(vf));
202      DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp);
203      if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; }
204      else { sqfreetest= 1; }
205      DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest);
206    }
207    else
208    {
209      DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!");
210      // Look at SqrFreeTest!
211      // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 !
212      // for now we use this workaround with Factorize...
213      // ...but it should go away soon!!!!
214      Variable X;
215      if (getAlgVar(R,X))
216      {
217          testlist=factorize( R, X );
218      }
219      else
220        testlist= Factorize(R);
221      DEBOUTLN(CERR, "testlist= ", testlist);
222      testlist.removeFirst();
223      sqfreetest=1;
224      for ( i=testlist; i.hasItem(); i++)
225        if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0) { sqfreetest=0; break; }
226      DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest);
227    }
228    if ( ! sqfreetest )
229    {
230      myrandom.next();
231      DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item());
232      if ( getCharacteristic() == 0 ) t= CanonicalForm(mapinto(myrandom.item()));
233      else t= CanonicalForm(myrandom.item());
234      s= f.mvar()+t*Palpha.mvar(); // s defines backsubstitution
235      DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s);
236      g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
237      DEBOUTLN(CERR, "             gives g= ", g);
238    }
239  }
240}
241
242static void
243sqrf_norm( const CanonicalForm & f, const CanonicalForm & PPalpha,
244           const Variable & Extension, CanonicalForm & s,  CanonicalForm & g,
245           CanonicalForm & R)
246{
247  DEBOUTLN(CERR, "sqrf_norm:      f= ", f);
248  DEBOUTLN(CERR, "sqrf_norm: Palpha= ", PPalpha);
249  if ( getCharacteristic() == 0 )
250  {
251    IntGenerator myrandom;
252    DEBOUTMSG(CERR, "sqrf_norm: no extension, char=0");
253    sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
254    DEBOUTLN(CERR, "sqrf_norm:      f= ", f);
255    DEBOUTLN(CERR, "sqrf_norm: Palpha= ", PPalpha);
256    DEBOUTLN(CERR, "sqrf_norm:      s= ", s);
257    DEBOUTLN(CERR, "sqrf_norm:      g= ", g);
258    DEBOUTLN(CERR, "sqrf_norm:      R= ", R);
259  }
260  else if ( degree(Extension) > 0 ) // working over Extensions
261  {
262    DEBOUTLN(CERR, "sqrf_norm: degree of extension is ", degree(Extension));
263    AlgExtGenerator myrandom(Extension);
264    sqrf_agnorm_sub(f,PPalpha, myrandom, s,g,R);
265  }
266  else
267  {
268    FFGenerator myrandom;
269    DEBOUTMSG(CERR, "sqrf_norm: degree of extension is 0");
270    sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
271  }
272}
273
274static Varlist
275Var_is_in_AS(const Varlist & uord, const CFList & Astar){
276  Varlist output;
277  CanonicalForm elem;
278  Variable x;
279
280  for ( VarlistIterator i=uord; i.hasItem(); i++)
281  {
282    x=i.getItem();
283    for ( CFListIterator j=Astar; j.hasItem(); j++ )
284    {
285      elem= j.getItem();
286      if ( degree(elem,x) > 0 ) // x actually occures in Astar
287      {
288        output.append(x);
289        break;
290      }
291    }
292  }
293  return output;
294}
295
296// Look if Minimalpolynomials in Astar define seperable Extensions
297// Must be a power of p: i.e. y^{p^e}-x
298static int
299inseperable(const CFList & Astar)
300{
301  CanonicalForm elem;
302  int Counter= 1;
303
304  if ( Astar.length() == 0 ) return 0;
305  for ( CFListIterator i=Astar; i.hasItem(); i++)
306  {
307    elem= i.getItem();
308    if ( elem.deriv() == elem.genZero() ) return Counter;
309    else Counter += 1;
310  }
311  return 0;
312}
313
314// calculate gcd of f and g in char=0
315static CanonicalForm
316gcd0( CanonicalForm f, CanonicalForm g )
317{
318  int charac= getCharacteristic();
319  int save=isOn(SW_RATIONAL);
320  setCharacteristic(0); Off(SW_RATIONAL);
321  CanonicalForm ff= mapinto(f), gg= mapinto(g);
322  CanonicalForm result= gcd(ff,gg);
323  setCharacteristic(charac);
324  if (save) On(SW_RATIONAL);
325  return mapinto(result);
326}
327
328// calculate big enough extension for finite fields
329// Idea: first calculate k, such that q^k > S (->thesis, -> getextension)
330// Second, search k with gcd(k,m_i)=1, where m_i is the degree of the i'th
331// minimal polynomial. Then the minpoly f_i remains irrd. over q^k and we
332// have enough elements to plug in.
333static int
334getextension( IntList & degreelist, int n)
335{
336  int charac= getCharacteristic();
337  setCharacteristic(0); // need it for k !
338  int k=1, m=1, length=degreelist.length();
339  IntListIterator i;
340
341  for (i=degreelist; i.hasItem(); i++) m= m*i.getItem();
342  int q=charac;
343  while (q <= ((n*m)*(n*m)/2)) { k= k+1; q= q*charac;}
344  int l=0;
345  do {
346    for (i=degreelist; i.hasItem(); i++){
347      l= l+1;
348      if ( gcd0(k,i.getItem()) == 1){
349        DEBOUTLN(CERR, "getextension: gcd == 1, l=",l);
350        if ( l==length ){ setCharacteristic(charac);  return k; }
351      }
352      else { DEBOUTMSG(CERR, "getextension: Next iteration"); break; }
353    }
354    k= k+1; l=0;
355  }
356  while ( 1 );
357}
358
359// calculate a "primitive element"
360// K must have more than S elements (->thesis, -> getextension)
361static CFList
362simpleextension(const CFList & Astar, const Variable & Extension,
363                CanonicalForm & R){
364  CFList Returnlist, Bstar=Astar;
365  CanonicalForm s, g;
366
367  DEBOUTLN(CERR, "simpleextension: Astar= ", Astar);
368  DEBOUTLN(CERR, "simpleextension:     R= ", R);
369  DEBOUTLN(CERR, "simpleextension: Extension= ", Extension);
370  if ( Astar.length() == 1 ){ R= Astar.getFirst();}
371  else{
372    R=Bstar.getFirst(); Bstar.removeFirst();
373    for ( CFListIterator i=Bstar; i.hasItem(); i++){
374      DEBOUTLN(CERR, "simpleextension: f(x)= ", i.getItem());
375      DEBOUTLN(CERR, "simpleextension: P(x)= ", R);
376      sqrf_norm(i.getItem(), R, Extension, s, g, R);
377      // spielt die Repraesentation eine Rolle?
378      // muessen wir die Nachfolger aendern, wenn s != 0 ?
379      DEBOUTLN(CERR, "simpleextension: g= ", g);
380      if ( s != 0 ) DEBOUTLN(CERR, "simpleextension: s= ", s);
381      else DEBOUTLN(CERR, "simpleextension: s= ", s);
382      DEBOUTLN(CERR, "simpleextension: R= ", R);
383      Returnlist.insert(s);
384    }
385  }
386
387  return Returnlist;
388}
389
390CanonicalForm alg_lc(const CanonicalForm &f)
391{
392  if (f.level()>0)
393  {
394    return alg_lc(f.LC());
395  }
396  //assert(f.inCoeffDomain());
397  return f;
398}
399
400// the heart of the algorithm: the one from Trager
401static CFFList
402alg_factor( const CanonicalForm & f, const CFList & Astar, const Variable & vminpoly, const Varlist & oldord, const CFList & as)
403{
404  CFFList L, Factorlist;
405  CanonicalForm R, Rstar, s, g, h;
406  CFList substlist;
407
408  DEBINCLEVEL(CERR,"alg_factor");
409  DEBOUTLN(CERR, "alg_factor: f= ", f);
410
411  //out_cf("start alg_factor:",f,"\n");
412  substlist= simpleextension(Astar, vminpoly, Rstar);
413  DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
414  DEBOUTLN(CERR, "alg_factor: minpoly Rstar= ", Rstar);
415  DEBOUTLN(CERR, "alg_factor: vminpoly= ", vminpoly);
416
417  sqrf_norm(f, Rstar, vminpoly, s, g, R );
418  //out_cf("sqrf_norm R:",R,"\n");
419  //out_cf("sqrf_norm s:",s,"\n");
420  //out_cf("sqrf_norm g:",g,"\n");
421  DEBOUTLN(CERR, "alg_factor: g= ", g);
422  DEBOUTLN(CERR, "alg_factor: s= ", s);
423  DEBOUTLN(CERR, "alg_factor: R= ", R);
424  Off(SW_RATIONAL);
425  Variable X;
426  if (getAlgVar(R,X))
427  {
428    // factorize R over alg.extension with X
429//CERR << "alg: "<< X << " mipo=" << getMipo(X,Variable('X')) <<"\n";
430    if (R.isUnivariate())
431    {
432      DEBOUTLN(CERR, "alg_factor: factorize( ", R);
433      Factorlist =  factorize( R, X );
434    }
435    else
436    {
437      #if 1
438      Variable XX;
439      CanonicalForm mipo=getMipo(X,XX);
440      CFList as(mipo);
441      DEBOUTLN(CERR, "alg_factor: newfactoras( ", R);
442      int success=1;
443      Factorlist = newfactoras(R, as , success);
444      #else
445      // factor R over k
446      DEBOUTLN(CERR, "alg_factor: Factorize( ", R);
447      Factorlist = Factorize(R);
448      #endif
449    }
450  }
451  else
452  {
453    // factor R over k
454    DEBOUTLN(CERR, "alg_factor: Factorize( ", R);
455    Factorlist = Factorize(R);
456  }
457  On(SW_RATIONAL);
458  DEBOUTLN(CERR, "alg_factor: Factorize(R)= ", Factorlist);
459  if ( !Factorlist.getFirst().factor().inCoeffDomain() )
460    Factorlist.insert(CFFactor(1,1));
461  if ( Factorlist.length() == 2 && Factorlist.getLast().exp()== 1)
462  { // irreduzibel (first entry is a constant)
463    L.append(CFFactor(f,1));
464  }
465  else
466  {
467    DEBOUTLN(CERR, "alg_factor: g= ", g);
468    CanonicalForm gnew= g(s,s.mvar());
469    DEBOUTLN(CERR, "alg_factor: gnew= ", gnew);
470    g=gnew;
471    for ( CFFListIterator i=Factorlist; i.hasItem(); i++)
472    {
473      CanonicalForm fnew=i.getItem().factor();
474      fnew= fnew(s,s.mvar());
475      DEBOUTLN(CERR, "alg_factor: fnew= ", fnew);
476      DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
477      for ( CFListIterator ii=substlist; ii.hasItem(); ii++){
478        DEBOUTLN(CERR, "alg_factor: item= ", ii.getItem());
479        fnew= fnew(ii.getItem(), ii.getItem().mvar());
480        DEBOUTLN(CERR, "alg_factor: fnew= ", fnew);
481      }
482      if (degree(i.getItem().factor()) > 0 )
483      {
484          h=alg_gcd(g,fnew,as);
485        DEBOUTLN(CERR, "  alg_factor: h= ", h);
486        DEBOUTLN(CERR, "  alg_factor: oldord= ", oldord);
487        if ( degree(h) > 0 )
488        { //otherwise it's a constant
489          g= divide(g, h,as);
490          DEBOUTLN(CERR, "alg_factor: g/h= ", g);
491          DEBOUTLN(CERR, "alg_factor: s= ", s);
492          DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
493          //out_cf("new g:",g,"\n");
494          L.append(CFFactor(h,1));
495        }
496        //else printf("degree <=1\n");
497      }
498    }
499    // we are not interested in a
500    // constant (over K_r, which can be a polynomial!)
501    if (degree(g, f.mvar())>0){ L.append(CFFactor(g,1)); }
502  }
503  CFFList LL;
504  if (getCharacteristic()>0)
505  {
506    CFFListIterator i=L;
507    CanonicalForm c_fac=1;
508    CanonicalForm c;
509    for(;i.hasItem(); i++ )
510    {
511      CanonicalForm ff=i.getItem().factor();
512      c=alg_lc(ff);
513      int e=i.getItem().exp();
514      ff/=c;
515      if (!ff.isOne()) LL.append(CFFactor(ff,e));
516      while (e>0) { c_fac*=c;e--; }
517    }
518    if (!c_fac.isOne()) LL.insert(CFFactor(c_fac,1));
519  }
520  else
521  {
522    LL=L;
523  }
524  //CFFListIterator i=LL;
525  //for(;i.hasItem(); i++ )
526  //  out_cf("end alg_f:",i.getItem().factor(),"\n");
527  //printf("end alg_factor\n");
528  DEBOUTLN(CERR, "alg_factor: L= ", LL);
529  DEBDECLEVEL(CERR,"alg_factor");
530  return LL;
531}
532
533static CFFList
534endler( const CanonicalForm & f, const CFList & AS, const Varlist & uord )
535{
536  CanonicalForm F=f, g, q,r;
537  CFFList Output;
538  CFList One, Two, asnew, as=AS;
539  CFListIterator i,ii;
540  VarlistIterator j;
541  Variable vg;
542
543  for (i=as; i.hasItem(); i++)
544  {
545    g= i.getItem();
546    if (g.deriv() == 0 )
547    {
548      DEBOUTLN(CERR, "Inseperable extension detected: ", g);
549      for (j=uord; j.hasItem(); j++)
550      {
551        if ( degree(g,j.getItem()) > 0 ) vg= j.getItem();
552      }
553      // Now we have the highest transzendental in vg;
554      DEBOUTLN(CERR, "Transzendental is ", vg);
555      CanonicalForm gg=-1*g[0];
556      divrem(gg,vg,q,r); r= gg-q*vg;   gg= gg-r;
557      //DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
558      DEBOUTLN(CERR, "  that is ", gg);
559      DEBOUTLN(CERR, "  maps to ", g+gg);
560      One.insert(gg); Two.insert(g+gg);
561      // Now transform all remaining polys in as:
562      int x=0;
563      for (ii=i; ii.hasItem(); ii++)
564      {
565        if ( x != 0 )
566        {
567          divrem(ii.getItem(), gg, q,r);
568//          CERR << ii.getItem() << " divided by " << gg << "\n";
569          DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
570          ii.append(ii.getItem()+q*g); ii.remove(1);
571          DEBOUTLN(CERR, "as= ", as);
572        }
573        x+= 1;
574      }
575      // Now transform F:
576      divrem(F, gg, q,r);
577      F= F+q*g;
578      DEBOUTLN(CERR, "new F= ", F);
579    }
580    else{ asnew.append(i.getItem());  }// just the identity
581  }
582  // factor F with minimal polys given in asnew:
583  DEBOUTLN(CERR, "Factor F=  ", F);
584  DEBOUTLN(CERR, "  with as= ", asnew);
585  int success=0;
586  CFFList factorlist= newcfactor(F,asnew, success);
587  DEBOUTLN(CERR, "  gives =  ", factorlist);
588  DEBOUTLN(CERR, "One= ", One);
589  DEBOUTLN(CERR, "Two= ", Two);
590
591  // Transform back:
592  for ( CFFListIterator k=factorlist; k.hasItem(); k++)
593  {
594    CanonicalForm factor= k.getItem().factor();
595    ii=One;
596    for (i=Two; i.hasItem(); i++)
597    {
598      DEBOUTLN(CERR, "Mapping ", i.getItem());
599      DEBOUTLN(CERR, "     to ", ii.getItem());
600      DEBOUTLN(CERR, "     in ", factor);
601      divrem(factor,i.getItem(),q,r); r=factor -q*i.getItem();
602      DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
603      factor= ii.getItem()*q +r; //
604      ii++;
605    }
606    Output.append(CFFactor(factor,k.getItem().exp()));
607  }
608
609  return Output;
610}
611
612
613// 1) prepares data
614// 2) for char=p we distinguish 3 cases:
615//           no transcendentals, seperable and inseperable extensions
616CFFList
617newfactoras( const CanonicalForm & f, const CFList & as, int &success)
618{
619  Variable vf=f.mvar();
620  CFListIterator i;
621  CFFListIterator jj;
622  CFList reduceresult;
623  CFFList result;
624
625  success=1;
626  DEBINCLEVEL(CERR, "newfactoras");
627  DEBOUTLN(CERR, "newfactoras called with f= ", f);
628  DEBOUTLN(CERR, "               content(f)= ", content(f));
629  DEBOUTLN(CERR, "                       as= ", as);
630  DEBOUTLN(CERR, "newfactoras: cls(vf)= ", cls(vf));
631  DEBOUTLN(CERR, "newfactoras: cls(as.getLast())= ", cls(as.getLast()));
632  DEBOUTLN(CERR, "newfactoras: degree(f,vf)= ", degree(f,vf));
633
634// F1: [Test trivial cases]
635// 1) first trivial cases:
636  if ( (cls(vf) <= cls(as.getLast())) ||  degree(f,vf)<=1 ){
637// ||( (as.length()==1) && (degree(f,vf)==3) && (degree(as.getFirst()==2)) )
638    DEBDECLEVEL(CERR,"newfactoras");
639    return CFFList(CFFactor(f,1));
640  }
641
642// 2) List of variables:
643// 2a) Setup list of those polys in AS having degree(AS[i], AS[i].mvar()) > 1
644// 2b) Setup variableordering
645  CFList Astar;
646  Variable x;
647  CanonicalForm elem;
648  Varlist ord, uord,oldord;
649  for ( int ii=1; ii< level(vf) ; ii++ ) { uord.append(Variable(ii));  }
650  oldord= uord; oldord.append(vf);
651
652  for ( i=as; i.hasItem(); i++ ){
653    elem= i.getItem();
654    x= elem.mvar();
655    if ( degree(elem,x) > 1){ // otherwise it's not an extension
656      Astar.append(elem);
657      ord.append(x);
658    }
659  }
660  uord= Difference(uord,ord);
661  DEBOUTLN(CERR, "Astar is: ", Astar);
662  DEBOUTLN(CERR, "ord is: ", ord);
663  DEBOUTLN(CERR, "uord is: ", uord);
664
665// 3) second trivial cases: we already prooved irr. of f over no extensions
666  if ( Astar.length() == 0 ){
667    DEBDECLEVEL(CERR,"newfactoras");
668    return CFFList(CFFactor(f,1));
669  }
670
671// 4) Try to obtain a partial factorization using prop2 and prop3
672//    Use with caution! We have to proof these propositions first!
673  // Not yet implemented
674
675// 5) Look if elements in uord actually occure in any of the minimal
676//    polynomials. If no element of uord occures in any of the minimal
677//   polynomials, we don't have transzendentals.
678  Varlist newuord=Var_is_in_AS(uord,Astar);
679  DEBOUTLN(CERR, "newuord is: ", newuord);
680
681  CFFList Factorlist;
682  Varlist gcdord= Union(ord,newuord); gcdord.append(f.mvar());
683  // This is for now. we need alg_sqrfree implemented!
684  CanonicalForm Fgcd;
685          Fgcd= alg_gcd(f,f.deriv(),Astar);
686  if ( Fgcd == 0 ) DEBOUTMSG(CERR, "WARNING: p'th root ?");
687  if (( degree(Fgcd, f.mvar()) > 0) && (!(f.deriv().isZero())) ){
688    DEBOUTLN(CERR, "Nontrivial GCD found of ", f);
689    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
690    DEBOUTLN(CERR, "  split into ", Fgcd);
691    DEBOUTLN(CERR, "         and ", Ggcd);
692    Fgcd= pp(Fgcd); Ggcd= pp(Ggcd);
693    DEBDECLEVEL(CERR,"newfactoras");
694    return myUnion(newfactoras(Fgcd,as,success) , newfactoras(Ggcd,as,success));
695  }
696  if ( getCharacteristic() > 0 ){
697
698    // First look for extension!
699    IntList degreelist;
700    Variable vminpoly;
701    for (i=Astar; i.hasItem(); i++){degreelist.append(degree(i.getItem()));}
702    int extdeg= getextension(degreelist, degree(f));
703    DEBOUTLN(CERR, "Extension needed of degree ", extdeg);
704
705    // Now the real stuff!
706    if ( newuord.length() == 0 ){ // no transzendentals
707      DEBOUTMSG(CERR, "No transzendentals!");
708      if ( extdeg > 1 ){
709        CanonicalForm MIPO= generate_mipo( extdeg, vminpoly);
710        DEBOUTLN(CERR, "Minpoly produced ", MIPO);
711        vminpoly= rootOf(MIPO);
712      }
713      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
714      DEBDECLEVEL(CERR,"newfactoras");
715      return Factorlist;
716    }
717    else if ( inseperable(Astar) > 0 ){ // Look if extensions are seperable
718      // a) Use Endler
719      DEBOUTMSG(CERR, "Inseperable extensions! Using Endler!");
720      CFFList templist= endler(f,Astar, newuord);
721      DEBOUTLN(CERR, "Endler gives: ", templist);
722      return templist;
723    }
724    else{ // we are on the save side: Use trager
725      DEBOUTMSG(CERR, "Only seperable extensions!");
726      if (extdeg > 1 ){
727        CanonicalForm MIPO=generate_mipo(extdeg, vminpoly );
728        vminpoly= rootOf(MIPO);
729        DEBOUTLN(CERR, "Minpoly generated: ", MIPO);
730        DEBOUTLN(CERR, "vminpoly= ", vminpoly);
731        DEBOUTLN(CERR, "degree(vminpoly)= ", degree(vminpoly));
732      }
733      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
734      DEBDECLEVEL(CERR,"newfactoras");
735      return Factorlist;
736    }
737  }
738  else{ // char=0 apply trager directly
739    DEBOUTMSG(CERR, "Char=0! Apply Trager!");
740    Variable vminpoly;
741    Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
742      DEBDECLEVEL(CERR,"newfactoras");
743      return Factorlist;
744  }
745
746  DEBDECLEVEL(CERR,"newfactoras");
747  return CFFList(CFFactor(f,1));
748}
749
750CFFList
751newcfactor(const CanonicalForm & f, const CFList & as, int & success )
752{
753  Off(SW_RATIONAL);
754  CFFList Output, output, Factors=Factorize(f);
755  On(SW_RATIONAL);
756  Factors.removeFirst();
757
758  if ( as.length() == 0 ){ success=1; return Factors;}
759  if ( cls(f) <= cls(as.getLast()) ) { success=1; return Factors;}
760
761  success=1;
762  for ( CFFListIterator i=Factors; i.hasItem(); i++ )
763  {
764    output=newfactoras(i.getItem().factor(),as, success);
765    for ( CFFListIterator j=output; j.hasItem(); j++)
766      Output = myappend(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp()));
767  }
768  return Output;
769}
Note: See TracBrowser for help on using the repository browser.