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