source: git/factory/libfac/charset/alg_factor.cc @ 0b618a7

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