Changeset 809d63 in git
 Timestamp:
 Apr 19, 2013, 4:18:38 PM (9 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '5bec8f88c9ee2573d328cf7c3aff2bcb301d2395')
 Children:
 19440966f58621d18daa0987fbb4e8aa899440d7
 Parents:
 4553b124a4bec0578e5f5f8d00c2d61d8464a7d6
 gitauthor:
 Martin Lee <martinlee84@web.de>20130419 16:18:38+02:00
 gitcommitter:
 Martin Lee <martinlee84@web.de>20130502 11:42:39+02:00
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/facAbsFact.cc
r4553b1 r809d63 33 33 TIMING_DEFINE_PRINT(fac_evalpoint) 34 34 35 void out_cf(const char *s1,const CanonicalForm &f,const char *s2);36 37 35 //TODO optimize choice of p > choose p as large as possible (better than small p since factorization mod p does not require field extension, also less lifting) 38 36 int choosePoint (const CanonicalForm& F, int tdegF, CFArray& eval, bool rec) … … 48 46 int i, p; 49 47 eval=CFArray (2); 50 printf ("tdegF= %d\n", tdegF);51 out_cf ("F= ", F, "\n");52 printf ("getCharacteristic()= %d\n", getCharacteristic());53 48 while (1) 54 49 { … … 59 54 f= E2(f1); 60 55 f2= E2 (F); 61 out_cf ("f= ", f, "\n"); 62 printf ("isOn (SW_RATIONAL)= %d\n", isOn (SW_RATIONAL)); 63 printf ("cf_getSmallPrime (cf_getNumSmallPrimes())= %d\n", cf_getSmallPrime (cf_getNumSmallPrimes()1)); 64 if ((!f.isZero()) && (abs(f) > cf_getSmallPrime (cf_getNumSmallPrimes()1))) 56 if ((!f.isZero()) && (abs(f)>cf_getSmallPrime (cf_getNumSmallPrimes()1))) 65 57 { 66 printf ("hier0\n");67 58 for (i= cf_getNumPrimes()1; i >= 0; i) 68 59 { … … 71 62 p= cf_getPrime(i); 72 63 Fp= mod (F,p); 73 out_cf ("Fp0= ", Fp, "\n"); 74 if (totaldegree (Fp) == tdegF && degree (mod (f2,p), 1) == degree (F,1) && degree (mod (f1, p),2) == degree (F,2)) 64 if (totaldegree (Fp) == tdegF && 65 degree (mod (f2,p), 1) == degree (F,1) && 66 degree (mod (f1, p),2) == degree (F,2)) 75 67 { 76 68 eval[0]= E1[1]; … … 83 75 else if (!f.isZero()) 84 76 { 85 printf ("hier\n");86 77 for (i= cf_getNumSmallPrimes()1; i >= 0; i) 87 78 { … … 90 81 p= cf_getSmallPrime (i); 91 82 Fp= mod (F,p); 92 out_cf ("Fp1= ", Fp, "\n"); 93 if (totaldegree (Fp) == tdegF && degree (mod (f2, p),1) == degree (F,1) && degree (mod (f1,p),2) == degree (F,2)) 83 if (totaldegree (Fp) == tdegF && 84 degree (mod (f2, p),1) == degree (F,1) && 85 degree (mod (f1,p),2) == degree (F,2)) 94 86 { 95 87 eval[0]= E1[1]; … … 102 94 E2.nextpoint(); 103 95 On (SW_RATIONAL); 104 out_cf ("E2= ", E2[2], "\n");105 96 } 106 97 E1.nextpoint(); 107 out_cf ("E1= ", E1[1], "\n");108 98 } 109 99 return 0; 110 100 } 111 101 112 // TODO sowohl bzgl. x als auch y auswerten und minpoly berechnen102 //G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed 113 103 CFAFList absFactorizeMain (const CanonicalForm& G) 114 104 { 115 //F is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed116 117 out_cf ("F= ", G, "\n");118 105 CanonicalForm F= bCommonDen (G)*G; 119 106 Off (SW_RATIONAL); 120 107 F /= icontent (F); 121 out_cf ("F after icontent= ", F, "\n");122 108 On (SW_RATIONAL); 123 109 CFArray eval; … … 130 116 Variable x= Variable (1); 131 117 Variable y= Variable (2); 118 CanonicalForm bufF= F; 119 CFFListIterator iter; 132 120 differentevalpoint: 133 121 while (1) … … 141 129 factors= factorize (Fp); 142 130 143 for (CFFListIterator iter= factors; iter.hasItem(); iter++)144 {145 out_cf ("factors= ", iter.getItem().factor(), "\n");146 printf ("exp= %d\n", iter.getItem().exp());147 }148 printf ("p= %d\n", p);149 131 if (factors.getFirst().factor().inCoeffDomain()) 150 132 factors.removeFirst(); 151 printf ("factors.length()= %d\n", factors.length()); 152 printf ("factors.getFirst().exp()= %d\n", factors.getFirst().exp()); 133 153 134 if (factors.length() == 1 && factors.getFirst().exp() == 1) 154 135 { 155 if (absIrredTest (Fp)) //TODO absIrredTest mit shift, modular absIrredTest136 if (absIrredTest (Fp)) 156 137 { 157 printf ("irred after test\n");158 printf ("absIrred\n");159 138 setCharacteristic(0); 160 139 alpha= rootOf (x); 161 out_cf ("G= ", G, "\n");162 out_cf ("getMipo (alpha)= ", getMipo (alpha), "\n");163 164 140 return CFAFList (CFAFactor (G, getMipo (alpha), 1)); 165 141 } … … 169 145 if (modularIrredTestWithShift (F)) 170 146 { 171 printf ("irred after modular test\n");172 147 alpha= rootOf (x); 173 148 return CFAFList (CFAFactor (G, getMipo (alpha), 1)); … … 177 152 } 178 153 } 179 CFFListIteratoriter= factors;154 iter= factors; 180 155 smallestFactor= iter.getItem().factor(); 181 out_cf ("smallestFactor before= ", smallestFactor, "\n");182 156 while (smallestFactor.isUnivariate() && iter.hasItem()) 183 157 { … … 185 159 if (!iter.hasItem()) 186 160 break; 187 out_cf ("factors= ", iter.getItem().factor(), "\n");188 printf ("exp= %d\n", iter.getItem().exp());189 161 smallestFactor= iter.getItem().factor(); 190 162 } 191 //TODO univariate Faktoren rausschmeiÃen! 163 192 164 minTdeg= totaldegree (smallestFactor); 193 165 if (iter.hasItem()) … … 195 167 for (; iter.hasItem(); iter++) 196 168 { 197 out_cf ("factors= ", iter.getItem().factor(), "\n"); 198 printf ("exp= %d\n", iter.getItem().exp()); 199 if (!iter.getItem().factor().isUnivariate() && (totaldegree (iter.getItem().factor()) < minTdeg)) 169 if (!iter.getItem().factor().isUnivariate() && 170 (totaldegree (iter.getItem().factor()) < minTdeg)) 200 171 { 201 172 smallestFactor= iter.getItem().factor(); … … 209 180 } 210 181 CanonicalForm Gp= Fp/smallestFactor; 211 out_cf ("Gp before= ", Gp, "\n");212 out_cf ("smallestFactor= ", smallestFactor, "\n");213 printf ("degree (Gp,1)= %d\n", degree (Gp, 1));214 printf ("degree smallestFactor= %d\n", degree (smallestFactor, 1));215 printf ("degree (Fp,1)= %d\n", degree (Fp,1));216 printf ("degree (F,1)= %d\n", degree (F,1));217 out_cf ("eval[1]= ", eval[1], "\n");218 out_cf ("eval[0]= ", eval[0], "\n");219 //printf ("Gp*smallestFactor==Fp ? %d\n", Gp*smallestFactor == Fp);220 182 Gp= Gp /Lc (Gp); 221 183 … … 223 185 CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1); 224 186 CanonicalForm Gpx= Gp (eval[1].mapinto(), 2); 225 out_cf ("Gp eval= ", Gp, "\n");226 187 CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2); 227 188 228 out_cf ("smallestFactorEvalx= ", smallestFactorEvalx, "\n");229 out_cf ("gcd (Gpx, smallestFactorEvalx)= ", gcd (Gpx, smallestFactorEvalx), "\n");230 bool xValid= !(Gpx.inCoeffDomain()  smallestFactorEvalx.inCoeffDomain()  !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());231 bool yValid= !(Gpy.inCoeffDomain()  smallestFactorEvaly.inCoeffDomain() !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());189 bool xValid= !(Gpx.inCoeffDomain()  smallestFactorEvalx.inCoeffDomain()  190 !gcd (Gpx, smallestFactorEvalx).inCoeffDomain()); 191 bool yValid= !(Gpy.inCoeffDomain()  smallestFactorEvaly.inCoeffDomain()  192 !gcd (Gpy, smallestFactorEvaly).inCoeffDomain()); 232 193 if (!xValid && !yValid) 233 194 { 234 195 rec= true; 235 196 setCharacteristic (0); 236 printf ("goto1\n");237 197 goto differentevalpoint; 238 198 } … … 260 220 261 221 CFArray mipos= CFArray (loopi); 262 printf ("loop= %d\n", loop);263 printf ("xValid= %d\n", xValid);264 printf ("yValid= %d\n", yValid);265 266 222 for (; i < loop; i++) 267 223 { 268 224 CanonicalForm Fi= F(eval[i1],i); 269 //CanonicalForm Fx= F(eval[0],1);270 //CanonicalForm Fy= F(eval[1],2);271 225 272 226 int s= tdegF/minTdeg + 1; … … 285 239 k= k+1; 286 240 fmpz_poly_t FLINTFi; 287 out_cf ("Fi= ", Fi, "\n");288 241 convertFacCF2Fmpz_poly_t (FLINTFi, Fi); 289 242 setCharacteristic (p); 290 printf ("p= %d\n", p);291 243 nmod_poly_t FLINTFpi, FLINTGpi; 292 244 if (i == 2) 293 245 { 294 convertFacCF2nmod_poly_t (FLINTFpi, smallestFactorEvalx/lc (smallestFactorEvalx)); 246 convertFacCF2nmod_poly_t (FLINTFpi, 247 smallestFactorEvalx/lc (smallestFactorEvalx)); 295 248 convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx)); 296 249 } 297 250 else 298 251 { 299 convertFacCF2nmod_poly_t (FLINTFpi, smallestFactorEvaly/lc (smallestFactorEvaly)); 252 convertFacCF2nmod_poly_t (FLINTFpi, 253 smallestFactorEvaly/lc (smallestFactorEvaly)); 300 254 convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy)); 301 255 } … … 305 259 nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L); 306 260 307 //out_cf ("Gpx= ", Gpx, "\n");308 //out_cf ("smallestFactorEvalx= ", smallestFactorEvalx, "\n");309 261 long * link= new long [2]; 310 262 fmpz_poly_t *v= new fmpz_poly_t[2]; … … 315 267 fmpz_poly_init(w[1]); 316 268 317 printf ("k= %ld\n", k);318 269 fmpz_poly_factor_t liftedFactors; 319 270 fmpz_poly_factor_init (liftedFactors); 320 _fmpz_poly_hensel_start_lift(liftedFactors, link, v, w, FLINTFi, nmodFactors, k); //lift factors up to p^k 271 _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi, 272 nmodFactors, k); 321 273 322 274 nmod_poly_factor_clear (nmodFactors); … … 326 278 setCharacteristic(0); 327 279 modpk pk= modpk (p,k); 328 CanonicalForm liftedSmallestFactor= convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors>p[0],Variable (1)); 329 330 CanonicalForm otherFactor= convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors>p[1],Variable (1)); 280 CanonicalForm liftedSmallestFactor= 281 convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors>p[0],Variable (1)); 282 283 CanonicalForm otherFactor= 284 convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors>p[1],Variable (1)); 331 285 CanonicalForm test= pk (otherFactor*liftedSmallestFactor); 332 286 … … 378 332 { 379 333 rec=true; 380 printf ("goto2\n");381 334 goto differentevalpoint; 382 //TODO check if mipoFactors has length 1 and multiplicity 1  if not choose a new point!383 335 } 384 336 } … … 395 347 alpha= rootOf (mipos[1]); 396 348 } 349 else if (xValid && yValid) 350 { 351 if (mipos[0].isZero()) 352 alpha= rootOf (mipos[1]); 353 else 354 alpha= rootOf (mipos[0]); 355 } 397 356 else 398 357 alpha= rootOf (mipo); 399 400 for (i= 0; i < mipos.size(); i++)401 {402 out_cf ("mipos= ", mipos [i], "\n");403 out_cf ("maxNorm mipo= ", maxNorm (mipos[i]), "\n");404 }405 358 406 359 CanonicalForm F1; … … 419 372 F1= F (eval[0], 1); 420 373 374 bool swap= false; 375 if (F1.level() == 2) 376 { 377 swap= true; 378 F1=swapvar (F1, x, y); 379 F= swapvar (F, x, y); 380 } 381 421 382 QaF1Factors= factorize (F1, alpha); 422 383 if (QaF1Factors.getFirst().factor().inCoeffDomain()) 423 384 QaF1Factors.removeFirst(); 424 out_cf ("mipo0= ", getMipo (alpha), "\n"); 425 for (CFFListIterator iter= QaF1Factors; iter.hasItem(); iter++) 426 { 427 out_cf ("QaF1Factors= ", iter.getItem().factor(), "\n"); 385 for (iter= QaF1Factors; iter.hasItem(); iter++) 386 { 428 387 if (degree (iter.getItem().factor()) > minTdeg) 429 388 wrongMipo++; … … 432 391 if (wrongMipo == QaF1Factors.length()) 433 392 { 434 if (xValid && yValid )435 { 436 if (m ipo==mipos[0])393 if (xValid && yValid && !mipos[0].isZero() && !mipos[1].isZero()) 394 { 395 if (maxNorm (mipos[0]) < maxNorm (mipos[1])) //try the other minpoly 437 396 alpha= rootOf (mipos[1]); 438 397 else 439 398 alpha= rootOf (mipos[0]); 440 399 } 400 else 401 { 402 rec= true; 403 F= bufF; 404 goto differentevalpoint; 405 } 441 406 442 407 wrongMipo= 0; 443 out_cf ("mipo1= ", getMipo (alpha), "\n");444 408 QaF1Factors= factorize (F1, alpha); 445 409 if (QaF1Factors.getFirst().factor().inCoeffDomain()) 446 410 QaF1Factors.removeFirst(); 447 for (CFFListIterator iter= QaF1Factors; iter.hasItem(); iter++) 448 { 449 out_cf ("QaF1Factors= ", iter.getItem().factor(), "\n"); 411 for (iter= QaF1Factors; iter.hasItem(); iter++) 412 { 450 413 if (degree (iter.getItem().factor()) > minTdeg) 451 414 wrongMipo++; … … 454 417 { 455 418 rec= true; 456 printf ("goto30\n");419 F= bufF; 457 420 goto differentevalpoint; 458 421 } 459 422 } 460 423 461 CanonicalForm A= F;462 CanonicalForm Aeval= F1;463 464 out_cf ("F1= ", F1, "\n");465 A *= bCommonDen (A);466 A= A (y + eval[1], y); //TODO find right evaluation point and swap if necessary 467 468 out_cf ("A= ", A, "\n");469 out_cf ("A[0]= ", A(0,y), "\n"); 470 int liftBound= degree ( A,y) + 1;424 CanonicalForm evaluation; 425 if (swap) 426 evaluation= eval[0]; 427 else 428 evaluation= eval[1]; 429 430 F *= bCommonDen (F); 431 F= F (y + evaluation, y); 432 433 int liftBound= degree (F,y) + 1; 471 434 472 435 modpk b= modpk(); 473 436 474 //bool mipoHasDen= false;475 437 CanonicalForm den= 1; 476 438 … … 478 440 479 441 CFList uniFactors; 480 for (CFFListIterator iter=QaF1Factors; iter.hasItem(); iter++) 481 { 442 for (iter=QaF1Factors; iter.hasItem(); iter++) 482 443 uniFactors.append (iter.getItem().factor()); 483 out_cf ("uniFactors.getLast()= ", uniFactors.getLast(), "\n"); 484 } 485 486 487 A /= Lc (Aeval); 488 //mipoHasDen= !bCommonDen(mipo).isOne(); 489 //mipo *= bCommonDen (mipo); 490 ZZX NTLmipo= convertFacCF2NTLZZX (mipo); 491 ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A))); 492 ZZ NTLf= resultant (NTLmipo, NTLLcf); 493 ZZ NTLD= discriminant (NTLmipo); 494 den= abs (convertZZ2CF (NTLD*NTLf)); 495 496 // make factors elements of Z(a)[x] disable for modularDiophant 497 CanonicalForm multiplier= 1; 498 for (CFListIterator i= uniFactors; i.hasItem(); i++) 499 { 500 multiplier *= bCommonDen (i.getItem()); 501 i.getItem()= i.getItem()*bCommonDen(i.getItem()); 502 } 503 A *= multiplier; 504 A *= bCommonDen (A); 505 506 Off (SW_RATIONAL); 507 int ii= 0; 508 CanonicalForm discMipo= convertZZ2CF (NTLD); 509 findGoodPrime (F*discMipo,ii); 510 findGoodPrime (Aeval*discMipo,ii); 511 findGoodPrime (A*discMipo,ii); 512 513 int pp=cf_getBigPrime(ii); 514 b = coeffBound( A, pp, mipo ); 515 modpk bb= coeffBound (Aeval, pp, mipo); 516 if (bb.getk() > b.getk() ) b=bb; 517 bb= coeffBound (F, pp, mipo); 518 if (bb.getk() > b.getk() ) b=bb; 444 445 F /= Lc (F1); 446 ZZX NTLmipo= convertFacCF2NTLZZX (mipo); 447 ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F))); 448 ZZ NTLf= resultant (NTLmipo, NTLLcf); 449 ZZ NTLD= discriminant (NTLmipo); 450 den= abs (convertZZ2CF (NTLD*NTLf)); 451 452 // make factors elements of Z(a)[x] disable for modularDiophant 453 CanonicalForm multiplier= 1; 454 for (CFListIterator i= uniFactors; i.hasItem(); i++) 455 { 456 multiplier *= bCommonDen (i.getItem()); 457 i.getItem()= i.getItem()*bCommonDen(i.getItem()); 458 } 459 F *= multiplier; 460 F *= bCommonDen (F); 461 462 Off (SW_RATIONAL); 463 int ii= 0; 464 CanonicalForm discMipo= convertZZ2CF (NTLD); 465 findGoodPrime (bufF*discMipo,ii); 466 findGoodPrime (F1*discMipo,ii); 467 findGoodPrime (F*discMipo,ii); 468 469 int pp=cf_getBigPrime(ii); 470 b = coeffBound( F, pp, mipo ); 471 modpk bb= coeffBound (F1, pp, mipo); 472 if (bb.getk() > b.getk() ) b=bb; 473 bb= coeffBound (F, pp, mipo); 474 if (bb.getk() > b.getk() ) b=bb; 519 475 520 476 ExtensionInfo dummy= ExtensionInfo (alpha, false); … … 525 481 TIMING_START (fac_bi_hensel_lift); 526 482 uniFactors= henselLiftAndEarly 527 ( A, earlySuccess, earlyFactors, degs, liftBound,528 uniFactors, dummy, eval [1], b, den);483 (F, earlySuccess, earlyFactors, degs, liftBound, 484 uniFactors, dummy, evaluation, b, den); 529 485 TIMING_END_AND_PRINT (fac_bi_hensel_lift, 530 486 "time for bivariate hensel lifting over Q: "); 531 487 DEBOUTLN (cerr, "lifted factors= " << uniFactors); 532 488 533 CanonicalForm MODl= power (y, liftBound); //TODO489 CanonicalForm MODl= power (y, liftBound); 534 490 535 491 On (SW_RATIONAL); 536 A *= bCommonDen (A);492 F *= bCommonDen (F); 537 493 Off (SW_RATIONAL); 538 494 539 printf ("earlyFactors.length()= %d\n", earlyFactors.length());540 495 CFList biFactors; 541 496 542 497 TIMING_START (fac_bi_factor_recombination); 543 biFactors= factorRecombination (uniFactors, A, MODl, degs, 1,498 biFactors= factorRecombination (uniFactors, F, MODl, degs, 1, 544 499 uniFactors.length()/2, b, den); 545 500 TIMING_END_AND_PRINT (fac_bi_factor_recombination, … … 554 509 555 510 for (CFListIterator i= biFactors; i.hasItem(); i++) 556 i.getItem()= i.getItem() (y  eval[1], y); //TODO 557 558 bool swap= false; 511 i.getItem()= i.getItem() (y  evaluation, y); 512 559 513 bool swap2= false; 560 514 appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap()); … … 565 519 bool found= false; 566 520 567 out_cf ("mipo= ", mipo, "\n"); 568 printf ("minTdeg= %d\n", minTdeg); 569 for (CFListIterator iter= biFactors; iter.hasItem(); iter++) 570 { 571 out_cf ("biFactors= ", iter.getItem(), "\n"); 572 printf ("totaldegree ()= %d\n", totaldegree (iter.getItem())); 573 if (totaldegree (iter.getItem()) == minTdeg) 574 { 575 result= CFAFList (CFAFactor (iter.getItem(), getMipo (alpha), 1)); 521 for (CFListIterator i= biFactors; i.hasItem(); i++) 522 { 523 if (totaldegree (i.getItem()) == minTdeg) 524 { 525 result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1)); 576 526 found= true; 577 527 break; … … 579 529 } 580 530 581 if (found) 582 { 583 printf ("thisexitexit\n\n"); 584 return result; 585 } 586 587 /* A *= bCommonDen (A); 588 A= A (y + evaluation, y); 589 590 int liftBound= degree (A, y) + 1; 591 592 modpk b= modpk(); 593 bool mipoHasDen= false; 594 CanonicalForm den= 1; 595 596 if (!extension) 597 { 598 Off (SW_RATIONAL); 599 int i= 0; 600 findGoodPrime(F,i); 601 findGoodPrime(Aeval,i); 602 findGoodPrime(A,i); 603 if (i >= cf_getNumBigPrimes()) 604 printf ("out of primes\n"); //TODO exit 605 606 int p=cf_getBigPrime(i); 607 b = coeffBound( A, p ); 608 modpk bb= coeffBound (Aeval, p); 609 if (bb.getk() > b.getk() ) b=bb; 610 bb= coeffBound (F, p); 611 if (bb.getk() > b.getk() ) b=bb; 612 } 613 else 614 { 615 A /= Lc (Aeval); 616 mipoHasDen= !bCommonDen(mipo).isOne(); 617 mipo *= bCommonDen (mipo); 618 ZZX NTLmipo= convertFacCF2NTLZZX (mipo); 619 ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A))); 620 ZZ NTLf= resultant (NTLmipo, NTLLcf); 621 ZZ NTLD= discriminant (NTLmipo); 622 den= abs (convertZZ2CF (NTLD*NTLf)); 623 624 // make factors elements of Z(a)[x] disable for modularDiophant 625 CanonicalForm multiplier= 1; 626 for (CFListIterator i= uniFactors; i.hasItem(); i++) 627 { 628 multiplier *= bCommonDen (i.getItem()); 629 i.getItem()= i.getItem()*bCommonDen(i.getItem()); 630 } 631 A *= multiplier; 632 A *= bCommonDen (A); 633 634 Off (SW_RATIONAL); 635 int i= 0; 636 CanonicalForm discMipo= convertZZ2CF (NTLD); 637 findGoodPrime (F*discMipo,i); 638 findGoodPrime (Aeval*discMipo,i); 639 findGoodPrime (A*discMipo,i); 640 641 int p=cf_getBigPrime(i); 642 b = coeffBound( A, p, mipo ); 643 modpk bb= coeffBound (Aeval, p, mipo); 644 if (bb.getk() > b.getk() ) b=bb; 645 bb= coeffBound (F, p, mipo); 646 if (bb.getk() > b.getk() ) b=bb; 647 } 648 649 ExtensionInfo dummy= ExtensionInfo (false); 650 if (extension) 651 dummy= ExtensionInfo (v, false); 652 bool earlySuccess= false; 653 CFList earlyFactors; 654 TIMING_START (fac_bi_hensel_lift); 655 uniFactors= henselLiftAndEarly 656 (A, earlySuccess, earlyFactors, degs, liftBound, 657 uniFactors, dummy, evaluation, b, den); 658 TIMING_END_AND_PRINT (fac_bi_hensel_lift, 659 "time for bivariate hensel lifting over Q: "); 660 DEBOUTLN (cerr, "lifted factors= " << uniFactors); 661 662 CanonicalForm MODl= power (y, liftBound); 663 664 if (mipoHasDen) 665 { 666 Variable vv; 667 for (CFListIterator iter= uniFactors; iter.hasItem(); iter++) 668 if (hasFirstAlgVar (iter.getItem(), vv)) 669 break; 670 for (CFListIterator iter= uniFactors; iter.hasItem(); iter++) 671 iter.getItem()= replacevar (iter.getItem(), vv, v); 672 } 673 674 On (SW_RATIONAL); 675 A *= bCommonDen (A); 676 Off (SW_RATIONAL); 677 678 TIMING_START (fac_bi_factor_recombination); 679 factors= factorRecombination (uniFactors, A, MODl, degs, 1, 680 uniFactors.length()/2, b, den); 681 TIMING_END_AND_PRINT (fac_bi_factor_recombination, 682 "time for bivariate factor recombination over Q: "); 683 684 On (SW_RATIONAL); 685 686 if (earlySuccess) 687 factors= Union (earlyFactors, factors); 688 else if (!earlySuccess && degs.getLength() == 1) 689 factors= earlyFactors; 690 691 for (CFListIterator i= factors; i.hasItem(); i++) 692 i.getItem()= i.getItem() (y  evaluation, y); 693 694 appendSwapDecompress (factors, conv (contentAxFactors), 695 conv (contentAyFactors), swap, swap2, N); 696 if (isOn (SW_RATIONAL)) 697 normalize (factors);*/ 698 699 TIMING_START (fac_Qa_factorize); 700 CFFList QaFactors= factorize (F, alpha); //TODO lift these factors 701 TIMING_END_AND_PRINT (fac_Qa_factorize, "time to factorize over Qa: "); 702 703 /*mipo= getMipo (alpha); 704 out_cf ("maxNorm (mipo)= ", maxNorm (mipo), "\n"); 705 QaFactors.append (CFFactor (mipo, 1)); //last factor is the minimal polynomial that defines the extension 706 if (degree (mipo) < 3) 707 printf ("scheissescheissescheissescheisse\n");*/ 708 printf ("minTdeg= %d\n", minTdeg); 709 //CFAFList result; 710 //bool found= false; 711 out_cf ("mipo= ", getMipo (alpha), "\n"); 712 for (CFFListIterator iter= QaFactors; iter.hasItem(); iter++) 713 { 714 out_cf ("QaFactors= ", iter.getItem().factor(), "\n"); 715 printf ("totaldegree ()= %d\n", totaldegree (iter.getItem().factor())); 716 if (totaldegree (iter.getItem().factor()) == minTdeg) 717 { 718 result= CFAFList (CFAFactor (iter.getItem().factor(), getMipo (alpha), 1)); 719 found= true; 720 break; 721 } 722 } 723 if (!found && xValid && yValid) 724 { 725 if (mipo == mipos [0]) 726 mipo= mipos[1]; 727 else 728 mipo= mipos[0]; 729 alpha= rootOf (mipo); 730 731 QaFactors= factorize (F, alpha); 732 733 for (CFFListIterator iter= QaFactors; iter.hasItem(); iter++) 734 { 735 out_cf ("QaFactors= ", iter.getItem().factor(), "\n"); 736 printf ("totaldegree ()= %d\n", totaldegree (iter.getItem().factor())); 737 if (totaldegree (iter.getItem().factor()) == minTdeg) 738 { 739 result= CFAFList (CFAFactor (iter.getItem().factor(), getMipo (alpha), 1)); 740 found= true; 741 break; 742 } 743 } 744 if (!found) 745 { 746 rec= true; 747 printf ("goto31\n"); 748 goto differentevalpoint; 749 } 750 } 751 else if (!found) 531 if (!found) 752 532 { 753 533 rec= true; 754 printf ("goto32\n");534 F= bufF; 755 535 goto differentevalpoint; 756 536 } … … 758 538 return result; 759 539 } 540 760 541 #endif 761 542 #endif
Note: See TracChangeset
for help on using the changeset viewer.