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