source: git/libfac/charset/alg_factor.cc @ 9d6bf4

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