[daa556] | 1 | /* Emacs edit mode for this file is -*- C++ -*- */ |
---|
[341696] | 2 | /* $Id$ */ |
---|
[1a776f] | 3 | |
---|
| 4 | //{{{ docu |
---|
| 5 | // |
---|
| 6 | // cf_factor.cc - factorization and square free algorithms. |
---|
| 7 | // |
---|
| 8 | // Used by: fac_multivar.cc, fac_univar.cc, cf_irred.cc |
---|
| 9 | // |
---|
[989079] | 10 | // Header file: cf_algorithm.h |
---|
| 11 | // |
---|
[1a776f] | 12 | //}}} |
---|
[2dd068] | 13 | |
---|
[e4fe2b] | 14 | #include "config.h" |
---|
[ab4548f] | 15 | |
---|
[650f2d8] | 16 | #include "cf_assert.h" |
---|
[8d9226] | 17 | |
---|
[2dd068] | 18 | #include "cf_defs.h" |
---|
| 19 | #include "canonicalform.h" |
---|
| 20 | #include "cf_iter.h" |
---|
| 21 | #include "fac_berlekamp.h" |
---|
| 22 | #include "fac_cantzass.h" |
---|
| 23 | #include "fac_univar.h" |
---|
| 24 | #include "fac_multivar.h" |
---|
| 25 | #include "fac_sqrfree.h" |
---|
[d6c703] | 26 | #include "cf_algorithm.h" |
---|
[7bf145] | 27 | #include "facFqFactorize.h" |
---|
[afd067] | 28 | #include "cf_map.h" |
---|
[7bf145] | 29 | #include "algext.h" |
---|
[59a7ca1] | 30 | #include "facAlgExt.h" |
---|
[fcf7587] | 31 | #include "facFactorize.h" |
---|
| 32 | #include "singext.h" |
---|
[2dd068] | 33 | |
---|
[a99e31] | 34 | #include "int_int.h" |
---|
[cd86ac] | 35 | #ifdef HAVE_NTL |
---|
[a99e31] | 36 | #include "NTLconvert.h" |
---|
| 37 | #endif |
---|
| 38 | |
---|
[daa556] | 39 | #include "cf_gmp.h" |
---|
| 40 | |
---|
[a99e31] | 41 | int getExp(); /* cf_char.cc */ |
---|
| 42 | |
---|
[01e8874] | 43 | //static bool isUnivariateBaseDomain( const CanonicalForm & f ) |
---|
| 44 | //{ |
---|
| 45 | // CFIterator i = f; |
---|
| 46 | // bool ok = i.coeff().inBaseDomain(); |
---|
| 47 | // i++; |
---|
| 48 | // while ( i.hasTerms() && ( ok = ok && i.coeff().inBaseDomain() ) ) i++; |
---|
| 49 | // return ok; |
---|
| 50 | //} |
---|
[2dd068] | 51 | |
---|
[28ffaa] | 52 | void find_exp(const CanonicalForm & f, int * exp_f) |
---|
| 53 | { |
---|
| 54 | if ( ! f.inCoeffDomain() ) |
---|
| 55 | { |
---|
| 56 | int e=f.level(); |
---|
| 57 | CFIterator i = f; |
---|
[7af0e48] | 58 | if (e>=0) |
---|
| 59 | { |
---|
| 60 | if (i.exp() > exp_f[e]) exp_f[e]=i.exp(); |
---|
| 61 | } |
---|
[28ffaa] | 62 | for (; i.hasTerms(); i++ ) |
---|
| 63 | { |
---|
| 64 | find_exp(i.coeff(), exp_f); |
---|
| 65 | } |
---|
| 66 | } |
---|
| 67 | } |
---|
| 68 | |
---|
| 69 | int find_mvar(const CanonicalForm & f) |
---|
| 70 | { |
---|
| 71 | int mv=f.level(); |
---|
| 72 | int *exp_f=new int[mv+1]; |
---|
| 73 | int i; |
---|
| 74 | for(i=mv;i>0;i--) exp_f[i]=0; |
---|
| 75 | find_exp(f,exp_f); |
---|
| 76 | for(i=mv;i>0;i--) |
---|
| 77 | { |
---|
| 78 | if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv])) |
---|
| 79 | { |
---|
| 80 | mv=i; |
---|
| 81 | } |
---|
| 82 | } |
---|
| 83 | delete[] exp_f; |
---|
| 84 | return mv; |
---|
| 85 | } |
---|
| 86 | |
---|
[32c11f] | 87 | #if 0 |
---|
[6f62c3] | 88 | //#ifndef NOSTREAMIO |
---|
[27bb97f] | 89 | void out_cf(const char *s1,const CanonicalForm &f,const char *s2) |
---|
[7af0e48] | 90 | { |
---|
| 91 | printf("%s",s1); |
---|
[1e6de6] | 92 | if (f.isZero()) printf("+0"); |
---|
[b1476d0] | 93 | //else if (! f.inCoeffDomain() ) |
---|
| 94 | else if (! f.inBaseDomain() ) |
---|
[7af0e48] | 95 | { |
---|
| 96 | int l = f.level(); |
---|
| 97 | for ( CFIterator i = f; i.hasTerms(); i++ ) |
---|
| 98 | { |
---|
| 99 | int e=i.exp(); |
---|
[b1476d0] | 100 | if (i.coeff().isOne()) |
---|
| 101 | { |
---|
| 102 | printf("+"); |
---|
[cd86ac] | 103 | if (e==0) printf("1"); |
---|
| 104 | else |
---|
| 105 | { |
---|
| 106 | printf("v(%d)",l); |
---|
| 107 | if (e!=1) printf("^%d",e); |
---|
[b1476d0] | 108 | } |
---|
[cd86ac] | 109 | } |
---|
[b1476d0] | 110 | else |
---|
| 111 | { |
---|
| 112 | out_cf("+(",i.coeff(),")"); |
---|
| 113 | if (e!=0) |
---|
[cd86ac] | 114 | { |
---|
| 115 | printf("*v(%d)",l); |
---|
| 116 | if (e!=1) printf("^%d",e); |
---|
| 117 | } |
---|
| 118 | } |
---|
[7af0e48] | 119 | } |
---|
| 120 | } |
---|
| 121 | else |
---|
| 122 | { |
---|
| 123 | if ( f.isImm() ) |
---|
| 124 | { |
---|
[b1476d0] | 125 | printf("+%d",f.intval()); |
---|
[7af0e48] | 126 | } |
---|
[3fd1ff] | 127 | else |
---|
| 128 | { |
---|
[6f62c3] | 129 | #ifdef NOSTREAMIO |
---|
[3fd1ff] | 130 | if (f.inZ()) |
---|
| 131 | { |
---|
[6d4f42] | 132 | mpz_t m; |
---|
[806c18] | 133 | gmp_numerator(f,m); |
---|
[6d4f42] | 134 | char * str = new char[mpz_sizeinbase( m, 10 ) + 2]; |
---|
| 135 | str = mpz_get_str( str, 10, m ); |
---|
[3fd1ff] | 136 | printf("%s",str); |
---|
| 137 | delete[] str; |
---|
[806c18] | 138 | mpz_clear(m); |
---|
[3fd1ff] | 139 | } |
---|
| 140 | else if (f.inQ()) |
---|
| 141 | { |
---|
[6d4f42] | 142 | mpz_t m; |
---|
[806c18] | 143 | gmp_numerator(f,m); |
---|
[6d4f42] | 144 | char * str = new char[mpz_sizeinbase( m, 10 ) + 2]; |
---|
| 145 | str = mpz_get_str( str, 10, m ); |
---|
[3fd1ff] | 146 | printf("%s/",str); |
---|
| 147 | delete[] str; |
---|
[806c18] | 148 | mpz_clear(m); |
---|
[6d4f42] | 149 | gmp_denominator(f,m); |
---|
| 150 | str = new char[mpz_sizeinbase( m, 10 ) + 2]; |
---|
| 151 | str = mpz_get_str( str, 10, m ); |
---|
[3fd1ff] | 152 | printf("%s",str); |
---|
| 153 | delete[] str; |
---|
[806c18] | 154 | mpz_clear(m); |
---|
[3fd1ff] | 155 | } |
---|
[6f62c3] | 156 | #else |
---|
[a1ab2a] | 157 | std::cout << f; |
---|
[6f62c3] | 158 | #endif |
---|
[3fd1ff] | 159 | } |
---|
[b1476d0] | 160 | //if (f.inZ()) printf("(Z)"); |
---|
| 161 | //else if (f.inQ()) printf("(Q)"); |
---|
| 162 | //else if (f.inFF()) printf("(FF)"); |
---|
| 163 | //else if (f.inPP()) printf("(PP)"); |
---|
| 164 | //else if (f.inGF()) printf("(PP)"); |
---|
| 165 | //else |
---|
| 166 | if (f.inExtension()) printf("E(%d)",f.level()); |
---|
[7af0e48] | 167 | } |
---|
| 168 | printf("%s",s2); |
---|
| 169 | } |
---|
| 170 | void out_cff(CFFList &L) |
---|
| 171 | { |
---|
[01e8874] | 172 | //int n = L.length(); |
---|
[7af0e48] | 173 | CFFListIterator J=L; |
---|
| 174 | int j=0; |
---|
| 175 | for ( ; J.hasItem(); J++, j++ ) |
---|
| 176 | { |
---|
| 177 | printf("F%d",j);out_cf(":",J.getItem().factor()," ^ "); |
---|
| 178 | printf("%d\n", J.getItem().exp()); |
---|
| 179 | } |
---|
| 180 | } |
---|
| 181 | void test_cff(CFFList &L,const CanonicalForm & f) |
---|
| 182 | { |
---|
[01e8874] | 183 | //int n = L.length(); |
---|
[7af0e48] | 184 | CFFListIterator J=L; |
---|
| 185 | CanonicalForm t=1; |
---|
| 186 | int j=0; |
---|
| 187 | if (!(L.getFirst().factor().inCoeffDomain())) |
---|
| 188 | printf("first entry is not const\n"); |
---|
| 189 | for ( ; J.hasItem(); J++, j++ ) |
---|
| 190 | { |
---|
| 191 | CanonicalForm tt=J.getItem().factor(); |
---|
| 192 | if (tt.inCoeffDomain() && (j!=0)) |
---|
| 193 | printf("other entry is const\n"); |
---|
| 194 | j=J.getItem().exp(); |
---|
| 195 | while(j>0) { t*=tt; j--; } |
---|
| 196 | } |
---|
[ceaa04] | 197 | if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");} |
---|
[7af0e48] | 198 | } |
---|
[6f62c3] | 199 | //#endif |
---|
[c6eecb] | 200 | #endif |
---|
[7af0e48] | 201 | |
---|
[6f62c3] | 202 | bool isPurePoly_m(const CanonicalForm & f) |
---|
| 203 | { |
---|
| 204 | if (f.inBaseDomain()) return true; |
---|
| 205 | if (f.level()<0) return false; |
---|
| 206 | for (CFIterator i=f;i.hasTerms();i++) |
---|
| 207 | { |
---|
| 208 | if (!isPurePoly_m(i.coeff())) return false; |
---|
| 209 | } |
---|
| 210 | return true; |
---|
| 211 | } |
---|
[034eec] | 212 | bool isPurePoly(const CanonicalForm & f) |
---|
[7af0e48] | 213 | { |
---|
| 214 | if (f.level()<=0) return false; |
---|
| 215 | for (CFIterator i=f;i.hasTerms();i++) |
---|
| 216 | { |
---|
| 217 | if (!(i.coeff().inBaseDomain())) return false; |
---|
| 218 | } |
---|
| 219 | return true; |
---|
| 220 | } |
---|
| 221 | |
---|
[6f62c3] | 222 | |
---|
[dad0bc5] | 223 | /////////////////////////////////////////////////////////////// |
---|
| 224 | // get_max_degree_Variable returns Variable with // |
---|
| 225 | // highest degree. We assume f is *not* a constant! // |
---|
| 226 | /////////////////////////////////////////////////////////////// |
---|
| 227 | Variable |
---|
| 228 | get_max_degree_Variable(const CanonicalForm & f) |
---|
| 229 | { |
---|
| 230 | ASSERT( ( ! f.inCoeffDomain() ), "no constants" ); |
---|
| 231 | int max=0, maxlevel=0, n=level(f); |
---|
| 232 | for ( int i=1; i<=n; i++ ) |
---|
| 233 | { |
---|
| 234 | if (degree(f,Variable(i)) >= max) |
---|
| 235 | { |
---|
| 236 | max= degree(f,Variable(i)); maxlevel= i; |
---|
| 237 | } |
---|
| 238 | } |
---|
| 239 | return Variable(maxlevel); |
---|
| 240 | } |
---|
| 241 | |
---|
| 242 | /////////////////////////////////////////////////////////////// |
---|
| 243 | // get_Terms: Split the polynomial in the containing terms. // |
---|
| 244 | // getTerms: the real work is done here. // |
---|
| 245 | /////////////////////////////////////////////////////////////// |
---|
| 246 | void |
---|
| 247 | getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result ) |
---|
| 248 | { |
---|
| 249 | if ( getNumVars(f) == 0 ) result.append(f*t); |
---|
| 250 | else{ |
---|
| 251 | Variable x(level(f)); |
---|
| 252 | for ( CFIterator i=f; i.hasTerms(); i++ ) |
---|
| 253 | getTerms( i.coeff(), t*power(x,i.exp()), result); |
---|
| 254 | } |
---|
| 255 | } |
---|
| 256 | CFList |
---|
| 257 | get_Terms( const CanonicalForm & f ){ |
---|
| 258 | CFList result,dummy,dummy2; |
---|
| 259 | CFIterator i; |
---|
| 260 | CFListIterator j; |
---|
| 261 | |
---|
| 262 | if ( getNumVars(f) == 0 ) result.append(f); |
---|
| 263 | else{ |
---|
| 264 | Variable _x(level(f)); |
---|
| 265 | for ( i=f; i.hasTerms(); i++ ){ |
---|
| 266 | getTerms(i.coeff(), 1, dummy); |
---|
| 267 | for ( j=dummy; j.hasItem(); j++ ) |
---|
| 268 | result.append(j.getItem() * power(_x, i.exp())); |
---|
| 269 | |
---|
| 270 | dummy= dummy2; // have to initalize new |
---|
| 271 | } |
---|
| 272 | } |
---|
| 273 | return result; |
---|
| 274 | } |
---|
| 275 | |
---|
| 276 | |
---|
| 277 | /////////////////////////////////////////////////////////////// |
---|
| 278 | // homogenize homogenizes f with Variable x // |
---|
| 279 | /////////////////////////////////////////////////////////////// |
---|
| 280 | |
---|
| 281 | CanonicalForm |
---|
| 282 | homogenize( const CanonicalForm & f, const Variable & x) |
---|
| 283 | { |
---|
| 284 | #if 0 |
---|
| 285 | int maxdeg=totaldegree(f), deg; |
---|
| 286 | CFIterator i; |
---|
[faa6c6] | 287 | CanonicalForm elem, result(0); |
---|
[3fd1ff] | 288 | |
---|
[dad0bc5] | 289 | for (i=f; i.hasTerms(); i++) |
---|
| 290 | { |
---|
| 291 | elem= i.coeff()*power(f.mvar(),i.exp()); |
---|
| 292 | deg = totaldegree(elem); |
---|
| 293 | if ( deg < maxdeg ) |
---|
| 294 | result += elem * power(x,maxdeg-deg); |
---|
[3fd1ff] | 295 | else |
---|
[dad0bc5] | 296 | result+=elem; |
---|
| 297 | } |
---|
| 298 | return result; |
---|
| 299 | #else |
---|
| 300 | CFList Newlist, Termlist= get_Terms(f); |
---|
| 301 | int maxdeg=totaldegree(f), deg; |
---|
| 302 | CFListIterator i; |
---|
[faa6c6] | 303 | CanonicalForm elem, result(0); |
---|
[dad0bc5] | 304 | |
---|
[a38d45] | 305 | for (i=Termlist; i.hasItem(); i++) |
---|
| 306 | { |
---|
[dad0bc5] | 307 | elem= i.getItem(); |
---|
| 308 | deg = totaldegree(elem); |
---|
| 309 | if ( deg < maxdeg ) |
---|
| 310 | Newlist.append(elem * power(x,maxdeg-deg)); |
---|
| 311 | else |
---|
| 312 | Newlist.append(elem); |
---|
| 313 | } |
---|
| 314 | for (i=Newlist; i.hasItem(); i++) // rebuild |
---|
| 315 | result += i.getItem(); |
---|
| 316 | |
---|
| 317 | return result; |
---|
| 318 | #endif |
---|
| 319 | } |
---|
| 320 | |
---|
[a38d45] | 321 | CanonicalForm |
---|
| 322 | homogenize( const CanonicalForm & f, const Variable & x, const Variable & v1, const Variable & v2) |
---|
| 323 | { |
---|
| 324 | #if 0 |
---|
| 325 | int maxdeg=totaldegree(f), deg; |
---|
| 326 | CFIterator i; |
---|
| 327 | CanonicalForm elem, result(0); |
---|
[3fd1ff] | 328 | |
---|
[a38d45] | 329 | for (i=f; i.hasTerms(); i++) |
---|
| 330 | { |
---|
| 331 | elem= i.coeff()*power(f.mvar(),i.exp()); |
---|
| 332 | deg = totaldegree(elem); |
---|
| 333 | if ( deg < maxdeg ) |
---|
| 334 | result += elem * power(x,maxdeg-deg); |
---|
[3fd1ff] | 335 | else |
---|
[a38d45] | 336 | result+=elem; |
---|
| 337 | } |
---|
| 338 | return result; |
---|
| 339 | #else |
---|
| 340 | CFList Newlist, Termlist= get_Terms(f); |
---|
| 341 | int maxdeg=totaldegree(f), deg; |
---|
| 342 | CFListIterator i; |
---|
| 343 | CanonicalForm elem, result(0); |
---|
| 344 | |
---|
| 345 | for (i=Termlist; i.hasItem(); i++) |
---|
| 346 | { |
---|
| 347 | elem= i.getItem(); |
---|
| 348 | deg = totaldegree(elem,v1,v2); |
---|
| 349 | if ( deg < maxdeg ) |
---|
| 350 | Newlist.append(elem * power(x,maxdeg-deg)); |
---|
| 351 | else |
---|
| 352 | Newlist.append(elem); |
---|
| 353 | } |
---|
| 354 | for (i=Newlist; i.hasItem(); i++) // rebuild |
---|
| 355 | result += i.getItem(); |
---|
| 356 | |
---|
| 357 | return result; |
---|
| 358 | #endif |
---|
| 359 | } |
---|
| 360 | |
---|
[fbbb08] | 361 | int singular_homog_flag=1; |
---|
| 362 | |
---|
[0cb22ad] | 363 | int cmpCF( const CFFactor & f, const CFFactor & g ) |
---|
[dad0bc5] | 364 | { |
---|
| 365 | if (f.exp() > g.exp()) return 1; |
---|
| 366 | if (f.exp() < g.exp()) return 0; |
---|
| 367 | if (f.factor() > g.factor()) return 1; |
---|
| 368 | return 0; |
---|
| 369 | } |
---|
| 370 | |
---|
[989079] | 371 | CFFList factorize ( const CanonicalForm & f, bool issqrfree ) |
---|
[2dd068] | 372 | { |
---|
[a99e31] | 373 | if ( f.inCoeffDomain() ) |
---|
[7af0e48] | 374 | return CFFList( f ); |
---|
[a99e31] | 375 | int mv=f.level(); |
---|
[cae0b6] | 376 | int org_v=mv; |
---|
[dad0bc5] | 377 | //out_cf("factorize:",f,"==================================\n"); |
---|
[a99e31] | 378 | if (! f.isUnivariate() ) |
---|
| 379 | { |
---|
[dad0bc5] | 380 | if ( singular_homog_flag && f.isHomogeneous()) |
---|
| 381 | { |
---|
| 382 | Variable xn = get_max_degree_Variable(f); |
---|
| 383 | int d_xn = degree(f,xn); |
---|
| 384 | CFMap n; |
---|
| 385 | CanonicalForm F = compress(f(1,xn),n); |
---|
| 386 | CFFList Intermediatelist; |
---|
| 387 | Intermediatelist = factorize(F); |
---|
| 388 | CFFList Homoglist; |
---|
| 389 | CFFListIterator j; |
---|
| 390 | for ( j=Intermediatelist; j.hasItem(); j++ ) |
---|
| 391 | { |
---|
| 392 | Homoglist.append( |
---|
| 393 | CFFactor( n(j.getItem().factor()), j.getItem().exp()) ); |
---|
| 394 | } |
---|
| 395 | CFFList Unhomoglist; |
---|
| 396 | CanonicalForm unhomogelem; |
---|
| 397 | for ( j=Homoglist; j.hasItem(); j++ ) |
---|
| 398 | { |
---|
| 399 | unhomogelem= homogenize(j.getItem().factor(),xn); |
---|
| 400 | Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp())); |
---|
| 401 | d_xn -= (degree(unhomogelem,xn)*j.getItem().exp()); |
---|
| 402 | } |
---|
| 403 | if ( d_xn != 0 ) // have to append xn^(d_xn) |
---|
[3fd1ff] | 404 | Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn)); |
---|
| 405 | if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF); |
---|
[dad0bc5] | 406 | return Unhomoglist; |
---|
| 407 | } |
---|
[a99e31] | 408 | mv=find_mvar(f); |
---|
[ec989c] | 409 | if ( getCharacteristic() == 0 ) |
---|
[a99e31] | 410 | { |
---|
[cae0b6] | 411 | if (mv!=f.level()) |
---|
| 412 | { |
---|
| 413 | swapvar(f,Variable(mv),f.mvar()); |
---|
| 414 | } |
---|
| 415 | } |
---|
| 416 | else |
---|
| 417 | { |
---|
| 418 | if (mv!=1) |
---|
| 419 | { |
---|
| 420 | swapvar(f,Variable(mv),Variable(1)); |
---|
| 421 | org_v=1; |
---|
| 422 | } |
---|
[a99e31] | 423 | } |
---|
| 424 | } |
---|
| 425 | CFFList F; |
---|
[7af0e48] | 426 | if ( getCharacteristic() > 0 ) |
---|
[a99e31] | 427 | { |
---|
[7bf145] | 428 | if (f.isUnivariate()) |
---|
[7af0e48] | 429 | { |
---|
[7bf145] | 430 | #ifdef HAVE_NTL |
---|
| 431 | if (isOn(SW_USE_NTL) && (isPurePoly(f))) |
---|
[a99e31] | 432 | { |
---|
[34ceab] | 433 | // USE NTL |
---|
| 434 | if (getCharacteristic()!=2) |
---|
| 435 | { |
---|
| 436 | if (fac_NTL_char!=getCharacteristic()) |
---|
| 437 | { |
---|
| 438 | fac_NTL_char=getCharacteristic(); |
---|
| 439 | #ifndef NTL_ZZ |
---|
| 440 | if (fac_NTL_char >NTL_SP_BOUND) |
---|
| 441 | { |
---|
| 442 | ZZ r; |
---|
| 443 | r=getCharacteristic(); |
---|
| 444 | ZZ_pContext ccc(r); |
---|
| 445 | ccc.restore(); |
---|
| 446 | ZZ_p::init(r); |
---|
| 447 | } |
---|
| 448 | else |
---|
| 449 | #endif |
---|
| 450 | { |
---|
| 451 | #ifdef NTL_ZZ |
---|
| 452 | ZZ r; |
---|
| 453 | r=getCharacteristic(); |
---|
| 454 | ZZ_pContext ccc(r); |
---|
| 455 | #else |
---|
| 456 | zz_pContext ccc(getCharacteristic()); |
---|
| 457 | #endif |
---|
| 458 | ccc.restore(); |
---|
| 459 | #ifdef NTL_ZZ |
---|
| 460 | ZZ_p::init(r); |
---|
| 461 | #else |
---|
| 462 | zz_p::init(getCharacteristic()); |
---|
| 463 | #endif |
---|
| 464 | } |
---|
| 465 | } |
---|
[3b77086] | 466 | #ifndef NTL_ZZ |
---|
| 467 | if (fac_NTL_char >NTL_SP_BOUND) |
---|
| 468 | { |
---|
[34ceab] | 469 | // convert to NTL |
---|
| 470 | ZZ_pX f1=convertFacCF2NTLZZpX(f); |
---|
| 471 | ZZ_p leadcoeff = LeadCoeff(f1); |
---|
| 472 | //make monic |
---|
| 473 | f1=f1 / LeadCoeff(f1); |
---|
| 474 | // factorize |
---|
| 475 | vec_pair_ZZ_pX_long factors; |
---|
| 476 | CanZass(factors,f1); |
---|
| 477 | // convert back to factory |
---|
| 478 | F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar()); |
---|
| 479 | } |
---|
| 480 | else |
---|
| 481 | #endif |
---|
| 482 | { |
---|
| 483 | // convert to NTL |
---|
| 484 | #ifdef NTL_ZZ |
---|
| 485 | ZZ_pX f1=convertFacCF2NTLZZpX(f); |
---|
| 486 | ZZ_p leadcoeff = LeadCoeff(f1); |
---|
| 487 | #else |
---|
| 488 | zz_pX f1=convertFacCF2NTLzzpX(f); |
---|
| 489 | zz_p leadcoeff = LeadCoeff(f1); |
---|
| 490 | #endif |
---|
| 491 | //make monic |
---|
| 492 | f1=f1 / LeadCoeff(f1); |
---|
| 493 | // factorize |
---|
| 494 | #ifdef NTL_ZZ |
---|
| 495 | vec_pair_ZZ_pX_long factors; |
---|
| 496 | #else |
---|
| 497 | vec_pair_zz_pX_long factors; |
---|
| 498 | #endif |
---|
| 499 | CanZass(factors,f1); |
---|
| 500 | // convert back to factory |
---|
| 501 | #ifdef NTL_ZZ |
---|
| 502 | F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar()); |
---|
| 503 | #else |
---|
| 504 | F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar()); |
---|
| 505 | #endif |
---|
| 506 | } |
---|
| 507 | //test_cff(F,f); |
---|
| 508 | } |
---|
[3b77086] | 509 | else /*getCharacteristic()==2*/ |
---|
[34ceab] | 510 | { |
---|
| 511 | // Specialcase characteristic==2 |
---|
| 512 | if (fac_NTL_char!=2) |
---|
| 513 | { |
---|
| 514 | fac_NTL_char=2; |
---|
| 515 | zz_p::init(2); |
---|
| 516 | } |
---|
| 517 | // convert to NTL using the faster conversion routine for characteristic 2 |
---|
| 518 | GF2X f1=convertFacCF2NTLGF2X(f); |
---|
| 519 | // no make monic necessary in GF2 |
---|
| 520 | //factorize |
---|
| 521 | vec_pair_GF2X_long factors; |
---|
| 522 | CanZass(factors,f1); |
---|
| 523 | |
---|
| 524 | // convert back to factory again using the faster conversion routine for vectors over GF2X |
---|
| 525 | F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar()); |
---|
| 526 | } |
---|
[a99e31] | 527 | } |
---|
| 528 | else |
---|
[7bf145] | 529 | #endif |
---|
| 530 | { // Use Factory without NTL |
---|
[34ceab] | 531 | if ( isOn( SW_BERLEKAMP ) ) |
---|
| 532 | F=FpFactorizeUnivariateB( f, issqrfree ); |
---|
| 533 | else |
---|
| 534 | F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() ); |
---|
[a99e31] | 535 | } |
---|
| 536 | } |
---|
| 537 | else |
---|
[7bf145] | 538 | { |
---|
| 539 | #ifdef HAVE_NTL |
---|
| 540 | if (issqrfree) |
---|
| 541 | { |
---|
| 542 | CFList factors; |
---|
| 543 | Variable alpha; |
---|
| 544 | if (CFFactory::gettype() == GaloisFieldDomain) |
---|
| 545 | factors= GFSqrfFactorize (f); |
---|
| 546 | else if (hasFirstAlgVar (f, alpha)) |
---|
| 547 | factors= FqSqrfFactorize (f, alpha); |
---|
| 548 | else |
---|
| 549 | factors= FpSqrfFactorize (f); |
---|
| 550 | for (CFListIterator i= factors; i.hasItem(); i++) |
---|
| 551 | F.append (CFFactor (i.getItem(), 1)); |
---|
| 552 | } |
---|
[e89e56] | 553 | else |
---|
[7bf145] | 554 | { |
---|
| 555 | Variable alpha; |
---|
| 556 | if (CFFactory::gettype() == GaloisFieldDomain) |
---|
| 557 | F= GFFactorize (f); |
---|
| 558 | else if (hasFirstAlgVar (f, alpha)) |
---|
| 559 | F= FqFactorize (f, alpha); |
---|
| 560 | else |
---|
[34ceab] | 561 | F= FpFactorize (f); |
---|
[7bf145] | 562 | } |
---|
| 563 | #else |
---|
| 564 | ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
| 565 | #endif |
---|
[7af0e48] | 566 | } |
---|
[a99e31] | 567 | } |
---|
[e89e56] | 568 | else |
---|
[a99e31] | 569 | { |
---|
[77f483] | 570 | bool on_rational = isOn(SW_RATIONAL); |
---|
| 571 | On(SW_RATIONAL); |
---|
[a99e31] | 572 | CanonicalForm cd = bCommonDen( f ); |
---|
| 573 | CanonicalForm fz = f * cd; |
---|
| 574 | Off(SW_RATIONAL); |
---|
| 575 | if ( f.isUnivariate() ) |
---|
| 576 | { |
---|
[7af0e48] | 577 | #ifdef HAVE_NTL |
---|
| 578 | if ((isOn(SW_USE_NTL)) && (isPurePoly(f))) |
---|
| 579 | { |
---|
[a99e31] | 580 | //USE NTL |
---|
[7af0e48] | 581 | CanonicalForm ic=icontent(fz); |
---|
| 582 | fz/=ic; |
---|
[a99e31] | 583 | ZZ c; |
---|
| 584 | vec_pair_ZZX_long factors; |
---|
| 585 | //factorize the converted polynomial |
---|
[7af0e48] | 586 | factor(c,factors,convertFacCF2NTLZZX(fz)); |
---|
| 587 | |
---|
[a99e31] | 588 | //convert the result back to Factory |
---|
| 589 | F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar()); |
---|
[7af0e48] | 590 | if ( ! ic.isOne() ) |
---|
| 591 | { |
---|
| 592 | if ( F.getFirst().factor().inCoeffDomain() ) |
---|
| 593 | { |
---|
| 594 | CFFactor new_first( F.getFirst().factor() * ic ); |
---|
| 595 | F.removeFirst(); |
---|
| 596 | F.insert( new_first ); |
---|
| 597 | } |
---|
| 598 | else |
---|
| 599 | F.insert( CFFactor( ic ) ); |
---|
| 600 | } |
---|
[cd86ac] | 601 | else |
---|
| 602 | { |
---|
[cae0b6] | 603 | if ( !F.getFirst().factor().inCoeffDomain() ) |
---|
| 604 | { |
---|
| 605 | CFFactor new_first( 1 ); |
---|
| 606 | F.insert( new_first ); |
---|
| 607 | } |
---|
[cd86ac] | 608 | } |
---|
[cae0b6] | 609 | //if ( F.getFirst().factor().isOne() ) |
---|
| 610 | //{ |
---|
| 611 | // F.removeFirst(); |
---|
| 612 | //} |
---|
[cd86ac] | 613 | //printf("NTL:\n");out_cff(F); |
---|
| 614 | //F=ZFactorizeUnivariate( fz, issqrfree ); |
---|
| 615 | //printf("fac.:\n");out_cff(F); |
---|
[a99e31] | 616 | } |
---|
| 617 | else |
---|
| 618 | #endif |
---|
[7af0e48] | 619 | { |
---|
[a99e31] | 620 | //Use Factory without NTL |
---|
| 621 | F = ZFactorizeUnivariate( fz, issqrfree ); |
---|
| 622 | } |
---|
| 623 | } |
---|
| 624 | else |
---|
[afd067] | 625 | { |
---|
[a99e31] | 626 | F = ZFactorizeMultivariate( fz, issqrfree ); |
---|
[afd067] | 627 | } |
---|
[a99e31] | 628 | |
---|
| 629 | if ( on_rational ) |
---|
| 630 | On(SW_RATIONAL); |
---|
| 631 | if ( ! cd.isOne() ) |
---|
| 632 | { |
---|
| 633 | if ( F.getFirst().factor().inCoeffDomain() ) |
---|
| 634 | { |
---|
| 635 | CFFactor new_first( F.getFirst().factor() / cd ); |
---|
| 636 | F.removeFirst(); |
---|
| 637 | F.insert( new_first ); |
---|
| 638 | } |
---|
| 639 | else |
---|
| 640 | { |
---|
| 641 | F.insert( CFFactor( 1/cd ) ); |
---|
| 642 | } |
---|
[2dd068] | 643 | } |
---|
[7af0e48] | 644 | } |
---|
[a99e31] | 645 | |
---|
[cae0b6] | 646 | if ((mv!=org_v) && (! f.isUnivariate() )) |
---|
[a99e31] | 647 | { |
---|
| 648 | CFFListIterator J=F; |
---|
| 649 | for ( ; J.hasItem(); J++) |
---|
| 650 | { |
---|
[cae0b6] | 651 | swapvar(J.getItem().factor(),Variable(mv),Variable(org_v)); |
---|
[2dd068] | 652 | } |
---|
[cae0b6] | 653 | swapvar(f,Variable(mv),Variable(org_v)); |
---|
[a99e31] | 654 | } |
---|
[cae0b6] | 655 | //out_cff(F); |
---|
[3fd1ff] | 656 | if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF); |
---|
[a99e31] | 657 | return F; |
---|
[2dd068] | 658 | } |
---|
[cae0b6] | 659 | |
---|
[6acb298] | 660 | #ifdef HAVE_NTL |
---|
[b1476d0] | 661 | CanonicalForm fntl ( const CanonicalForm & f, int j ) |
---|
| 662 | { |
---|
| 663 | ZZX f1=convertFacCF2NTLZZX(f); |
---|
| 664 | return convertZZ2CF(coeff(f1,j)); |
---|
[cd86ac] | 665 | } |
---|
[6acb298] | 666 | #endif |
---|
[2dd068] | 667 | |
---|
| 668 | CFFList factorize ( const CanonicalForm & f, const Variable & alpha ) |
---|
| 669 | { |
---|
[fcf7587] | 670 | if ( f.inCoeffDomain() ) |
---|
| 671 | return CFFList( f ); |
---|
[cd86ac] | 672 | //out_cf("factorize:",f,"==================================\n"); |
---|
| 673 | //out_cf("mipo:",getMipo(alpha),"\n"); |
---|
| 674 | CFFList F; |
---|
| 675 | ASSERT( alpha.level() < 0, "not an algebraic extension" ); |
---|
[34ceab] | 676 | int ch=getCharacteristic(); |
---|
| 677 | if (f.isUnivariate()&& (ch>0)) |
---|
[cd86ac] | 678 | { |
---|
[7bf145] | 679 | #ifdef HAVE_NTL |
---|
| 680 | if (isOn(SW_USE_NTL)) |
---|
[cd86ac] | 681 | { |
---|
[7bf145] | 682 | //USE NTL |
---|
[34ceab] | 683 | if (ch>2) |
---|
[b1326b] | 684 | { |
---|
[34ceab] | 685 | // First all cases with characteristic !=2 |
---|
| 686 | // set remainder |
---|
| 687 | if (fac_NTL_char!=getCharacteristic()) |
---|
| 688 | { |
---|
| 689 | fac_NTL_char=getCharacteristic(); |
---|
| 690 | #ifdef NTL_ZZ |
---|
| 691 | ZZ r; |
---|
| 692 | r=getCharacteristic(); |
---|
| 693 | ZZ_pContext ccc(r); |
---|
| 694 | #else |
---|
| 695 | zz_pContext ccc(getCharacteristic()); |
---|
| 696 | #endif |
---|
| 697 | ccc.restore(); |
---|
| 698 | #ifdef NTL_ZZ |
---|
| 699 | ZZ_p::init(r); |
---|
| 700 | #else |
---|
| 701 | zz_p::init(getCharacteristic()); |
---|
| 702 | #endif |
---|
| 703 | } |
---|
| 704 | |
---|
| 705 | // set minimal polynomial in NTL |
---|
| 706 | #ifdef NTL_ZZ |
---|
| 707 | ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha)); |
---|
| 708 | ZZ_pEContext c(minPo); |
---|
| 709 | #else |
---|
| 710 | zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha)); |
---|
| 711 | zz_pEContext c(minPo); |
---|
| 712 | #endif |
---|
| 713 | |
---|
| 714 | c.restore(); |
---|
| 715 | |
---|
| 716 | // convert to NTL |
---|
| 717 | #ifdef NTL_ZZ |
---|
| 718 | ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo); |
---|
| 719 | ZZ_pE leadcoeff= LeadCoeff(f1); |
---|
| 720 | #else |
---|
| 721 | zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo); |
---|
| 722 | zz_pE leadcoeff= LeadCoeff(f1); |
---|
| 723 | #endif |
---|
| 724 | |
---|
| 725 | //make monic |
---|
| 726 | f1=f1 / leadcoeff; |
---|
| 727 | |
---|
| 728 | // factorize using NTL |
---|
| 729 | #ifdef NTL_ZZ |
---|
| 730 | vec_pair_ZZ_pEX_long factors; |
---|
| 731 | #else |
---|
| 732 | vec_pair_zz_pEX_long factors; |
---|
| 733 | #endif |
---|
| 734 | CanZass(factors,f1); |
---|
| 735 | |
---|
| 736 | // return converted result |
---|
[37cf8f] | 737 | #ifdef NTL_ZZ |
---|
| 738 | F=convertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha); |
---|
| 739 | #else |
---|
[34ceab] | 740 | F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha); |
---|
[37cf8f] | 741 | #endif |
---|
[34ceab] | 742 | } |
---|
| 743 | else if (/*getCharacteristic()*/ch==2) |
---|
| 744 | { |
---|
| 745 | // special case : GF2 |
---|
| 746 | |
---|
| 747 | // remainder is two ==> nothing to do |
---|
| 748 | // set remainder |
---|
| 749 | ZZ r; |
---|
| 750 | r=getCharacteristic(); |
---|
| 751 | ZZ_pContext ccc(r); |
---|
| 752 | ccc.restore(); |
---|
| 753 | |
---|
| 754 | // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2 |
---|
| 755 | GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar())); |
---|
| 756 | GF2EContext c(minPo); |
---|
| 757 | c.restore(); |
---|
| 758 | |
---|
| 759 | // convert to NTL again using the faster conversion routines |
---|
| 760 | GF2EX f1; |
---|
| 761 | if (isPurePoly(f)) |
---|
| 762 | { |
---|
| 763 | GF2X f_tmp=convertFacCF2NTLGF2X(f); |
---|
| 764 | f1=to_GF2EX(f_tmp); |
---|
| 765 | } |
---|
| 766 | else |
---|
| 767 | { |
---|
| 768 | f1=convertFacCF2NTLGF2EX(f,minPo); |
---|
| 769 | } |
---|
| 770 | |
---|
| 771 | // make monic (in Z/2(a)) |
---|
| 772 | GF2E f1_coef=LeadCoeff(f1); |
---|
| 773 | MakeMonic(f1); |
---|
| 774 | |
---|
| 775 | // factorize using NTL |
---|
| 776 | vec_pair_GF2EX_long factors; |
---|
| 777 | CanZass(factors,f1); |
---|
| 778 | |
---|
| 779 | // return converted result |
---|
| 780 | F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha); |
---|
[b1326b] | 781 | } |
---|
| 782 | else |
---|
| 783 | { |
---|
| 784 | } |
---|
[a99e31] | 785 | } |
---|
[7bf145] | 786 | else |
---|
| 787 | #endif |
---|
| 788 | { |
---|
| 789 | F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() ); |
---|
| 790 | } |
---|
[cd86ac] | 791 | } |
---|
[34ceab] | 792 | else if (ch>0) |
---|
[cd86ac] | 793 | { |
---|
[7bf145] | 794 | #ifdef HAVE_NTL |
---|
| 795 | F= FqFactorize (f, alpha); |
---|
| 796 | #else |
---|
| 797 | ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
| 798 | #endif |
---|
[34ceab] | 799 | |
---|
| 800 | } |
---|
[fcf7587] | 801 | else if (f.isUnivariate() && (ch == 0)) // Q(a)[x] |
---|
[59a7ca1] | 802 | { |
---|
| 803 | F= AlgExtFactorize (f, alpha); |
---|
| 804 | } |
---|
| 805 | else //Q(a)[x1,...,xn] |
---|
[34ceab] | 806 | { |
---|
[fcf7587] | 807 | F= ratFactorize (f, alpha); |
---|
[cd86ac] | 808 | } |
---|
[c58765] | 809 | if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF); |
---|
[cd86ac] | 810 | return F; |
---|
[2dd068] | 811 | } |
---|
| 812 | |
---|
[e89e56] | 813 | CFFList sqrFree ( const CanonicalForm & f ) |
---|
[2dd068] | 814 | { |
---|
[e89e56] | 815 | // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
[87e1de] | 816 | CFFList result; |
---|
| 817 | |
---|
[2dd068] | 818 | if ( getCharacteristic() == 0 ) |
---|
[e89e56] | 819 | result = sqrFreeZ( f ); |
---|
[2dd068] | 820 | else |
---|
[e89e56] | 821 | result = sqrFreeFp( f ); |
---|
[87e1de] | 822 | |
---|
[e89e56] | 823 | //return ( sort ? sortCFFList( result ) : result ); |
---|
| 824 | return result; |
---|
[87e1de] | 825 | } |
---|
| 826 | |
---|
[e89e56] | 827 | bool isSqrFree ( const CanonicalForm & f ) |
---|
[2dd068] | 828 | { |
---|
[e89e56] | 829 | // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
| 830 | if ( getCharacteristic() == 0 ) |
---|
| 831 | return isSqrFreeZ( f ); |
---|
[2dd068] | 832 | else |
---|
[e89e56] | 833 | return isSqrFreeFp( f ); |
---|
[2dd068] | 834 | } |
---|
[a99e31] | 835 | |
---|