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