Changeset 44651b in git
 Timestamp:
 Jun 17, 2010, 6:19:12 PM (14 years ago)
 Branches:
 (u'fiekerDuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b52fc4b2495505785981d640dcf7eb3e456778ef')
 Children:
 e558c41b132228287898863201fbd5c35b4231fd
 Parents:
 d52c121e17973d80d9181edd4a487916a0741038
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/facFqFactorize.cc
rd52c12 r44651b 1 1 /*****************************************************************************\ 2 * Computer Algebra System SINGULAR 2 * Computer Algebra System SINGULAR 3 3 \*****************************************************************************/ 4 4 /** @file facFqFactorize.cc 5 * 5 * 6 6 * This file implements functions for factoring a multivariate polynomial over 7 * a finite field. 8 * 9 * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by 10 * L. Bernardin & M. Monagon. 7 * a finite field. 8 * 9 * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by 10 * L. Bernardin & M. Monagon. 11 11 * 12 12 * @author Martin Lee … … 40 40 41 41 static inline 42 CanonicalForm 42 CanonicalForm 43 43 listGCD (const CFList& L); 44 44 45 45 static inline 46 CanonicalForm 46 CanonicalForm 47 47 myContent (const CanonicalForm& F) 48 48 { … … 58 58 if (GF) 59 59 { 60 return swapvar (GCD_GF (L.getFirst(), L.getLast()), F.mvar(), 60 return swapvar (GCD_GF (L.getFirst(), L.getLast()), F.mvar(), 61 61 Variable (1)); 62 62 } 63 63 else if (!GF && algExt) 64 64 { 65 return swapvar (GCD_Fp_extension (L.getFirst(), L.getLast(), alpha), 65 return swapvar (GCD_Fp_extension (L.getFirst(), L.getLast(), alpha), 66 66 F.mvar(), Variable (1)); 67 67 } 68 68 else 69 return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(), 69 return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(), 70 70 Variable (1)); 71 71 } … … 78 78 79 79 static inline 80 CanonicalForm 80 CanonicalForm 81 81 listGCD (const CFList& L) 82 82 { … … 91 91 return GCD_GF (L.getFirst(), L.getLast()); 92 92 } 93 else if (!GF && (hasFirstAlgVar (L.getFirst(), alpha)  93 else if (!GF && (hasFirstAlgVar (L.getFirst(), alpha)  94 94 hasFirstAlgVar (L.getLast(), alpha))) 95 95 { … … 107 107 int j= 0; 108 108 for (CFListIterator i= L; j < length; i++, j++) 109 lHi.append (i.getItem()); 109 lHi.append (i.getItem()); 110 110 lLo= Difference (L, lHi); 111 111 resultHi= listGCD (lHi); … … 117 117 return GCD_GF (resultHi, resultLo); 118 118 } 119 else if (!GF && (hasFirstAlgVar (resultHi, alpha)  119 else if (!GF && (hasFirstAlgVar (resultHi, alpha)  120 120 hasFirstAlgVar (resultLo, alpha))) 121 121 { … … 158 158 { 159 159 if (swap) 160 return swapvar(GCD_Fp_extension (L.getFirst(), L.getLast(), alpha), 160 return swapvar(GCD_Fp_extension (L.getFirst(), L.getLast(), alpha), 161 161 F.mvar(), x); 162 162 else … … 166 166 { 167 167 if (swap) 168 return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(), 168 return swapvar (GCD_small_p (L.getFirst(), L.getLast()), F.mvar(), 169 169 x); 170 170 else … … 194 194 if (GF) 195 195 return (F/GCD_GF (F, G))*G; 196 else if (!GF && (hasFirstAlgVar (F, alpha)  196 else if (!GF && (hasFirstAlgVar (F, alpha)  197 197 hasFirstAlgVar (G, alpha))) 198 198 return (F/GCD_Fp_extension (F, G, alpha))*G; … … 203 203 204 204 205 static inline 205 static inline 206 206 CanonicalForm myCompress (const CanonicalForm& F, CFMap& N) 207 207 { … … 210 210 int ** swap; 211 211 swap= new int* [n + 1]; 212 for (int i= 0; i <= n; i++) 212 for (int i= 0; i <= n; i++) 213 213 { 214 214 degsf[i]= 0; 215 215 swap [i]= new int [2]; 216 swap [i] [0]= 0; 216 217 swap [i] [1]= 0; 217 swap [i] [2]= 0;218 218 } 219 219 int i= 1; 220 n= 1; 220 n= 1; 221 221 degsf= degrees (F, degsf); 222 222 223 223 CanonicalForm result= F; 224 while ( i <= F.level() ) 224 while ( i <= F.level() ) 225 225 { 226 226 while( degsf[i] == 0 ) i++; 227 swap[n][ 1]= i;228 swap[n][ 2]= degsf[i];227 swap[n][0]= i; 228 swap[n][1]= degsf[i]; 229 229 if (i != n) 230 230 result= swapvar (result, Variable (n), Variable(i)); … … 235 235 n; 236 236 237 for (i= 1; i < n; i++) 238 { 239 for (int j= 1; j < n  i + 1; j++) 240 { 241 if (swap[j][2] < swap[j + 1][2]) 242 { 243 buf1= swap [j + 1] [1]; 244 buf2= swap [j + 1] [2]; 237 for (i= 1; i < n; i++) 238 { 239 for (int j= 1; j < n  i + 1; j++) 240 { 241 if (swap[j][1] < swap[j + 1][1]) 242 { 243 buf1= swap [j + 1] [0]; 244 buf2= swap [j + 1] [1]; 245 swap[j + 1] [0]= swap[j] [0]; 245 246 swap[j + 1] [1]= swap[j] [1]; 246 swap[j + 1] [2]= swap[j] [2]; 247 swap[j][1]= buf1; 248 swap[j][2]= buf2; 247 swap[j][0]= buf1; 248 swap[j][1]= buf2; 249 249 result= swapvar (result, Variable (j + 1), Variable (j)); 250 } 251 } 252 } 253 254 for (i= n; i > 0; i) 255 { 256 if (i != swap[i] [ 1])257 N.newpair (Variable (i), Variable (swap[i] [ 1]));250 } 251 } 252 } 253 254 for (i= n; i > 0; i) 255 { 256 if (i != swap[i] [0]) 257 N.newpair (Variable (i), Variable (swap[i] [0])); 258 258 } 259 259 … … 266 266 return result; 267 267 } 268 269 CFList 268 269 CFList 270 270 monicFactorRecombi (const CFList& factors,const CanonicalForm& F, const 271 CanonicalForm& M, const DegreePattern& degs) 271 CanonicalForm& M, const DegreePattern& degs) 272 272 { 273 if (degs.getLength() == 1) 274 return CFList(F); 273 if (degs.getLength() == 1) 274 return CFList(F); 275 275 276 276 CFList T, S; 277 277 278 278 T= factors; 279 279 … … 290 290 int subsetDeg; 291 291 DegreePattern bufDegs1= degs, bufDegs2; 292 TT= copy (factors); 293 while (T.length() >= 2*s) 294 { 295 while (noSubset == false) 296 { 297 if (T.length() == s) 292 TT= copy (factors); 293 while (T.length() >= 2*s) 294 { 295 while (noSubset == false) 296 { 297 if (T.length() == s) 298 298 { 299 299 result.append (prodMod (T, M)); … … 303 303 if (noSubset) break; 304 304 subsetDeg= subsetDegree (S); 305 if (!degs.find (subsetDeg)) 305 if (!degs.find (subsetDeg)) 306 306 continue; 307 else 308 { 307 else 308 { 309 309 g= prodMod0 (S, M); 310 310 gg= mod (g*LCBuf, M); //univariate polys … … 324 324 bufDegs2= DegreePattern (T); 325 325 bufDegs1.intersect (bufDegs2); 326 bufDegs1.refine (); 327 if (T.length() < 2*s  T.length() == s  328 bufDegs1.getLength() == 1) 326 bufDegs1.refine (); 327 if (T.length() < 2*s  T.length() == s  328 bufDegs1.getLength() == 1) 329 329 { 330 result.append (prodMod (T, M)); 331 return result; 330 result.append (prodMod (T, M)); 331 return result; 332 332 } 333 333 TT= copy (T); 334 334 indexUpdate (v, s, T.length(), noSubset); 335 if (noSubset) break; 335 if (noSubset) break; 336 336 } 337 337 } … … 339 339 } 340 340 s++; 341 if (T.length() < 2*s  T.length() == s) 341 if (T.length() < 2*s  T.length() == s) 342 342 { 343 343 result.append (prodMod (T, M)); … … 349 349 noSubset= false; 350 350 } 351 if (T.length() < 2*s) 352 result.append (prodMod (T, M)); 353 354 return result; 355 } 356 357 CFList 358 earlyMonicFactorDetect (CanonicalForm& F, CFList& factors, 351 if (T.length() < 2*s) 352 result.append (prodMod (T, M)); 353 354 return result; 355 } 356 357 CFList 358 earlyMonicFactorDetect (CanonicalForm& F, CFList& factors, 359 359 int& adaptedLiftBound, DegreePattern& degs, 360 360 bool& success, int deg, const int bound) … … 371 371 int e= 0; 372 372 adaptedLiftBound= 0; 373 for (CFListIterator i= factors; i.hasItem(); i++) 373 for (CFListIterator i= factors; i.hasItem(); i++) 374 374 { 375 375 if (!bufDegs1.find (degree (i.getItem(), 1))) … … 392 392 d = degree (gg) + degree (LC (gg, 1)); 393 393 e= tmax (e, degree (gg) + degree (LC (gg, 1))); 394 LCBuf= LC (buf, Variable (1)); 394 LCBuf= LC (buf, Variable (1)); 395 395 T= Difference (T, CFList (i.getItem())); 396 396 … … 398 398 bufDegs2= DegreePattern (T); 399 399 bufDegs1.intersect (bufDegs2); 400 bufDegs1.refine (); 400 bufDegs1.refine (); 401 401 if (bufDegs1.getLength() <= 1) 402 402 { 403 result.append (prodMod (T, M)); 403 result.append (prodMod (T, M)); 404 404 break; 405 405 } … … 410 410 adaptedLiftBound= d; 411 411 412 if (adaptedLiftBound < deg) 412 if (adaptedLiftBound < deg) 413 413 { 414 414 factors= T; … … 457 457 458 458 CFList biFactorizer (const CanonicalForm& F, const Variable& alpha, 459 CanonicalForm& bivarEval, int& liftBound) 459 CanonicalForm& bivarEval, int& liftBound) 460 460 { 461 461 CanonicalForm A= F; 462 462 bool GF= (CFFactory::gettype() == GaloisFieldDomain); 463 463 464 if (A.isUnivariate()) 464 if (A.isUnivariate()) 465 465 return uniFactorizer (F, alpha, GF); 466 466 467 467 468 468 CFMap N; … … 482 482 //trivial case 483 483 CFList factors; 484 if (A.inCoeffDomain()) 484 if (A.inCoeffDomain()) 485 485 { 486 486 append (factors, contentAyFactors); … … 489 489 return factors; 490 490 } 491 else if (A.isUnivariate()) 492 { 493 if (A.mvar() == x) 491 else if (A.isUnivariate()) 492 { 493 if (A.mvar() == x) 494 494 factors= uniFactorizer (A, alpha, GF); 495 495 append (factors, contentAyFactors); … … 503 503 DegreePattern degs; 504 504 DegreePattern bufDegs; 505 505 506 506 int factorNums= 5; 507 if (factorNums < (int) ceil (log (totaldegree (A)))) 507 if (factorNums < (int) ceil (log (totaldegree (A)))) 508 508 factorNums= (int) ceil (log (totaldegree (A))); 509 for (int i= 0; i < factorNums; i++) 510 { 511 if (i == 0) 509 for (int i= 0; i < factorNums; i++) 510 { 511 if (i == 0) 512 512 Aeval= A (bivarEval, y); 513 513 else if (i > 0 && contentAx.inCoeffDomain()) 514 514 { 515 Aeval= A; 515 Aeval= A; 516 516 evaluation= evalPoint (A, Aeval, alpha, list, GF, fail); 517 517 } 518 519 if (fail && (i != 0)) 518 519 if (fail && (i != 0)) 520 520 break; 521 521 … … 523 523 uniFactors= uniFactorizer (Aeval, alpha, GF); 524 524 525 if (uniFactors.length() == 1) 526 { 525 if (uniFactors.length() == 1) 526 { 527 527 append (factors, contentAyFactors); 528 528 if (contentAyFactors.isEmpty()) 529 529 factors.append (F/lc(F)); 530 else 530 else 531 531 { 532 532 A= A (y  bivarEval, y); … … 537 537 (void) extgcd (LC (A, 1), power (y, liftBound), s, t); 538 538 A *= s; 539 A= mod (A, power (y, liftBound)); 539 A= mod (A, power (y, liftBound)); 540 540 } 541 541 factors.append (A); 542 542 } 543 543 decompress (factors, N); 544 bivarEval= N (bivarEval); 544 bivarEval= N (bivarEval); 545 545 return factors; 546 546 } … … 549 549 degs= DegreePattern (uniFactors); 550 550 551 if (i == 0) 551 if (i == 0) 552 552 { 553 553 bufAeval= Aeval; … … 558 558 break; 559 559 } 560 else 561 { 562 bufDegs.intersect (degs); 563 if (uniFactors.length() < bufUniFactors.length()) 564 { 560 else 561 { 562 bufDegs.intersect (degs); 563 if (uniFactors.length() < bufUniFactors.length()) 564 { 565 565 bufUniFactors= uniFactors; 566 566 bufAeval= Aeval; … … 574 574 if (contentAyFactors.isEmpty()) 575 575 factors.append (F/lc(F)); 576 else 576 else 577 577 { 578 578 A= A (y  bivarEval, y); … … 583 583 (void) extgcd (LC (A, 1), power (y, liftBound), s, t); 584 584 A *= s; 585 A= mod (A, power (y, liftBound)); 585 A= mod (A, power (y, liftBound)); 586 586 } 587 587 factors.append (A); 588 588 } 589 589 decompress (factors, N); 590 bivarEval= N (bivarEval); 590 bivarEval= N (bivarEval); 591 591 return factors; 592 592 } … … 600 600 // Hensel lifting 601 601 CFList diophant; 602 CFMatrix M= CFMatrix (liftBound, bufUniFactors.length()  1); 602 CFMatrix M= CFMatrix (liftBound, bufUniFactors.length()  1); 603 603 CFArray Pi; 604 604 bool earlySuccess= false; … … 639 639 1, Pi, diophant, M); 640 640 earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound, 641 bufDegs, earlySuccess, 641 bufDegs, earlySuccess, 642 642 degree (A, y) + 1, liftBound); 643 643 if (bufDegs.getLength() > 1 && !earlySuccess) 644 644 { 645 646 645 if (newLiftBound > degree (A, y) + 1) 646 { 647 647 if (newLiftBound < newLiftBound) 648 649 650 648 liftBound= newLiftBound; 649 bufUniFactors.insert (LC(A, x)); 650 henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound, 651 651 Pi, diophant, M); 652 652 } 653 653 } 654 654 else if (earlySuccess) … … 667 667 factors= monicFactorRecombi (bufUniFactors, A, MODl, bufDegs); 668 668 669 if (earlySuccess) 669 if (earlySuccess) 670 670 factors= Union (earlyFactors, factors); 671 671 else if (!earlySuccess && bufDegs.getLength() == 1) … … 679 679 } 680 680 681 CFList 682 extFactorRecombination (const CFList& factors, const CanonicalForm& F, 683 const CFList& M, const ExtensionInfo& info, 681 CFList 682 extFactorRecombination (const CFList& factors, const CanonicalForm& F, 683 const CFList& M, const ExtensionInfo& info, 684 684 const CFList& evaluation) 685 { 685 { 686 686 Variable alpha= info.getAlpha(); 687 687 Variable beta= info.getBeta(); … … 690 690 int k= info.getGFDegree(); 691 691 CFList source, dest; 692 if (factors.length() == 1) 692 if (factors.length() == 1) 693 693 { 694 694 CanonicalForm buf= reverseShift (F, evaluation); 695 return CFList (mapDown (buf, info, source, dest)); 696 } 695 return CFList (mapDown (buf, info, source, dest)); 696 } 697 697 if (factors.length() < 1) 698 698 return CFList(); … … 711 711 CanonicalForm buf; 712 712 if (beta != Variable (1)) 713 buf= mapDown (F, gamma, delta, alpha, source, dest); 713 buf= mapDown (F, gamma, delta, alpha, source, dest); 714 714 else 715 715 buf= F; 716 716 717 CanonicalForm g, LCBuf= LC (buf, Variable (1)); 717 CanonicalForm g, LCBuf= LC (buf, Variable (1)); 718 718 CanonicalForm buf2; 719 719 int v [T.length()]; … … 723 723 CFArray TT; 724 724 int subsetDeg; 725 TT= copy (factors); 725 TT= copy (factors); 726 726 bool recombination= false; 727 while (T.length() >= 2*s) 728 { 729 while (noSubset == false) 730 { 731 if (T.length() == s) 727 while (T.length() >= 2*s) 728 { 729 while (noSubset == false) 730 { 731 if (T.length() == s) 732 732 { 733 733 if (recombination) … … 757 757 S.removeFirst(); 758 758 g /= myContent (g); 759 if (fdivides (g, buf)) 760 { 761 buf2= reverseShift (g, evaluation); 759 if (fdivides (g, buf)) 760 { 761 buf2= reverseShift (g, evaluation); 762 762 buf2 /= Lc (buf2); 763 if (!k && beta == Variable (1)) 764 765 766 { 767 768 769 770 771 772 773 else 774 775 776 777 778 779 780 781 782 783 784 785 if (T.length() < 2*s  T.length() == s) 786 787 763 if (!k && beta == Variable (1)) 764 { 765 if (degree (buf2, alpha) < degMipoBeta) 766 { 767 appendTestMapDown (result, buf2, info, source, dest); 768 buf /= g; 769 LCBuf= LC (buf, Variable (1)); 770 recombination= true; 771 } 772 } 773 else 774 { 775 if (!isInExtension (buf2, delta, k)) 776 { 777 appendTestMapDown (result, buf2, info, source, dest); 778 buf /= g; 779 LCBuf= LC (buf, Variable (1)); 780 recombination= true; 781 } 782 } 783 T= Difference (T, S); 784 785 if (T.length() < 2*s  T.length() == s) 786 { 787 buf= reverseShift (buf, evaluation); 788 788 buf /= Lc (buf); 789 790 return result; 791 792 793 794 if (noSubset) break; 789 appendTestMapDown (result, buf, info, source, dest); 790 return result; 791 } 792 TT= copy (T); 793 indexUpdate (v, s, T.length(), noSubset); 794 if (noSubset) break; 795 795 } 796 796 } 797 797 s++; 798 if (T.length() < 2*s  T.length() == s) 798 if (T.length() < 2*s  T.length() == s) 799 799 { 800 800 buf= reverseShift (buf, evaluation); … … 809 809 if (T.length() < 2*s) 810 810 { 811 buf= reverseShift (F, evaluation); 812 appendMapDown (result, buf, info, source, dest); 813 } 814 815 return result; 816 } 817 818 CFList 819 factorRecombination (const CanonicalForm& F, const CFList& factors, 811 buf= reverseShift (F, evaluation); 812 appendMapDown (result, buf, info, source, dest); 813 } 814 815 return result; 816 } 817 818 CFList 819 factorRecombination (const CanonicalForm& F, const CFList& factors, 820 820 const CFList& M) 821 821 { 822 if (factors.length() == 1) 822 if (factors.length() == 1) 823 823 return CFList(F); 824 824 if (factors.length() < 1) … … 839 839 CFArray TT; 840 840 int subsetDeg; 841 TT= copy (factors); 841 TT= copy (factors); 842 842 Variable y= F.level()  1; 843 843 bool recombination= false; 844 844 CanonicalForm h; 845 while (T.length() >= 2*s) 846 { 847 while (noSubset == false) 848 { 849 if (T.length() == s) 845 while (T.length() >= 2*s) 846 { 847 while (noSubset == false) 848 { 849 if (T.length() == s) 850 850 { 851 851 if (recombination) … … 872 872 LCBuf= LC (buf, Variable(1)); 873 873 T= Difference (T, S); 874 if (T.length() < 2*s  T.length() == s) 875 { 876 877 return result; 878 879 880 881 if (noSubset) break; 874 if (T.length() < 2*s  T.length() == s) 875 { 876 result.append (buf); 877 return result; 878 } 879 TT= copy (T); 880 indexUpdate (v, s, T.length(), noSubset); 881 if (noSubset) break; 882 882 } 883 883 } 884 884 s++; 885 if (T.length() < 2*s  T.length() == s) 885 if (T.length() < 2*s  T.length() == s) 886 886 { 887 887 result.append (buf); … … 893 893 noSubset= false; 894 894 } 895 if (T.length() < 2*s) 895 if (T.length() < 2*s) 896 896 result.append (F); 897 897 898 return result; 898 return result; 899 899 } 900 900 … … 913 913 int e= 0; 914 914 int nBuf; 915 for (CFListIterator i= factors; i.hasItem(); i++) 916 { 917 g= mulMod (i.getItem(), LCBuf, M); 915 for (CFListIterator i= factors; i.hasItem(); i++) 916 { 917 g= mulMod (i.getItem(), LCBuf, M); 918 918 g /= myContent (g); 919 919 if (fdivides (g, buf)) … … 923 923 e= tmax (e, nBuf); 924 924 buf /= g; 925 LCBuf= LC (buf, Variable (1)); 925 LCBuf= LC (buf, Variable (1)); 926 926 } 927 927 } 928 928 adaptedLiftBound= d; 929 929 930 if (adaptedLiftBound < deg) 931 { 930 if (adaptedLiftBound < deg) 931 { 932 932 if (adaptedLiftBound < degree (F) + 1) 933 933 { … … 939 939 success= false; 940 940 } 941 else 941 else 942 942 { 943 943 success= true; … … 951 951 { 952 952 success= true; 953 adaptedLiftBound= deg; 953 adaptedLiftBound= deg; 954 954 } 955 955 } … … 962 962 } 963 963 964 int 965 extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool& 966 success, const ExtensionInfo& info, const CFList& eval, 964 int 965 extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool& 966 success, const ExtensionInfo& info, const CFList& eval, 967 967 const int deg, const CFList& MOD, const int bound) 968 968 { … … 981 981 adaptedLiftBound= 0; 982 982 int d= bound; 983 int e= 0; 983 int e= 0; 984 984 int nBuf; 985 985 int degMipoBeta; … … 989 989 degMipoBeta= degree (getMipo (beta)); 990 990 991 for (CFListIterator i= factors; i.hasItem(); i++) 991 for (CFListIterator i= factors; i.hasItem(); i++) 992 992 { 993 993 g= mulMod (i.getItem(), LCBuf, M); … … 997 997 gg= reverseShift (g, eval); 998 998 gg /= Lc (gg); 999 if (!k && beta == Variable (1)) 999 if (!k && beta == Variable (1)) 1000 1000 { 1001 1001 if (degree (gg, alpha) < degMipoBeta) 1002 {1003 buf /= g;1004 nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);1005 d = nBuf;1006 e= tmax (e, nBuf);1007 LCBuf= LC (buf, Variable (1));1008 }1009 }1010 else1011 {1012 if (!isInExtension (gg, delta, k))1013 1002 { 1014 1003 buf /= g; … … 1019 1008 } 1020 1009 } 1021 } 1010 else 1011 { 1012 if (!isInExtension (gg, delta, k)) 1013 { 1014 buf /= g; 1015 nBuf= degree (g, y) + degree (LC (g, Variable (1)), y); 1016 d = nBuf; 1017 e= tmax (e, nBuf); 1018 LCBuf= LC (buf, Variable (1)); 1019 } 1020 } 1021 } 1022 1022 } 1023 1023 adaptedLiftBound= d; … … 1034 1034 success= false; 1035 1035 } 1036 else 1036 else 1037 1037 { 1038 1038 success= true; … … 1043 1043 } 1044 1044 } 1045 else 1045 else 1046 1046 { 1047 1047 success= true; 1048 adaptedLiftBound= deg; 1048 adaptedLiftBound= deg; 1049 1049 } 1050 1050 } … … 1058 1058 } 1059 1059 1060 CFList 1060 CFList 1061 1061 earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound, 1062 bool& success, const int deg, const CFList& MOD, 1062 bool& success, const int deg, const CFList& MOD, 1063 1063 const int bound) 1064 1064 { … … 1075 1075 int e= 0; 1076 1076 int nBuf; 1077 for (CFListIterator i= factors; i.hasItem(); i++) 1077 for (CFListIterator i= factors; i.hasItem(); i++) 1078 1078 { 1079 1079 g= mulMod (i.getItem(), LCBuf, M); … … 1086 1086 e= tmax (e, nBuf); 1087 1087 buf /= g; 1088 LCBuf= LC (buf, Variable (1)); 1088 LCBuf= LC (buf, Variable (1)); 1089 1089 T= Difference (T, CFList (i.getItem())); 1090 1090 } … … 1092 1092 adaptedLiftBound= d; 1093 1093 1094 if (adaptedLiftBound < deg) 1094 if (adaptedLiftBound < deg) 1095 1095 { 1096 1096 if (adaptedLiftBound < degree (F) + 1) … … 1099 1099 adaptedLiftBound= tmin (e + 1, deg); 1100 1100 else 1101 adaptedLiftBound= deg; 1101 adaptedLiftBound= deg; 1102 1102 } 1103 1103 factors= T; … … 1108 1108 } 1109 1109 1110 CFList 1110 CFList 1111 1111 extEarlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound, 1112 bool& success, const ExtensionInfo& info, const CFList& 1112 bool& success, const ExtensionInfo& info, const CFList& 1113 1113 eval, const int deg, const CFList& MOD, const int bound) 1114 1114 { … … 1138 1138 degMipoBeta= degree (getMipo (beta)); 1139 1139 1140 for (CFListIterator i= factors; i.hasItem(); i++) 1140 for (CFListIterator i= factors; i.hasItem(); i++) 1141 1141 { 1142 1142 g= mulMod (i.getItem(), LCBuf, M); … … 1146 1146 gg= reverseShift (g, eval); 1147 1147 gg /= Lc (gg); 1148 if (!k && beta == Variable (1)) 1148 if (!k && beta == Variable (1)) 1149 1149 { 1150 1150 if (degree (gg, alpha) < degMipoBeta) 1151 { 1151 { 1152 1152 appendTestMapDown (result, gg, info, source, dest); 1153 1153 buf /= g; … … 1155 1155 d = nBuf; 1156 1156 e= tmax (e, nBuf); 1157 LCBuf= LC (buf, Variable (1)); 1157 LCBuf= LC (buf, Variable (1)); 1158 1158 } 1159 1159 } 1160 else 1160 else 1161 1161 { 1162 1162 if (!isInExtension (gg, delta, k)) … … 1169 1169 LCBuf= LC (buf, Variable (1)); 1170 1170 } 1171 } 1171 } 1172 1172 T= Difference (T, CFList (i.getItem())); 1173 1173 } … … 1182 1182 adaptedLiftBound= tmin (e + 1, deg); 1183 1183 else 1184 adaptedLiftBound= deg; 1184 adaptedLiftBound= deg; 1185 1185 } 1186 1186 success= true; … … 1191 1191 } 1192 1192 1193 CFList 1193 CFList 1194 1194 evalPoints (const CanonicalForm& F, CFList & eval, const Variable& alpha, 1195 CFList& list, const bool& GF, bool& fail) 1196 { 1195 CFList& list, const bool& GF, bool& fail) 1196 { 1197 1197 int k= F.level()  1; 1198 1198 Variable x= Variable (1); … … 1201 1201 GFRandom genGF; 1202 1202 int p= getCharacteristic (); 1203 double bound; 1204 if (alpha != Variable (1)) 1203 double bound; 1204 if (alpha != Variable (1)) 1205 1205 { 1206 1206 bound= pow ((double) p, (double) degree (getMipo(alpha))); 1207 1207 bound= pow ((double) bound, (double) k); 1208 1208 } 1209 else if (GF) 1209 else if (GF) 1210 1210 { 1211 1211 bound= pow ((double) p, (double) getGFDegree()); … … 1217 1217 CanonicalForm random; 1218 1218 CanonicalForm deriv_x, gcd_deriv; 1219 do 1219 do 1220 1220 { 1221 1221 random= 0; 1222 1222 // possible overflow if list.length() does not fit into a int 1223 if (list.length() >= bound) 1224 { 1223 if (list.length() >= bound) 1224 { 1225 1225 fail= true; 1226 1226 break; 1227 1227 } 1228 for (int i= 0; i < k; i++) 1229 { 1230 if (GF) 1228 for (int i= 0; i < k; i++) 1229 { 1230 if (GF) 1231 1231 { 1232 1232 result.append (genGF.generate()); 1233 1233 random += result.getLast()*power (x, i); 1234 1234 } 1235 else if (alpha != Variable(1)) 1236 { 1235 else if (alpha != Variable(1)) 1236 { 1237 1237 AlgExtRandomF genAlgExt (alpha); 1238 1238 result.append (genAlgExt.generate()); 1239 random += result.getLast()*power (x, i); 1240 } 1241 else 1242 { 1239 random += result.getLast()*power (x, i); 1240 } 1241 else 1242 { 1243 1243 result.append (genFF.generate()); 1244 1244 random += result.getLast()*power (x, i); 1245 } 1246 } 1247 if (find (list, random)) 1245 } 1246 } 1247 if (find (list, random)) 1248 1248 { 1249 1249 result= CFList(); … … 1252 1252 int l= F.level(); 1253 1253 eval.insert (F); 1254 for (CFListIterator i= result; i.hasItem(); i++, l) 1254 for (CFListIterator i= result; i.hasItem(); i++, l) 1255 1255 eval.insert (eval.getFirst()(i.getItem(), l)); 1256 1256 1257 if (degree (eval.getFirst()) != degree (F, 1)) 1257 if (degree (eval.getFirst()) != degree (F, 1)) 1258 1258 { 1259 1259 if (!find (list, random)) … … 1262 1262 eval= CFList(); 1263 1263 continue; 1264 } 1265 1264 } 1265 1266 1266 deriv_x= deriv (eval.getFirst(), x); 1267 1267 gcd_deriv= gcd (eval.getFirst(), deriv_x); 1268 if (degree (gcd_deriv) > 0) 1269 { 1268 if (degree (gcd_deriv) > 0) 1269 { 1270 1270 if (!find (list, random)) 1271 1271 list.append (random); … … 1286 1286 } 1287 1287 1288 if (list.length() >= bound) 1288 if (list.length() >= bound) 1289 1289 { 1290 1290 fail= true; … … 1293 1293 } while (find (list, random)); 1294 1294 1295 if (!eval.isEmpty()) 1295 if (!eval.isEmpty()) 1296 1296 eval.removeFirst(); 1297 1297 … … 1299 1299 } 1300 1300 1301 static inline 1301 static inline 1302 1302 int newMainVariableSearch (CanonicalForm& A, CFList& Aeval, CFList& 1303 evaluation, const Variable& alpha, const int lev) 1304 { 1303 evaluation, const Variable& alpha, const int lev) 1304 { 1305 1305 Variable x= Variable (1); 1306 1306 CanonicalForm derivI, buf; … … 1312 1312 Aeval= CFList(); 1313 1313 evaluation= CFList(); 1314 for (int i= lev; i <= A.level(); i++) 1314 for (int i= lev; i <= A.level(); i++) 1315 1315 { 1316 1316 derivI= deriv (buf, Variable (i)); 1317 1317 if (!derivI.isZero()) 1318 1318 { 1319 buf= swapvar (buf, x, Variable (i)); 1319 buf= swapvar (buf, x, Variable (i)); 1320 1320 Aeval= CFList(); 1321 1321 evaluation= CFList(); 1322 1322 fail= false; 1323 1323 evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail); 1324 if (!fail) 1325 { 1326 1327 1328 1329 } 1330 else 1324 if (!fail) 1325 { 1326 A= buf; 1327 swapLevel= i; 1328 break; 1329 } 1330 else 1331 1331 buf= A; 1332 1332 } … … 1335 1335 } 1336 1336 1337 static inline 1338 CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi) 1337 static inline 1338 CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi) 1339 1339 { 1340 1340 int i= A.level(); 1341 1341 contentAi.append (myContent (A, i)); 1342 1342 contentAi.append (myContent (A, i  1)); 1343 CanonicalForm result= myLcm (contentAi.getFirst(), contentAi.getLast()); 1344 for (i= i  2; i > 0; i) 1343 CanonicalForm result= myLcm (contentAi.getFirst(), contentAi.getLast()); 1344 for (i= i  2; i > 0; i) 1345 1345 { 1346 1346 contentAi.append (content (A, i)); … … 1348 1348 } 1349 1349 return result; 1350 } 1351 1350 } 1351 1352 1352 CFList 1353 1353 henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool& 1354 1354 earlySuccess, CFList& earlyFactors, const CFList& Aeval, 1355 const CFList& biFactors, const CFList& evaluation, 1355 const CFList& biFactors, const CFList& evaluation, 1356 1356 const ExtensionInfo& info) 1357 1357 { 1358 1358 bool extension= info.isInExtension(); 1359 CFList bufFactors= biFactors; 1359 CFList bufFactors= biFactors; 1360 1360 bufFactors.insert (LC (Aeval.getFirst(), 1)); 1361 1361 … … 1365 1365 CFArray Pi; 1366 1366 int smallFactorDeg= 11; //tunable parameter 1367 CFList result; 1367 CFList result; 1368 1368 int newLiftBound= 0; 1369 1369 int adaptedLiftBound= 0; … … 1389 1389 { 1390 1390 if (!extension) 1391 earlyFactors= earlyFactorDetect 1391 earlyFactors= earlyFactorDetect 1392 1392 (buf, result, adaptedLiftBound, earlySuccess, 1393 1393 degree (buf) + 1, MOD, liftBound); 1394 1394 else 1395 earlyFactors= extEarlyFactorDetect 1395 earlyFactors= extEarlyFactorDetect 1396 1396 (buf, result, adaptedLiftBound, earlySuccess, 1397 info, evaluation, degree 1397 info, evaluation, degree 1398 1398 (buf) + 1, MOD, liftBound); 1399 1399 } … … 1406 1406 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info, 1407 1407 evaluation, degree (buf) + 1, 1408 MOD, liftBound); 1408 MOD, liftBound); 1409 1409 } 1410 1410 if (!earlySuccess) … … 1413 1413 liftBounds[1]= adaptedLiftBound; 1414 1414 liftBound= adaptedLiftBound; 1415 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1415 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1416 1416 Pi, diophant, Mat, MOD); 1417 } 1417 } 1418 1418 else 1419 1419 liftBounds[1]= adaptedLiftBound; … … 1426 1426 { 1427 1427 if (!extension) 1428 earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound, 1428 earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound, 1429 1429 earlySuccess, smallFactorDeg, MOD, 1430 1430 liftBound); 1431 else 1431 else 1432 1432 earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound, 1433 1433 earlySuccess, info, evaluation, … … 1441 1441 else 1442 1442 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info, 1443 evaluation, smallFactorDeg, MOD, 1443 evaluation, smallFactorDeg, MOD, 1444 1444 liftBound); 1445 1445 } … … 1448 1448 { 1449 1449 result.insert (LC (buf, 1)); 1450 henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1, 1450 henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1, 1451 1451 Pi, diophant, Mat, MOD); 1452 1452 if (Aeval.length() == 2) … … 1459 1459 earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound, 1460 1460 earlySuccess, info, evaluation, 1461 degree (buf) + 1, MOD, 1461 degree (buf) + 1, MOD, 1462 1462 liftBound); 1463 1463 } 1464 else 1464 else 1465 1465 { 1466 1466 if (!extension) 1467 1467 adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess, 1468 degree (buf) + 1, MOD,liftBound); 1468 degree (buf) + 1, MOD,liftBound); 1469 1469 else 1470 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, 1470 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, 1471 1471 info, evaluation, 1472 1472 degree (buf) + 1, MOD, … … 1478 1478 liftBounds[1]= adaptedLiftBound; 1479 1479 liftBound= adaptedLiftBound; 1480 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1480 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1481 1481 Pi, diophant, Mat, MOD); 1482 1482 } … … 1499 1499 int liftBoundsLength= Aeval.getLast().level()  1; 1500 1500 for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++) 1501 { 1501 { 1502 1502 earlySuccess= false; 1503 1503 result.insert (LC (bufEval.getFirst(), 1)); … … 1509 1509 if (smallFactorDeg >= liftBound) 1510 1510 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat, 1511 1511 liftBounds[i  1], liftBounds[i]); 1512 1512 else if (smallFactorDeg >= degree (buf) + 1) 1513 1513 { 1514 1515 1516 1517 1518 1519 1520 earlyFactors= earlyFactorDetect 1514 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat, 1515 liftBounds[i  1], degree (buf) + 1); 1516 1517 if (Aeval.length() == i + 1) 1518 { 1519 if (!extension) 1520 earlyFactors= earlyFactorDetect 1521 1521 (buf, result, adaptedLiftBound, earlySuccess, 1522 1522 degree (buf) + 1, MOD, liftBound); 1523 1524 earlyFactors= extEarlyFactorDetect 1523 else 1524 earlyFactors= extEarlyFactorDetect 1525 1525 (buf, result, adaptedLiftBound, earlySuccess, 1526 1526 info, evaluation, degree (buf) + 1, MOD, liftBound); 1527 1528 1529 1530 1531 adaptedLiftBound= liftBoundAdaption 1527 } 1528 else 1529 { 1530 if (!extension) 1531 adaptedLiftBound= liftBoundAdaption 1532 1532 (buf, result, earlySuccess, degree (buf) 1533 1533 + 1, MOD, liftBound); 1534 1535 adaptedLiftBound= extLiftBoundAdaption 1536 (buf, result, earlySuccess, info, evaluation, 1537 degree (buf) + 1, MOD, liftBound); 1538 1539 1540 1541 1542 1534 else 1535 adaptedLiftBound= extLiftBoundAdaption 1536 (buf, result, earlySuccess, info, evaluation, 1537 degree (buf) + 1, MOD, liftBound); 1538 } 1539 1540 if (!earlySuccess) 1541 { 1542 result.insert (LC (buf, 1)); 1543 1543 liftBounds[i]= adaptedLiftBound; 1544 1544 liftBound= adaptedLiftBound; 1545 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1546 1547 } 1548 1549 1550 1551 1545 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1546 Pi, diophant, Mat, MOD); 1547 } 1548 else 1549 { 1550 liftBounds[i]= adaptedLiftBound; 1551 } 1552 1552 } 1553 1553 else if (smallFactorDeg < degree (buf) + 1) 1554 1554 { 1555 1556 1557 1558 1559 1560 1561 earlyFactors= earlyFactorDetect 1555 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat, 1556 liftBounds[i  1], smallFactorDeg); 1557 1558 if (Aeval.length() == i + 1) 1559 { 1560 if (!extension) 1561 earlyFactors= earlyFactorDetect 1562 1562 (buf, result, adaptedLiftBound, earlySuccess, 1563 1563 smallFactorDeg, MOD, liftBound); 1564 1565 earlyFactors= extEarlyFactorDetect 1564 else 1565 earlyFactors= extEarlyFactorDetect 1566 1566 (buf, result, adaptedLiftBound, earlySuccess, 1567 1567 info, evaluation, smallFactorDeg, MOD, liftBound); 1568 1569 1570 1571 1572 adaptedLiftBound= liftBoundAdaption 1568 } 1569 else 1570 { 1571 if (!extension) 1572 adaptedLiftBound= liftBoundAdaption 1573 1573 (buf, result, earlySuccess, 1574 1574 smallFactorDeg, MOD, liftBound); 1575 1576 adaptedLiftBound= extLiftBoundAdaption 1575 else 1576 adaptedLiftBound= extLiftBoundAdaption 1577 1577 (buf, result, earlySuccess, info, evaluation, 1578 smallFactorDeg, MOD, liftBound); 1579 1580 1581 1582 1583 1584 henselLiftResume (buf, result, smallFactorDeg, 1578 smallFactorDeg, MOD, liftBound); 1579 } 1580 1581 if (!earlySuccess) 1582 { 1583 result.insert (LC (buf, 1)); 1584 henselLiftResume (buf, result, smallFactorDeg, 1585 1585 degree (buf) + 1, Pi, diophant, Mat, MOD); 1586 1587 1588 1589 earlyFactors= earlyFactorDetect 1586 if (Aeval.length() == i + 1) 1587 { 1588 if (!extension) 1589 earlyFactors= earlyFactorDetect 1590 1590 (buf, result, adaptedLiftBound, earlySuccess, 1591 1591 degree (buf) + 1, MOD, liftBound); 1592 1593 earlyFactors= extEarlyFactorDetect 1592 else 1593 earlyFactors= extEarlyFactorDetect 1594 1594 (buf, result, adaptedLiftBound, earlySuccess, 1595 info, evaluation, degree (buf) + 1, MOD, 1595 info, evaluation, degree (buf) + 1, MOD, 1596 1596 liftBound); 1597 1598 1599 1600 1601 adaptedLiftBound= liftBoundAdaption 1597 } 1598 else 1599 { 1600 if (!extension) 1601 adaptedLiftBound= liftBoundAdaption 1602 1602 (buf, result, earlySuccess, degree 1603 1603 (buf) + 1, MOD, liftBound); 1604 1605 adaptedLiftBound= extLiftBoundAdaption 1606 (buf, result, earlySuccess, info, evaluation, 1607 degree (buf) + 1, MOD, liftBound); 1608 1609 1610 1611 1612 1604 else 1605 adaptedLiftBound= extLiftBoundAdaption 1606 (buf, result, earlySuccess, info, evaluation, 1607 degree (buf) + 1, MOD, liftBound); 1608 } 1609 1610 if (!earlySuccess) 1611 { 1612 result.insert (LC (buf, 1)); 1613 1613 liftBounds[i]= adaptedLiftBound; 1614 1614 liftBound= adaptedLiftBound; 1615 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1616 1617 1618 1619 1620 1621 1622 1615 henselLiftResume (buf, result, degree (buf) + 1, liftBound, 1616 Pi, diophant, Mat, MOD); 1617 } 1618 else 1619 liftBounds[i]= adaptedLiftBound; 1620 } 1621 else 1622 liftBounds[i]= adaptedLiftBound; 1623 1623 } 1624 1624 MOD.append (power (Variable (i + 2), liftBounds[i])); … … 1635 1635 } 1636 1636 1637 CFList 1638 extFactorize (const CanonicalForm& F, const ExtensionInfo& info); 1639 1640 CFList 1641 multiFactorize (const CanonicalForm& F, const ExtensionInfo& info) 1637 CFList 1638 extFactorize (const CanonicalForm& F, const ExtensionInfo& info); 1639 1640 CFList 1641 multiFactorize (const CanonicalForm& F, const ExtensionInfo& info) 1642 1642 { 1643 1643 … … 1659 1659 bool GF= (CFFactory::gettype() == GaloisFieldDomain); 1660 1660 //univariate case 1661 if (F.isUnivariate()) 1661 if (F.isUnivariate()) 1662 1662 { 1663 1663 if (extension == false) 1664 1664 return uniFactorizer (F, alpha, GF); 1665 else 1666 { 1665 else 1666 { 1667 1667 CFList source, dest; 1668 1668 A= mapDown (F, info, source, dest); … … 1672 1672 1673 1673 //bivariate case 1674 if (A.level() == 2) 1675 { 1676 CFList buf= biFactorize (F, info); 1674 if (A.level() == 2) 1675 { 1676 CFList buf= biFactorize (F, info); 1677 1677 return buf; 1678 1678 } 1679 1679 1680 1680 Variable x= Variable (1); 1681 1681 Variable y= Variable (2); 1682 1682 1683 1683 // remove content 1684 1684 CFList contentAi; 1685 1685 CanonicalForm lcmCont= lcmContent (A, contentAi); 1686 A /= lcmCont; 1686 A /= lcmCont; 1687 1687 1688 1688 // trivial after content removal 1689 1689 CFList contentAFactors; 1690 if (A.inCoeffDomain()) 1691 { 1692 for (CFListIterator i= contentAi; i.hasItem(); i++) 1690 if (A.inCoeffDomain()) 1691 { 1692 for (CFListIterator i= contentAi; i.hasItem(); i++) 1693 1693 { 1694 1694 if (i.getItem().inCoeffDomain()) 1695 1695 continue; 1696 else 1696 else 1697 1697 { 1698 1698 lcmCont /= i.getItem(); 1699 contentAFactors= 1700 Union (multiFactorize (lcmCont, info), 1699 contentAFactors= 1700 Union (multiFactorize (lcmCont, info), 1701 1701 multiFactorize (i.getItem(), info)); 1702 1702 break; … … 1709 1709 1710 1710 // factorize content 1711 contentAFactors= multiFactorize (lcmCont, info); 1711 contentAFactors= multiFactorize (lcmCont, info); 1712 1712 1713 1713 // univariate after content removal 1714 1714 CFList factors; 1715 if (A.isUnivariate ()) 1715 if (A.isUnivariate ()) 1716 1716 { 1717 1717 factors= uniFactorizer (A, alpha, GF); … … 1728 1728 Variable z; 1729 1729 for (int i= 1; i <= A.level(); i++) 1730 { 1730 { 1731 1731 z= Variable (i); 1732 1732 derivZ= deriv (bufA, z); … … 1746 1746 } 1747 1747 if (GF) 1748 gcdDerivZ= GCD_GF (bufA, derivZ); 1748 gcdDerivZ= GCD_GF (bufA, derivZ); 1749 1749 else if (alpha == Variable (1)) 1750 1750 gcdDerivZ= GCD_small_p (bufA, derivZ); 1751 else 1751 else 1752 1752 gcdDerivZ= GCD_Fp_extension (bufA, derivZ, alpha); 1753 if (degree (gcdDerivZ) > 0 && !derivZ.isZero()) 1753 if (degree (gcdDerivZ) > 0 && !derivZ.isZero()) 1754 1754 { 1755 1755 CanonicalForm g= bufA/gcdDerivZ; 1756 CFList factorsG= 1756 CFList factorsG= 1757 1757 Union (multiFactorize (g, info), 1758 1758 multiFactorize (gcdDerivZ, info)); … … 1774 1774 CanonicalForm evalPoly; 1775 1775 int lift, bufLift; 1776 if (factorNums < (int) ceil (log (totaldegree (A)))) 1776 if (factorNums < (int) ceil (log (totaldegree (A)))) 1777 1777 factorNums= (int) ceil (log (totaldegree (A))); 1778 // several bivariate factorizations 1779 for (int i= 0; i < factorNums; i++) 1778 // several bivariate factorizations 1779 for (int i= 0; i < factorNums; i++) 1780 1780 { 1781 1781 bufA= A; 1782 1782 bufAeval= CFList(); 1783 1783 bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail); 1784 evalPoly= 0; 1785 1786 if (fail && (i == 0)) 1784 evalPoly= 0; 1785 1786 if (fail && (i == 0)) 1787 1787 { 1788 1788 if (!swapLevel) 1789 1790 else 1791 1789 level= 2; 1790 else 1791 level= swapLevel + 1; 1792 1792 1793 1793 swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level); 1794 1794 1795 1795 if (!swapLevel2) // need to pass to an extension 1796 { 1797 1798 1799 1800 1796 { 1797 factors= extFactorize (A, info); 1798 appendSwapDecompress (factors, contentAFactors, N, swapLevel, x); 1799 normalize (factors); 1800 return factors; 1801 1801 } 1802 1802 else … … 1805 1805 bufAeval= Aeval; 1806 1806 bufA= A; 1807 bufEvaluation= evaluation; 1807 bufEvaluation= evaluation; 1808 1808 } 1809 1809 } … … 1812 1812 1813 1813 bivarEval= bufEvaluation.getLast(); 1814 bufEvaluation.removeLast(); 1814 bufEvaluation.removeLast(); 1815 1815 1816 1816 bufLift= degree (A, y) + 1 + degree (LC(A, x), y); 1817 1817 1818 1818 TIMING_START (fac_bi_factorizer); 1819 bufBiFactors= biFactorizer (bufAeval.getFirst(), alpha, bivarEval, bufLift); 1820 TIMING_END_AND_PRINT (fac_bi_factorizer, 1821 1822 1823 if (bufBiFactors.length() == 1) 1824 { 1825 if (extension) 1826 { 1827 1828 1819 bufBiFactors= biFactorizer (bufAeval.getFirst(), alpha, bivarEval, bufLift); 1820 TIMING_END_AND_PRINT (fac_bi_factorizer, 1821 "time for bivariate factorization: "); 1822 1823 if (bufBiFactors.length() == 1) 1824 { 1825 if (extension) 1826 { 1827 CFList source, dest; 1828 A= mapDown (A, info, source, dest); 1829 1829 } 1830 1830 factors.append (A); 1831 1831 appendSwapDecompress (factors, contentAFactors, N, swapLevel, 1832 1832 swapLevel2, x); 1833 1833 normalize (factors); 1834 1834 return factors; … … 1845 1845 else 1846 1846 { 1847 if (bufBiFactors.length() < biFactors.length()  1847 if (bufBiFactors.length() < biFactors.length()  1848 1848 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length()))) 1849 1849 { … … 1857 1857 for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++) 1858 1858 evalPoly += j.getItem()*power (x, k); 1859 list.append (evalPoly); 1859 list.append (evalPoly); 1860 1860 } 1861 1861 … … 1866 1866 int liftBoundsLength= F.level()  1; 1867 1867 liftBounds= liftingBounds (A, lift); 1868 1868 1869 1869 CFList MOD; 1870 1870 bool earlySuccess; 1871 1871 CFList earlyFactors; 1872 1872 TIMING_START (fac_hensel_lift); 1873 CFList liftedFactors= henselLiftAndEarly 1873 CFList liftedFactors= henselLiftAndEarly 1874 1874 (A, MOD, liftBounds, earlySuccess, earlyFactors, 1875 1875 Aeval, biFactors, evaluation, info); 1876 1876 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); 1877 1877 1878 if (!extension) 1878 if (!extension) 1879 1879 { 1880 1880 TIMING_START (fac_factor_recombination); 1881 1881 factors= factorRecombination (A, liftedFactors, MOD); 1882 TIMING_END_AND_PRINT (fac_factor_recombination, 1882 TIMING_END_AND_PRINT (fac_factor_recombination, 1883 1883 "time for factor recombination: "); 1884 1884 } 1885 else 1885 else 1886 1886 { 1887 1887 TIMING_START (fac_factor_recombination); 1888 1888 factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation); 1889 TIMING_END_AND_PRINT (fac_factor_recombination, 1890 "time for factor recombination: "); 1889 TIMING_END_AND_PRINT (fac_factor_recombination, 1890 "time for factor recombination: "); 1891 1891 } 1892 1892 … … 1894 1894 factors= Union (factors, earlyFactors); 1895 1895 1896 if (!extension) 1896 if (!extension) 1897 1897 { 1898 1898 for (CFListIterator i= factors; i.hasItem(); i++) … … 1908 1908 } 1909 1909 1910 swap (factors, swapLevel, swapLevel2, x); 1910 swap (factors, swapLevel, swapLevel2, x); 1911 1911 append (factors, contentAFactors); 1912 1912 decompress (factors, N); … … 1919 1919 1920 1920 /// multivariate factorization over an extension of the initial field 1921 CFList 1922 extFactorize (const CanonicalForm& F, const ExtensionInfo& info) 1921 CFList 1922 extFactorize (const CanonicalForm& F, const ExtensionInfo& info) 1923 1923 { 1924 1924 CanonicalForm A= F; … … 1936 1936 { 1937 1937 CFList factors; 1938 bool extension= true; 1938 bool extension= true; 1939 1939 int p= getCharacteristic(); 1940 1940 if (p*p < (1<<16)) // pass to GF if possible 1941 { 1941 { 1942 1942 setCharacteristic (getCharacteristic(), 2, 'Z'); 1943 1943 ExtensionInfo info= ExtensionInfo (extension); … … 1947 1947 Variable vBuf= rootOf (gf_mipo); 1948 1948 setCharacteristic (getCharacteristic()); 1949 for (CFListIterator j= factors; j.hasItem(); j++) 1950 1949 for (CFListIterator j= factors; j.hasItem(); j++) 1950 j.getItem()= GF2FalphaRep (j.getItem(), vBuf); 1951 1951 } 1952 1952 else // not able to pass to GF, pass to F_p(\alpha) … … 1959 1959 } 1960 1960 else if (!GF && (alpha != w)) // we are in F_p(\alpha) 1961 { 1961 { 1962 1962 if (k == 1) // need factorization over F_p 1963 1963 { 1964 1964 int extDeg= degree (getMipo (alpha)); 1965 extDeg++; 1965 extDeg++; 1966 1966 CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1)); 1967 1967 Variable v= rootOf (mipo); … … 1969 1969 factors= biFactorize (A, info); 1970 1970 } 1971 else 1971 else 1972 1972 { 1973 1973 if (beta == Variable (1)) … … 1985 1985 1986 1986 CFList source, dest; 1987 CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem, 1987 CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem, 1988 1988 source, dest); 1989 1989 ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem); … … 2014 2014 } 2015 2015 else // we are in GF (p^k) 2016 { 2016 { 2017 2017 int p= getCharacteristic(); 2018 2018 int extensionDeg= getGFDegree(); 2019 2019 bool extension= true; 2020 2020 if (k == 1) // need factorization over F_p 2021 { 2021 { 2022 2022 extensionDeg++; 2023 if (pow ((double) p, (double) extensionDeg) < (1<<16)) 2023 if (pow ((double) p, (double) extensionDeg) < (1<<16)) 2024 2024 // pass to GF(p^k+1) 2025 { 2025 { 2026 2026 setCharacteristic (p); 2027 2028 2029 2027 Variable vBuf= rootOf (gf_mipo); 2028 A= GF2FalphaRep (A, vBuf); 2029 setCharacteristic (p, extensionDeg, 'Z'); 2030 2030 ExtensionInfo info= ExtensionInfo (extension); 2031 2031 factors= multiFactorize (A.mapinto(), info); 2032 2032 } 2033 2033 else // not able to pass to another GF, pass to F_p(\alpha) 2034 { 2035 2036 2037 2038 2034 { 2035 setCharacteristic (p); 2036 Variable vBuf= rootOf (gf_mipo); 2037 A= GF2FalphaRep (A, vBuf); 2038 Variable v= chooseExtension (A, beta); 2039 2039 ExtensionInfo info= ExtensionInfo (v, extension); 2040 2040 factors= multiFactorize (A, info); 2041 2041 } 2042 2042 } 2043 2043 else // need factorization over GF (p^k) 2044 2044 { 2045 if (pow ((double) p, (double) 2*extensionDeg) < (1<<16)) 2045 if (pow ((double) p, (double) 2*extensionDeg) < (1<<16)) 2046 2046 // pass to GF(p^2k) 2047 { 2048 2047 { 2048 setCharacteristic (p, 2*extensionDeg, 'Z'); 2049 2049 ExtensionInfo info= ExtensionInfo (k, cGFName, extension); 2050 factors= multiFactorize (GFMapUp (A, extensionDeg), info); 2051 2050 factors= multiFactorize (GFMapUp (A, extensionDeg), info); 2051 setCharacteristic (p, extensionDeg, cGFName); 2052 2052 } 2053 2053 else // not able to pass to GF (p^2k), pass to F_p (\alpha) 2054 { 2055 2056 2057 2058 Variable v2= chooseExtension (A, v1); 2054 { 2055 setCharacteristic (p); 2056 Variable v1= rootOf (gf_mipo); 2057 A= GF2FalphaRep (A, v1); 2058 Variable v2= chooseExtension (A, v1); 2059 2059 CanonicalForm primElem, imPrimElem; 2060 2060 bool primFail= false; … … 2070 2070 } 2071 2071 CFList source, dest; 2072 CanonicalForm bufA= mapUp (A, alpha, beta, primElem, imPrimElem, 2072 CanonicalForm bufA= mapUp (A, alpha, beta, primElem, imPrimElem, 2073 2073 source, dest); 2074 2074 ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem); 2075 factors= multiFactorize (bufA, info); 2076 2077 for (CFListIterator i= factors; i.hasItem(); i++) 2078 2075 factors= multiFactorize (bufA, info); 2076 setCharacteristic (p, k, cGFName); 2077 for (CFListIterator i= factors; i.hasItem(); i++) 2078 i.getItem()= Falpha2GFRep (i.getItem()); 2079 2079 } 2080 2080 }
Note: See TracChangeset
for help on using the changeset viewer.