[0479e09] | 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 | |
---|
[9b25e7e] | 20 | void out_cf(char *s1,const CanonicalForm &f,char *s2); |
---|
[639047e] | 21 | |
---|
[0479e09] | 22 | #ifdef ALGFACTORDEBUG |
---|
| 23 | # define DEBUGOUTPUT |
---|
| 24 | #else |
---|
| 25 | # undef DEBUGOUTPUT |
---|
| 26 | #endif |
---|
| 27 | |
---|
[d92d71] | 28 | #include <libfac/factor/debug.h> |
---|
[0479e09] | 29 | |
---|
[405ebc] | 30 | static Varlist |
---|
| 31 | Var_is_in_AS(const Varlist & uord, const CFList & Astar); |
---|
| 32 | |
---|
[0be2bc] | 33 | int 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 | |
---|
[0479e09] | 56 | //////////////////////////////////////////////////////////////////////// |
---|
[0be2bc] | 57 | // This implements the algorithm of Trager for factorization of |
---|
| 58 | // (multivariate) polynomials over algebraic extensions and so called |
---|
| 59 | // function field extensions. |
---|
[0479e09] | 60 | //////////////////////////////////////////////////////////////////////// |
---|
| 61 | |
---|
| 62 | // // missing class: IntGenerator: |
---|
| 63 | bool IntGenerator::hasItems() const |
---|
| 64 | { |
---|
| 65 | return 1; |
---|
| 66 | } |
---|
| 67 | |
---|
| 68 | CanonicalForm IntGenerator::item() const |
---|
| 69 | //int IntGenerator::item() const |
---|
| 70 | { |
---|
| 71 | //return current; //CanonicalForm( current ); |
---|
| 72 | return mapinto(CanonicalForm( current )); |
---|
| 73 | } |
---|
| 74 | |
---|
| 75 | void IntGenerator::next() |
---|
| 76 | { |
---|
| 77 | current++; |
---|
| 78 | } |
---|
| 79 | |
---|
| 80 | // replacement for factory's broken psr |
---|
| 81 | static CanonicalForm |
---|
| 82 | mypsr ( 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; |
---|
[e89e56] | 92 | while ( ( dv <= dr ) && ( r != r.genZero()) ){ |
---|
[0479e09] | 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 |
---|
| 105 | static CanonicalForm |
---|
| 106 | resultante( const CanonicalForm & f, const CanonicalForm& g, const Variable & v ){ |
---|
[625105] | 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 | |
---|
| 115 | return resultant(fz,gz,v); |
---|
[0479e09] | 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 |
---|
[01e8874] | 120 | //static CFFList alg_sqrfree( const CanonicalForm & f ) |
---|
| 121 | //{ |
---|
| 122 | // CFFList L; |
---|
| 123 | // |
---|
| 124 | // L.append(CFFactor(f,1)); |
---|
| 125 | // return L; |
---|
| 126 | //} |
---|
[0479e09] | 127 | |
---|
| 128 | // Calculates a square free norm |
---|
[0be2bc] | 129 | // Input: f(x, alpha) a square free polynomial over K(alpha), |
---|
[0479e09] | 130 | // alpha is defined by the minimal polynomial Palpha |
---|
| 131 | // K has more than S elements (S is defined in thesis; look getextension) |
---|
| 132 | static void |
---|
[0be2bc] | 133 | sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha, |
---|
| 134 | CFGenerator & myrandom, CanonicalForm & s, CanonicalForm & g, |
---|
| 135 | CanonicalForm & R){ |
---|
[0479e09] | 136 | Variable y=PPalpha.mvar(),vf=f.mvar(); |
---|
| 137 | CanonicalForm temp, Palpha=PPalpha, t; |
---|
| 138 | int sqfreetest=0; |
---|
| 139 | CFFList testlist; |
---|
| 140 | CFFListIterator i; |
---|
[0be2bc] | 141 | |
---|
[e2ca88] | 142 | DEBOUTLN(CERR, "sqrf_norm_sub: f= ", f); |
---|
| 143 | DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha); |
---|
[0be2bc] | 144 | myrandom.reset(); s=f.mvar()-myrandom.item()*Palpha.mvar(); g=f; |
---|
[0479e09] | 145 | R= CanonicalForm(0); |
---|
[e2ca88] | 146 | DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s); |
---|
[0479e09] | 147 | |
---|
| 148 | // Norm, resultante taken with respect to y |
---|
| 149 | while ( !sqfreetest ){ |
---|
[e2ca88] | 150 | DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha); |
---|
[17ce9d] | 151 | R = resultante(Palpha, g, y); R= R* bCommonDen(R); |
---|
[e2ca88] | 152 | DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R); |
---|
[0479e09] | 153 | // sqfree check ; R is a polynomial in K[x] |
---|
[405ebc] | 154 | if ( getCharacteristic() == 0 ) |
---|
| 155 | { |
---|
[0be2bc] | 156 | temp= gcd(R, R.deriv(vf)); |
---|
[e2ca88] | 157 | DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp); |
---|
[e89e56] | 158 | if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; } |
---|
[0479e09] | 159 | else { sqfreetest= 1; } |
---|
[e2ca88] | 160 | DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest); |
---|
[0479e09] | 161 | } |
---|
[0be2bc] | 162 | else{ |
---|
[e89e56] | 163 | DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!"); |
---|
| 164 | // Look at SqrFreeTest! |
---|
[0479e09] | 165 | // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 ! |
---|
[0be2bc] | 166 | // for now we use this workaround with Factorize... |
---|
[0479e09] | 167 | // ...but it should go away soon!!!! |
---|
[fa8e1c] | 168 | Variable X; |
---|
| 169 | if (getAlgVar(R,X)) |
---|
[9b25e7e] | 170 | { |
---|
[fa8e1c] | 171 | if (R.isUnivariate()) |
---|
[9b25e7e] | 172 | testlist=factorize( R, X ); |
---|
| 173 | else |
---|
[fa8e1c] | 174 | testlist= Factorize(R, X, 0); |
---|
| 175 | } |
---|
[9b25e7e] | 176 | else |
---|
[af221ea] | 177 | testlist= Factorize(R); |
---|
[e2ca88] | 178 | DEBOUTLN(CERR, "testlist= ", testlist); |
---|
[0f2e64] | 179 | testlist.removeFirst(); |
---|
[0479e09] | 180 | sqfreetest=1; |
---|
| 181 | for ( i=testlist; i.hasItem(); i++) |
---|
[0be2bc] | 182 | if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0) { sqfreetest=0; break; } |
---|
[e89e56] | 183 | DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest); |
---|
[0479e09] | 184 | } |
---|
| 185 | if ( ! sqfreetest ){ |
---|
[0be2bc] | 186 | myrandom.next(); |
---|
[e2ca88] | 187 | DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item()); |
---|
[90e403f] | 188 | if ( getCharacteristic() == 0 ) t= CanonicalForm(mapinto(myrandom.item())); |
---|
| 189 | else t= CanonicalForm(myrandom.item()); |
---|
[0479e09] | 190 | s= f.mvar()+t*Palpha.mvar(); // s defines backsubstitution |
---|
[e2ca88] | 191 | DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s); |
---|
[0479e09] | 192 | g= f(f.mvar()-t*Palpha.mvar(), f.mvar()); |
---|
[e2ca88] | 193 | DEBOUTLN(CERR, " gives g= ", g); |
---|
[0479e09] | 194 | } |
---|
| 195 | } |
---|
| 196 | } |
---|
[b96e07] | 197 | static void |
---|
| 198 | sqrf_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 | |
---|
[e2ca88] | 207 | DEBOUTLN(CERR, "sqrf_norm_sub: f= ", f); |
---|
| 208 | DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha); |
---|
[b96e07] | 209 | myrandom.reset(); s=f.mvar()-myrandom.item()*Palpha.mvar(); g=f; |
---|
| 210 | R= CanonicalForm(0); |
---|
[e2ca88] | 211 | DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s); |
---|
[b96e07] | 212 | |
---|
| 213 | // Norm, resultante taken with respect to y |
---|
| 214 | while ( !sqfreetest ){ |
---|
[e2ca88] | 215 | DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha); |
---|
[b96e07] | 216 | R = resultante(Palpha, g, y); R= R* bCommonDen(R); |
---|
[e2ca88] | 217 | DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R); |
---|
[b96e07] | 218 | // sqfree check ; R is a polynomial in K[x] |
---|
| 219 | if ( getCharacteristic() == 0 ) |
---|
| 220 | { |
---|
| 221 | temp= gcd(R, R.deriv(vf)); |
---|
[e2ca88] | 222 | DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp); |
---|
[e89e56] | 223 | if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; } |
---|
[b96e07] | 224 | else { sqfreetest= 1; } |
---|
[e2ca88] | 225 | DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest); |
---|
[b96e07] | 226 | } |
---|
| 227 | else{ |
---|
[e89e56] | 228 | DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!"); |
---|
| 229 | // Look at SqrFreeTest! |
---|
[b96e07] | 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); |
---|
[e2ca88] | 243 | DEBOUTLN(CERR, "testlist= ", testlist); |
---|
[b96e07] | 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; } |
---|
[e89e56] | 248 | DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest); |
---|
[b96e07] | 249 | } |
---|
| 250 | if ( ! sqfreetest ){ |
---|
| 251 | myrandom.next(); |
---|
[e2ca88] | 252 | DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item()); |
---|
[b96e07] | 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 |
---|
[e2ca88] | 256 | DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s); |
---|
[b96e07] | 257 | g= f(f.mvar()-t*Palpha.mvar(), f.mvar()); |
---|
[e2ca88] | 258 | DEBOUTLN(CERR, " gives g= ", g); |
---|
[b96e07] | 259 | } |
---|
| 260 | } |
---|
| 261 | } |
---|
[0479e09] | 262 | |
---|
| 263 | static void |
---|
[0be2bc] | 264 | sqrf_norm( const CanonicalForm & f, const CanonicalForm & PPalpha, |
---|
| 265 | const Variable & Extension, CanonicalForm & s, CanonicalForm & g, |
---|
| 266 | CanonicalForm & R){ |
---|
| 267 | |
---|
[e2ca88] | 268 | DEBOUTLN(CERR, "sqrf_norm: f= ", f); |
---|
| 269 | DEBOUTLN(CERR, "sqrf_norm: Palpha= ", PPalpha); |
---|
[0479e09] | 270 | if ( getCharacteristic() == 0 ) { |
---|
[0be2bc] | 271 | IntGenerator myrandom; |
---|
[e2ca88] | 272 | DEBOUTMSG(CERR, "sqrf_norm: no extension, char=0"); |
---|
[90e403f] | 273 | sqrf_norm_sub(f,PPalpha, myrandom, s,g,R); |
---|
[e2ca88] | 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); |
---|
[0be2bc] | 279 | } |
---|
[0479e09] | 280 | else if ( degree(Extension) > 0 ){ // working over Extensions |
---|
[e2ca88] | 281 | DEBOUTLN(CERR, "sqrf_norm: degree of extension is ", degree(Extension)); |
---|
[90e403f] | 282 | AlgExtGenerator myrandom(Extension); |
---|
[b96e07] | 283 | sqrf_agnorm_sub(f,PPalpha, myrandom, s,g,R); |
---|
[0479e09] | 284 | } |
---|
| 285 | else{ |
---|
[90e403f] | 286 | FFGenerator myrandom; |
---|
[e2ca88] | 287 | DEBOUTMSG(CERR, "sqrf_norm: degree of extension is 0"); |
---|
[90e403f] | 288 | sqrf_norm_sub(f,PPalpha, myrandom, s,g,R); |
---|
[0479e09] | 289 | } |
---|
| 290 | } |
---|
| 291 | |
---|
| 292 | static Varlist |
---|
| 293 | Var_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 |
---|
[0be2bc] | 303 | output.append(x); |
---|
| 304 | break; |
---|
[0479e09] | 305 | } |
---|
| 306 | } |
---|
| 307 | } |
---|
| 308 | return output; |
---|
| 309 | } |
---|
| 310 | |
---|
| 311 | // Look if Minimalpolynomials in Astar define seperable Extensions |
---|
[0be2bc] | 312 | // Must be a power of p: i.e. y^{p^e}-x |
---|
[0479e09] | 313 | static int |
---|
| 314 | inseperable(const CFList & Astar){ |
---|
| 315 | CanonicalForm elem; |
---|
| 316 | int Counter= 1; |
---|
| 317 | |
---|
| 318 | if ( Astar.length() == 0 ) return 0; |
---|
[e89e56] | 319 | for ( CFListIterator i=Astar; i.hasItem(); i++){ |
---|
[0479e09] | 320 | elem= i.getItem(); |
---|
[e89e56] | 321 | if ( elem.deriv() == elem.genZero() ) return Counter; |
---|
[0479e09] | 322 | else Counter += 1; |
---|
| 323 | } |
---|
| 324 | return 0; |
---|
| 325 | } |
---|
| 326 | |
---|
| 327 | // calculate gcd of f and g in char=0 |
---|
| 328 | static CanonicalForm |
---|
| 329 | gcd0( CanonicalForm f, CanonicalForm g ){ |
---|
| 330 | int charac= getCharacteristic(); |
---|
[625105] | 331 | int save=isOn(SW_RATIONAL); |
---|
[0479e09] | 332 | setCharacteristic(0); Off(SW_RATIONAL); |
---|
| 333 | CanonicalForm ff= mapinto(f), gg= mapinto(g); |
---|
| 334 | CanonicalForm result= gcd(ff,gg); |
---|
[625105] | 335 | setCharacteristic(charac); |
---|
| 336 | if (save) On(SW_RATIONAL); |
---|
[0479e09] | 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. |
---|
| 345 | static int |
---|
| 346 | getextension( 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){ |
---|
[e2ca88] | 360 | DEBOUTLN(CERR, "getextension: gcd == 1, l=",l); |
---|
[0be2bc] | 361 | if ( l==length ){ setCharacteristic(charac); return k; } |
---|
[0479e09] | 362 | } |
---|
[e2ca88] | 363 | else { DEBOUTMSG(CERR, "getextension: Next iteration"); break; } |
---|
[0479e09] | 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) |
---|
[0be2bc] | 372 | static CFList |
---|
| 373 | simpleextension(const CFList & Astar, const Variable & Extension, |
---|
| 374 | CanonicalForm & R){ |
---|
[0479e09] | 375 | CFList Returnlist, Bstar=Astar; |
---|
| 376 | CanonicalForm s, g; |
---|
| 377 | |
---|
[e2ca88] | 378 | DEBOUTLN(CERR, "simpleextension: Astar= ", Astar); |
---|
| 379 | DEBOUTLN(CERR, "simpleextension: R= ", R); |
---|
| 380 | DEBOUTLN(CERR, "simpleextension: Extension= ", Extension); |
---|
[0479e09] | 381 | if ( Astar.length() == 1 ){ R= Astar.getFirst();} |
---|
| 382 | else{ |
---|
| 383 | R=Bstar.getFirst(); Bstar.removeFirst(); |
---|
| 384 | for ( CFListIterator i=Bstar; i.hasItem(); i++){ |
---|
[e2ca88] | 385 | DEBOUTLN(CERR, "simpleextension: f(x)= ", i.getItem()); |
---|
| 386 | DEBOUTLN(CERR, "simpleextension: P(x)= ", R); |
---|
[0479e09] | 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 ? |
---|
[e2ca88] | 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); |
---|
[0479e09] | 394 | Returnlist.insert(s); |
---|
| 395 | } |
---|
| 396 | } |
---|
| 397 | |
---|
| 398 | return Returnlist; |
---|
| 399 | } |
---|
| 400 | |
---|
[639047e] | 401 | CanonicalForm alg_lc(const CanonicalForm &f) |
---|
| 402 | { |
---|
| 403 | if (f.level()>0) |
---|
| 404 | { |
---|
| 405 | return alg_lc(f.LC()); |
---|
| 406 | } |
---|
[8c1592] | 407 | //assert(f.inCoeffDomain()); |
---|
[01e8874] | 408 | return f; |
---|
[9b25e7e] | 409 | } |
---|
[639047e] | 410 | |
---|
[0479e09] | 411 | // the heart of the algorithm: the one from Trager |
---|
| 412 | static CFFList |
---|
[38e7b3] | 413 | alg_factor( const CanonicalForm & f, const CFList & Astar, const Variable & vminpoly, const Varlist & oldord, const CFList & as) |
---|
| 414 | { |
---|
[0479e09] | 415 | CFFList L, Factorlist; |
---|
| 416 | CanonicalForm R, Rstar, s, g, h; |
---|
| 417 | CFList substlist; |
---|
| 418 | |
---|
[e2ca88] | 419 | DEBINCLEVEL(CERR,"alg_factor"); |
---|
| 420 | DEBOUTLN(CERR, "alg_factor: f= ", f); |
---|
[38e7b3] | 421 | |
---|
[639047e] | 422 | //out_cf("start alg_factor:",f,"\n"); |
---|
[0479e09] | 423 | substlist= simpleextension(Astar, vminpoly, Rstar); |
---|
[e2ca88] | 424 | DEBOUTLN(CERR, "alg_factor: substlist= ", substlist); |
---|
| 425 | DEBOUTLN(CERR, "alg_factor: minpoly Rstar= ", Rstar); |
---|
| 426 | DEBOUTLN(CERR, "alg_factor: vminpoly= ", vminpoly); |
---|
[0be2bc] | 427 | |
---|
[0479e09] | 428 | sqrf_norm(f, Rstar, vminpoly, s, g, R ); |
---|
[639047e] | 429 | //out_cf("sqrf_norm R:",R,"\n"); |
---|
| 430 | //out_cf("sqrf_norm s:",s,"\n"); |
---|
| 431 | //out_cf("sqrf_norm g:",g,"\n"); |
---|
[e2ca88] | 432 | DEBOUTLN(CERR, "alg_factor: g= ", g); |
---|
| 433 | DEBOUTLN(CERR, "alg_factor: s= ", s); |
---|
| 434 | DEBOUTLN(CERR, "alg_factor: R= ", R); |
---|
[0479e09] | 435 | Off(SW_RATIONAL); |
---|
[0be2bc] | 436 | Variable X; |
---|
| 437 | if (getAlgVar(R,X)) |
---|
| 438 | { |
---|
| 439 | // factorize R over alg.extension with X |
---|
[e2ca88] | 440 | //CERR << "alg: "<< X << " mipo=" << getMipo(X,Variable('X')) <<"\n"; |
---|
[0be2bc] | 441 | if (R.isUnivariate()) |
---|
[9b25e7e] | 442 | { |
---|
[e2ca88] | 443 | DEBOUTLN(CERR, "alg_factor: factorize( ", R); |
---|
[0be2bc] | 444 | Factorlist = factorize( R, X ); |
---|
[9b25e7e] | 445 | } |
---|
[0be2bc] | 446 | else |
---|
| 447 | { |
---|
[b87513c] | 448 | #if 1 |
---|
[0be2bc] | 449 | Variable XX; |
---|
| 450 | CanonicalForm mipo=getMipo(X,XX); |
---|
| 451 | CFList as(mipo); |
---|
[e2ca88] | 452 | DEBOUTLN(CERR, "alg_factor: newfactoras( ", R); |
---|
[adfb22] | 453 | int success=1; |
---|
| 454 | Factorlist = newfactoras(R, as , success); |
---|
[b87513c] | 455 | #else |
---|
| 456 | // factor R over k |
---|
[e2ca88] | 457 | DEBOUTLN(CERR, "alg_factor: Factorize( ", R); |
---|
[b87513c] | 458 | Factorlist = Factorize(R); |
---|
| 459 | #endif |
---|
[0be2bc] | 460 | } |
---|
| 461 | } |
---|
| 462 | else |
---|
| 463 | { |
---|
| 464 | // factor R over k |
---|
[e2ca88] | 465 | DEBOUTLN(CERR, "alg_factor: Factorize( ", R); |
---|
[0be2bc] | 466 | Factorlist = Factorize(R); |
---|
| 467 | } |
---|
[0479e09] | 468 | On(SW_RATIONAL); |
---|
[e2ca88] | 469 | DEBOUTLN(CERR, "alg_factor: Factorize(R)= ", Factorlist); |
---|
[0be2bc] | 470 | if ( !Factorlist.getFirst().factor().inCoeffDomain() ) |
---|
| 471 | Factorlist.insert(CFFactor(1,1)); |
---|
[38e7b3] | 472 | if ( Factorlist.length() == 2 && Factorlist.getLast().exp()== 1) |
---|
| 473 | { // irreduzibel (first entry is a constant) |
---|
[0479e09] | 474 | L.append(CFFactor(f,1)); |
---|
| 475 | } |
---|
[38e7b3] | 476 | else |
---|
| 477 | { |
---|
[e2ca88] | 478 | DEBOUTLN(CERR, "alg_factor: g= ", g); |
---|
[0479e09] | 479 | CanonicalForm gnew= g(s,s.mvar()); |
---|
[e2ca88] | 480 | DEBOUTLN(CERR, "alg_factor: gnew= ", gnew); |
---|
[0479e09] | 481 | g=gnew; |
---|
[38e7b3] | 482 | for ( CFFListIterator i=Factorlist; i.hasItem(); i++) |
---|
| 483 | { |
---|
[0479e09] | 484 | CanonicalForm fnew=i.getItem().factor(); |
---|
| 485 | fnew= fnew(s,s.mvar()); |
---|
[e2ca88] | 486 | DEBOUTLN(CERR, "alg_factor: fnew= ", fnew); |
---|
| 487 | DEBOUTLN(CERR, "alg_factor: substlist= ", substlist); |
---|
[0479e09] | 488 | for ( CFListIterator ii=substlist; ii.hasItem(); ii++){ |
---|
[e2ca88] | 489 | DEBOUTLN(CERR, "alg_factor: item= ", ii.getItem()); |
---|
[0be2bc] | 490 | fnew= fnew(ii.getItem(), ii.getItem().mvar()); |
---|
[e2ca88] | 491 | DEBOUTLN(CERR, "alg_factor: fnew= ", fnew); |
---|
[0479e09] | 492 | } |
---|
[38e7b3] | 493 | if (degree(i.getItem().factor()) > 0 ) |
---|
| 494 | { |
---|
[9b25e7e] | 495 | h=alg_gcd(g,fnew,as); |
---|
[e2ca88] | 496 | DEBOUTLN(CERR, " alg_factor: h= ", h); |
---|
| 497 | DEBOUTLN(CERR, " alg_factor: oldord= ", oldord); |
---|
[38e7b3] | 498 | if ( degree(h) > 0 ) |
---|
| 499 | { //otherwise it's a constant |
---|
[0be2bc] | 500 | g= divide(g, h,as); |
---|
[e2ca88] | 501 | DEBOUTLN(CERR, "alg_factor: g/h= ", g); |
---|
| 502 | DEBOUTLN(CERR, "alg_factor: s= ", s); |
---|
| 503 | DEBOUTLN(CERR, "alg_factor: substlist= ", substlist); |
---|
[38e7b3] | 504 | //out_cf("new g:",g,"\n"); |
---|
[0be2bc] | 505 | L.append(CFFactor(h,1)); |
---|
| 506 | } |
---|
[38e7b3] | 507 | //else printf("degree <=1\n"); |
---|
[0479e09] | 508 | } |
---|
| 509 | } |
---|
[0be2bc] | 510 | // we are not interested in a |
---|
[0479e09] | 511 | // constant (over K_r, which can be a polynomial!) |
---|
| 512 | if (degree(g, f.mvar())>0){ L.append(CFFactor(g,1)); } |
---|
| 513 | } |
---|
[639047e] | 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"); |
---|
[e2ca88] | 539 | DEBOUTLN(CERR, "alg_factor: L= ", LL); |
---|
| 540 | DEBDECLEVEL(CERR,"alg_factor"); |
---|
[639047e] | 541 | return LL; |
---|
[0479e09] | 542 | } |
---|
| 543 | |
---|
| 544 | static CFFList |
---|
| 545 | endler( 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; |
---|
[0be2bc] | 552 | |
---|
[0479e09] | 553 | for (i=as; i.hasItem(); i++){ |
---|
| 554 | g= i.getItem(); |
---|
| 555 | if (g.deriv() == 0 ){ |
---|
[e2ca88] | 556 | DEBOUTLN(CERR, "Inseperable extension detected: ", g); |
---|
[0479e09] | 557 | for (j=uord; j.hasItem(); j++){ |
---|
[0be2bc] | 558 | if ( degree(g,j.getItem()) > 0 ) vg= j.getItem(); |
---|
[0479e09] | 559 | } |
---|
| 560 | // Now we have the highest transzendental in vg; |
---|
[e2ca88] | 561 | DEBOUTLN(CERR, "Transzendental is ", vg); |
---|
[0479e09] | 562 | CanonicalForm gg=-1*g[0]; |
---|
| 563 | divrem(gg,vg,q,r); r= gg-q*vg; gg= gg-r; |
---|
[e2ca88] | 564 | //DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r); |
---|
| 565 | DEBOUTLN(CERR, " that is ", gg); |
---|
| 566 | DEBOUTLN(CERR, " maps to ", g+gg); |
---|
[0479e09] | 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++){ |
---|
[0be2bc] | 571 | if ( x != 0 ){ |
---|
| 572 | divrem(ii.getItem(), gg, q,r); |
---|
[e2ca88] | 573 | // CERR << ii.getItem() << " divided by " << gg << "\n"; |
---|
| 574 | DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r); |
---|
[0be2bc] | 575 | ii.append(ii.getItem()+q*g); ii.remove(1); |
---|
[e2ca88] | 576 | DEBOUTLN(CERR, "as= ", as); |
---|
[0be2bc] | 577 | } |
---|
| 578 | x+= 1; |
---|
[0479e09] | 579 | } |
---|
[0be2bc] | 580 | // Now transform F: |
---|
[0479e09] | 581 | divrem(F, gg, q,r); |
---|
[0be2bc] | 582 | F= F+q*g; |
---|
[e2ca88] | 583 | DEBOUTLN(CERR, "new F= ", F); |
---|
[0479e09] | 584 | } |
---|
| 585 | else{ asnew.append(i.getItem()); }// just the identity |
---|
| 586 | } |
---|
| 587 | // factor F with minimal polys given in asnew: |
---|
[e2ca88] | 588 | DEBOUTLN(CERR, "Factor F= ", F); |
---|
| 589 | DEBOUTLN(CERR, " with as= ", asnew); |
---|
[0479e09] | 590 | int success=0; |
---|
| 591 | CFFList factorlist= newcfactor(F,asnew, success); |
---|
[e2ca88] | 592 | DEBOUTLN(CERR, " gives = ", factorlist); |
---|
| 593 | DEBOUTLN(CERR, "One= ", One); |
---|
| 594 | DEBOUTLN(CERR, "Two= ", Two); |
---|
[0479e09] | 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++){ |
---|
[e2ca88] | 601 | DEBOUTLN(CERR, "Mapping ", i.getItem()); |
---|
| 602 | DEBOUTLN(CERR, " to ", ii.getItem()); |
---|
| 603 | DEBOUTLN(CERR, " in ", factor); |
---|
[0479e09] | 604 | divrem(factor,i.getItem(),q,r); r=factor -q*i.getItem(); |
---|
[e2ca88] | 605 | DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r); |
---|
[0be2bc] | 606 | factor= ii.getItem()*q +r; // |
---|
[0479e09] | 607 | ii++; |
---|
| 608 | } |
---|
| 609 | Output.append(CFFactor(factor,k.getItem().exp())); |
---|
| 610 | } |
---|
| 611 | |
---|
| 612 | return Output; |
---|
| 613 | } |
---|
| 614 | |
---|
| 615 | |
---|
| 616 | // 1) prepares data |
---|
[0be2bc] | 617 | // 2) for char=p we distinguish 3 cases: |
---|
[0479e09] | 618 | // no transcendentals, seperable and inseperable extensions |
---|
| 619 | CFFList |
---|
[ec958b] | 620 | newfactoras( const CanonicalForm & f, const CFList & as, int &success){ |
---|
[0479e09] | 621 | Variable vf=f.mvar(); |
---|
| 622 | CFListIterator i; |
---|
| 623 | CFFListIterator jj; |
---|
| 624 | CFList reduceresult; |
---|
| 625 | CFFList result; |
---|
[0be2bc] | 626 | |
---|
[0479e09] | 627 | success=1; |
---|
[e2ca88] | 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)); |
---|
[0479e09] | 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)) ) |
---|
[e2ca88] | 640 | DEBDECLEVEL(CERR,"newfactoras"); |
---|
[0479e09] | 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 |
---|
[3e27a5] | 658 | Astar.append(elem); |
---|
| 659 | ord.append(x); |
---|
[0479e09] | 660 | } |
---|
| 661 | } |
---|
| 662 | uord= Difference(uord,ord); |
---|
[e2ca88] | 663 | DEBOUTLN(CERR, "Astar is: ", Astar); |
---|
| 664 | DEBOUTLN(CERR, "ord is: ", ord); |
---|
| 665 | DEBOUTLN(CERR, "uord is: ", uord); |
---|
[0479e09] | 666 | |
---|
| 667 | // 3) second trivial cases: we already prooved irr. of f over no extensions |
---|
[0be2bc] | 668 | if ( Astar.length() == 0 ){ |
---|
[e2ca88] | 669 | DEBDECLEVEL(CERR,"newfactoras"); |
---|
[0be2bc] | 670 | return CFFList(CFFactor(f,1)); |
---|
[0479e09] | 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 | |
---|
[0be2bc] | 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 |
---|
[0479e09] | 679 | // polynomials, we don't have transzendentals. |
---|
| 680 | Varlist newuord=Var_is_in_AS(uord,Astar); |
---|
[e2ca88] | 681 | DEBOUTLN(CERR, "newuord is: ", newuord); |
---|
[0479e09] | 682 | |
---|
| 683 | CFFList Factorlist; |
---|
| 684 | Varlist gcdord= Union(ord,newuord); gcdord.append(f.mvar()); |
---|
| 685 | // This is for now. we need alg_sqrfree implemented! |
---|
[639047e] | 686 | CanonicalForm Fgcd; |
---|
[9b25e7e] | 687 | Fgcd= alg_gcd(f,f.deriv(),Astar); |
---|
[e2ca88] | 688 | if ( Fgcd == 0 ) DEBOUTMSG(CERR, "WARNING: p'th root ?"); |
---|
[001a685] | 689 | if (( degree(Fgcd, f.mvar()) > 0) && (!(f.deriv().isZero())) ){ |
---|
[e2ca88] | 690 | DEBOUTLN(CERR, "Nontrivial GCD found of ", f); |
---|
[0479e09] | 691 | CanonicalForm Ggcd= divide(f, Fgcd,Astar); |
---|
[e2ca88] | 692 | DEBOUTLN(CERR, " split into ", Fgcd); |
---|
| 693 | DEBOUTLN(CERR, " and ", Ggcd); |
---|
[0479e09] | 694 | Fgcd= pp(Fgcd); Ggcd= pp(Ggcd); |
---|
[e2ca88] | 695 | DEBDECLEVEL(CERR,"newfactoras"); |
---|
[e89e56] | 696 | return myUnion(newfactoras(Fgcd,as,success) , newfactoras(Ggcd,as,success)); |
---|
[0479e09] | 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)); |
---|
[e2ca88] | 705 | DEBOUTLN(CERR, "Extension needed of degree ", extdeg); |
---|
[0479e09] | 706 | |
---|
| 707 | // Now the real stuff! |
---|
| 708 | if ( newuord.length() == 0 ){ // no transzendentals |
---|
[e2ca88] | 709 | DEBOUTMSG(CERR, "No transzendentals!"); |
---|
[0479e09] | 710 | if ( extdeg > 1 ){ |
---|
[0be2bc] | 711 | CanonicalForm MIPO= generate_mipo( extdeg, vminpoly); |
---|
[e2ca88] | 712 | DEBOUTLN(CERR, "Minpoly produced ", MIPO); |
---|
[0be2bc] | 713 | vminpoly= rootOf(MIPO); |
---|
[0479e09] | 714 | } |
---|
| 715 | Factorlist= alg_factor(f, Astar, vminpoly, oldord, as); |
---|
[e2ca88] | 716 | DEBDECLEVEL(CERR,"newfactoras"); |
---|
[0479e09] | 717 | return Factorlist; |
---|
| 718 | } |
---|
| 719 | else if ( inseperable(Astar) > 0 ){ // Look if extensions are seperable |
---|
[0be2bc] | 720 | // a) Use Endler |
---|
[e2ca88] | 721 | DEBOUTMSG(CERR, "Inseperable extensions! Using Endler!"); |
---|
[0479e09] | 722 | CFFList templist= endler(f,Astar, newuord); |
---|
[e2ca88] | 723 | DEBOUTLN(CERR, "Endler gives: ", templist); |
---|
[0479e09] | 724 | return templist; |
---|
| 725 | } |
---|
| 726 | else{ // we are on the save side: Use trager |
---|
[e2ca88] | 727 | DEBOUTMSG(CERR, "Only seperable extensions!"); |
---|
[0479e09] | 728 | if (extdeg > 1 ){ |
---|
[0be2bc] | 729 | CanonicalForm MIPO=generate_mipo(extdeg, vminpoly ); |
---|
| 730 | vminpoly= rootOf(MIPO); |
---|
[e2ca88] | 731 | DEBOUTLN(CERR, "Minpoly generated: ", MIPO); |
---|
| 732 | DEBOUTLN(CERR, "vminpoly= ", vminpoly); |
---|
| 733 | DEBOUTLN(CERR, "degree(vminpoly)= ", degree(vminpoly)); |
---|
[0479e09] | 734 | } |
---|
| 735 | Factorlist= alg_factor(f, Astar, vminpoly, oldord, as); |
---|
[e2ca88] | 736 | DEBDECLEVEL(CERR,"newfactoras"); |
---|
[0479e09] | 737 | return Factorlist; |
---|
| 738 | } |
---|
| 739 | } |
---|
| 740 | else{ // char=0 apply trager directly |
---|
[e2ca88] | 741 | DEBOUTMSG(CERR, "Char=0! Apply Trager!"); |
---|
[0479e09] | 742 | Variable vminpoly; |
---|
| 743 | Factorlist= alg_factor(f, Astar, vminpoly, oldord, as); |
---|
[e2ca88] | 744 | DEBDECLEVEL(CERR,"newfactoras"); |
---|
[0479e09] | 745 | return Factorlist; |
---|
| 746 | } |
---|
| 747 | |
---|
[e2ca88] | 748 | DEBDECLEVEL(CERR,"newfactoras"); |
---|
[0be2bc] | 749 | return CFFList(CFFactor(f,1)); |
---|
[0479e09] | 750 | } |
---|
| 751 | |
---|
| 752 | CFFList |
---|
[2f573cc] | 753 | newcfactor(const CanonicalForm & f, const CFList & as, int & success ){ |
---|
[0479e09] | 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++) |
---|
[e89e56] | 765 | Output = myappend(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp())); |
---|
[0479e09] | 766 | } |
---|
| 767 | return Output; |
---|
| 768 | } |
---|