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