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