source: git/factory/libfac/charset/alg_factor.cc @ 85bcd6

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