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