Changeset 11bf82 in git
- Timestamp:
- May 24, 2011, 6:49:41 PM (12 years ago)
- Branches:
- (u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')
- Children:
- d19fa29f38b52d293cf6fcbe33a75284288cb5d3
- Parents:
- f876a663240524d1f86ed3519e45b68d1ae877b3
- Location:
- factory
- Files:
-
- 5 edited
-
facFqBivar.cc (modified) (44 diffs)
-
facFqBivar.h (modified) (3 diffs)
-
facFqFactorize.cc (modified) (5 diffs)
-
facHensel.cc (modified) (4 diffs)
-
facHensel.h (modified) (4 diffs)
Legend:
- Unmodified
- Added
- Removed
-
factory/facFqBivar.cc
rf876a66 r11bf82 33 33 #include "cf_map.h" 34 34 #include "cf_gcd_smallp.h" 35 #include "facFqBivarUtil.h" 35 36 #include "facFqBivar.h" 36 37 #include "cfNewtonPolygon.h" 37 38 38 39 #ifdef HAVE_NTL … … 91 92 bound= p; 92 93 94 random= 0; 93 95 do 94 96 { … … 101 103 random= 0; 102 104 else if (GF) 103 random= genGF.generate(); 104 else if (list.length() < p || alpha == x) 105 { 106 if (list.length() == 1) 107 random= getGFGenerator(); 108 else 109 random= genGF.generate(); 110 } 111 else if (list.length() < p || alpha.level() == 1) 105 112 random= genFF.generate(); 106 113 else if (alpha != x && list.length() >= p) 107 114 { 108 AlgExtRandomF genAlgExt (alpha); 109 random= genAlgExt.generate(); 115 if (list.length() == p) 116 random= alpha; 117 else 118 { 119 AlgExtRandomF genAlgExt (alpha); 120 random= genAlgExt.generate(); 121 } 110 122 } 111 123 if (find (list, random)) continue; … … 227 239 /// multivariate polynomials over a finite field" by L Bernardin. 228 240 CFList 229 extFactorRecombination ( const CFList& factors, constCanonicalForm& F,241 extFactorRecombination (CFList& factors, CanonicalForm& F, 230 242 const CanonicalForm& M, const ExtensionInfo& info, 231 const DegreePattern& degs, const CanonicalForm& eval) 243 DegreePattern& degs, const CanonicalForm& eval, int s, 244 int thres) 232 245 { 233 246 if (factors.length() == 0) 247 { 248 F= 1; 234 249 return CFList(); 250 } 235 251 236 252 Variable alpha= info.getAlpha(); … … 243 259 CFList source, dest; 244 260 if (degs.getLength() <= 1 || factors.length() == 1) 245 return CFList(mapDown (F(y-eval, y), info, source, dest)); 261 { 262 CFList result= CFList(mapDown (F(y-eval, y), info, source, dest)); 263 F= 1; 264 return result; 265 } 246 266 247 267 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " << … … 256 276 T= factors; 257 277 258 int s= 1;259 278 CFList result; 260 279 CanonicalForm buf, buf2; 261 if (beta != Variable (1)) 262 buf= mapDown (F, gamma, delta, alpha, source, dest); 263 else 264 buf= F; 280 281 buf= F; 265 282 266 283 CanonicalForm g, LCBuf= LC (buf, Variable (1)); … … 277 294 bool recombination= false; 278 295 bool trueFactor= false; 279 while (T.length() >= 2*s )296 while (T.length() >= 2*s && s <= thres) 280 297 { 281 298 while (nosubset == false) … … 293 310 g /= Lc (g); 294 311 appendTestMapDown (result, g, info, source, dest); 312 F= 1; 295 313 return result; 296 314 } … … 298 316 { 299 317 appendMapDown (result, F (y - eval, y), info, source, dest); 318 F= 1; 300 319 return result; 301 320 } … … 323 342 buf2 /= Lc (buf2); 324 343 325 if (!k && beta == Variable (1))344 if (!k && beta.level() == 1) 326 345 { 327 346 if (degree (buf2, alpha) < degMipoBeta) … … 360 379 appendTestMapDown (result, buf (y - eval, y), info, source, 361 380 dest); 381 F= 1; 362 382 return result; 363 383 } … … 365 385 { 366 386 appendMapDown (result, F (y - eval, y), info, source, dest); 387 F= 1; 367 388 return result; 368 389 } … … 384 405 { 385 406 appendTestMapDown (result, buf (y - eval, y), info, source, dest); 407 F= 1; 386 408 return result; 387 409 } … … 389 411 { 390 412 appendMapDown (result, F (y - eval, y), info, source, dest); 413 F= 1; 391 414 return result; 392 415 } … … 397 420 } 398 421 if (T.length() < 2*s) 422 { 399 423 appendMapDown (result, F (y - eval, y), info, source, dest); 424 F= 1; 425 delete [] v; 426 return result; 427 } 428 429 if (s > thres) 430 { 431 factors= T; 432 F= buf; 433 degs= bufDegs1; 434 } 400 435 401 436 delete [] v; … … 406 441 /// multivariate polynomials over a finite field" by L Bernardin. 407 442 CFList 408 factorRecombination (const CFList& factors, const CanonicalForm& F, 409 const CanonicalForm& M, const DegreePattern& degs) 443 factorRecombination (CFList& factors, CanonicalForm& F, 444 const CanonicalForm& M, DegreePattern& degs, int s, 445 int thres 446 ) 410 447 { 411 448 if (factors.length() == 0) 449 { 450 F= 1; 412 451 return CFList (); 452 } 413 453 if (degs.getLength() <= 1 || factors.length() == 1) 414 return CFList(F); 454 { 455 CFList result= CFList (F); 456 F= 1; 457 return result; 458 } 415 459 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " << 416 460 (LC (F, 1)*prodMod (factors, M) == F)); … … 418 462 419 463 T= factors; 420 int s= 1;421 464 CFList result; 422 465 CanonicalForm LCBuf= LC (F, Variable (1)); … … 432 475 TT= copy (factors); 433 476 bool recombination= false; 434 while (T.length() >= 2*s )477 while (T.length() >= 2*s && s <= thres) 435 478 { 436 479 while (nosubset == false) … … 445 488 T.removeFirst(); 446 489 result.append (g/content (g, Variable (1))); 490 F= 1; 447 491 return result; 448 492 } 449 493 else 450 return CFList (F); 494 { 495 result= CFList (F); 496 F= 1; 497 return result; 498 } 451 499 } 452 500 S= subset (v, s, TT, nosubset); … … 486 534 { 487 535 result.append (buf); 536 F= 1; 488 537 return result; 489 538 } 490 539 else 491 return CFList (F); 540 { 541 result= CFList (F); 542 F= 1; 543 return result; 544 } 492 545 } 493 546 TT= copy (T); … … 505 558 { 506 559 result.append (buf); 560 F= 1; 507 561 return result; 508 562 } 509 563 else 510 return CFList (F); 564 { 565 result= CFList (F); 566 F= 1; 567 return result; 568 } 511 569 } 512 570 for (int i= 0; i < T.length(); i++) … … 514 572 nosubset= false; 515 573 } 574 delete [] v; 516 575 if (T.length() < 2*s) 576 { 517 577 result.append (F); 518 519 delete [] v; 578 F= 1; 579 return result; 580 } 581 582 if (s > thres) 583 { 584 factors= T; 585 F= buf; 586 degs= bufDegs1; 587 } 588 520 589 return result; 521 590 } 522 591 523 Variable chooseExtension (const CanonicalForm & A, const Variable & alpha)592 Variable chooseExtension (const Variable & alpha, const Variable& beta, int k) 524 593 { 525 int p= getCharacteristic(); 526 ZZ NTLp= to_ZZ (p); 527 ZZ_p::init (NTLp); 528 ZZ_pX NTLirredpoly; 529 int d= degree (A); 530 int m= 1; 531 if (alpha != Variable (1)) 594 zz_p::init (getCharacteristic()); 595 zz_pX NTLIrredpoly; 596 int i, m; 597 // extension of F_p needed 598 if (alpha.level() == 1 && beta.level() == 1 && k == 1) 599 { 600 i= 1; 601 m= 2; 602 } //extension of F_p(alpha) needed but want to factorize over F_p 603 else if (alpha.level() != 1 && beta.level() == 1 && k == 1) 604 { 605 i= 1; 606 m= degree (getMipo (alpha)) + 1; 607 } //extension of F_p(alpha) needed for first time 608 else if (alpha.level() != 1 && beta.level() == 1 && k != 1) 609 { 610 i= 2; 532 611 m= degree (getMipo (alpha)); 533 int i= (int) floor((double) d/(double) m) - 1;534 if (i < 2)535 i= 2;536 if (i > 8)537 i= i/4;538 BuildIrred (NTLirredpoly, i*m);539 Variable x= A.mvar();540 CanonicalForm newMipo= convertNTL ZZpX2CF (NTLirredpoly, x);612 } 613 else if (alpha.level() != 1 && beta.level() != 1 && k != 1) 614 { 615 m= degree (getMipo (beta)); 616 i= degree (getMipo (alpha))/m + 1; 617 } 618 BuildIrred (NTLIrredpoly, i*m); 619 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1)); 541 620 return rootOf (newMipo); 542 621 } … … 555 634 CanonicalForm M= power (F.mvar(), deg); 556 635 adaptedLiftBound= 0; 557 int d; 558 if (degree (LCBuf) == degree (F)) 559 d= degree (F); 560 else 561 d= degree (F) + degree (LCBuf); 636 int d= degree (F) + degree (LCBuf); 562 637 for (CFListIterator i= factors; i.hasItem(); i++) 563 638 { … … 626 701 adaptedLiftBound= 0; 627 702 bool trueFactor= false; 628 int d; 629 if (degree (F) == degree (LCBuf)) 630 d= degree (F); 631 else 632 d= degree (F) + degree (LCBuf); 703 int d= degree (F) + degree (LCBuf); 633 704 CFList source, dest; 634 705 int degMipoBeta; … … 787 858 if (newLiftBound > degree (A, y) + 1) 788 859 { 789 if (newLiftBound < newLiftBound)790 liftBound= newLiftBound;791 860 bufUniFactors.insert (LC(A, x)); 792 861 henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound, … … 803 872 liftBound= newLiftBound; 804 873 return bufUniFactors; 874 } 875 876 long isReduced (const mat_zz_p& M) 877 { 878 long i, j, nonZero; 879 for (i = 1; i <= M.NumRows(); i++) 880 { 881 nonZero= 0; 882 for (j = 1; j <= M.NumCols(); j++) 883 { 884 if (!IsZero (M (i,j))) 885 nonZero++; 886 } 887 if (nonZero != 1) 888 return 0; 889 } 890 return 1; 891 } 892 893 long isReduced (const mat_zz_pE& M) 894 { 895 long i, j, nonZero; 896 for (i = 1; i <= M.NumRows(); i++) 897 { 898 nonZero= 0; 899 for (j = 1; j <= M.NumCols(); j++) 900 { 901 if (!IsZero (M (i,j))) 902 nonZero++; 903 } 904 if (nonZero != 1) 905 return 0; 906 } 907 return 1; 908 } 909 910 int * extractZeroOneVecs (const mat_zz_p& M) 911 { 912 long i, j; 913 bool nonZeroOne= false; 914 int * result= new int [M.NumCols()]; 915 for (i = 1; i <= M.NumCols(); i++) 916 { 917 for (j = 1; j <= M.NumRows(); j++) 918 { 919 if (!(IsOne (M (j,i)) || IsZero (M (j,i)))) 920 { 921 nonZeroOne= true; 922 break; 923 } 924 } 925 if (!nonZeroOne) 926 result [i - 1]= 1; 927 else 928 result [i - 1]= 0; 929 nonZeroOne= false; 930 } 931 return result; 932 } 933 934 int * extractZeroOneVecs (const mat_zz_pE& M) 935 { 936 long i, j; 937 bool nonZeroOne= false; 938 int * result= new int [M.NumCols()]; 939 for (i = 1; i <= M.NumCols(); i++) 940 { 941 for (j = 1; j <= M.NumRows(); j++) 942 { 943 if (!(IsOne (M (j,i)) || IsZero (M (j,i)))) 944 { 945 nonZeroOne= true; 946 break; 947 } 948 } 949 if (!nonZeroOne) 950 result [i - 1]= 1; 951 else 952 result [i - 1]= 0; 953 nonZeroOne= false; 954 } 955 return result; 956 } 957 958 void 959 reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList& 960 factors, const int liftBound, int& factorsFound, int*& 961 factorsFoundIndex, mat_zz_pE& N, bool beenInThres 962 ) 963 { 964 Variable y= Variable (2); 965 Variable x= Variable (1); 966 CanonicalForm yToL= power (y, liftBound); 967 for (long i= 1; i <= N.NumCols(); i++) 968 { 969 if (factorsFoundIndex [i - 1] == 1) 970 continue; 971 CFListIterator iter= factors; 972 CanonicalForm buf; 973 if (beenInThres) 974 { 975 int count= 1; 976 while (count < i) 977 { 978 count++; 979 iter++; 980 } 981 buf= iter.getItem(); 982 } 983 else 984 { 985 buf= 1; 986 for (long j= 1; j <= N.NumRows(); j++, iter++) 987 { 988 if (!IsZero (N (j,i))) 989 buf= mulMod2 (buf, iter.getItem(), yToL); 990 } 991 } 992 buf *= LC (F, x); 993 buf= mod (buf, yToL); 994 buf /= content (buf, x); 995 if (fdivides (buf, F)) 996 { 997 factorsFoundIndex[i - 1]= 1; 998 factorsFound++; 999 F /= buf; 1000 F /= Lc (F); 1001 reconstructedFactors.append (buf); 1002 } 1003 if (degree (F) <= 0) 1004 return; 1005 if (factorsFound + 1 == N.NumCols()) 1006 { 1007 reconstructedFactors.append (F); 1008 return; 1009 } 1010 } 1011 } 1012 1013 void 1014 reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList& 1015 factors, const int liftBound, int& factorsFound, int*& 1016 factorsFoundIndex, mat_zz_p& N, bool beenInThres 1017 ) 1018 { 1019 Variable y= Variable (2); 1020 Variable x= Variable (1); 1021 CanonicalForm yToL= power (y, liftBound); 1022 for (long i= 1; i <= N.NumCols(); i++) 1023 { 1024 if (factorsFoundIndex [i - 1] == 1) 1025 continue; 1026 CFListIterator iter= factors; 1027 CanonicalForm buf; 1028 if (beenInThres) 1029 { 1030 int count= 1; 1031 while (count < i) 1032 { 1033 count++; 1034 iter++; 1035 } 1036 buf= iter.getItem(); 1037 } 1038 else 1039 { 1040 buf= 1; 1041 for (long j= 1; j <= N.NumRows(); j++, iter++) 1042 { 1043 if (!IsZero (N (j,i))) 1044 buf= mulMod2 (buf, iter.getItem(), yToL); 1045 } 1046 } 1047 buf *= LC (F, x); 1048 buf= mod (buf, yToL); 1049 buf /= content (buf, x); 1050 if (fdivides (buf, F)) 1051 { 1052 factorsFoundIndex[i - 1]= 1; 1053 factorsFound++; 1054 F /= buf; 1055 F /= Lc (F); 1056 reconstructedFactors.append (buf); 1057 } 1058 if (degree (F) <= 0) 1059 return; 1060 if (factorsFound + 1 == N.NumCols()) 1061 { 1062 reconstructedFactors.append (F); 1063 return; 1064 } 1065 } 1066 } 1067 1068 CFList 1069 reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int 1070 precision, const mat_zz_pE& N 1071 ) 1072 { 1073 Variable y= Variable (2); 1074 Variable x= Variable (1); 1075 CanonicalForm F= G; 1076 CanonicalForm yToL= power (y, precision); 1077 CFList result; 1078 CFList bufFactors= factors; 1079 CFList factorsConsidered; 1080 for (long i= 1; i <= N.NumCols(); i++) 1081 { 1082 if (zeroOneVecs [i - 1] == 0) 1083 continue; 1084 CFListIterator iter= factors; 1085 CanonicalForm buf= 1; 1086 factorsConsidered= CFList(); 1087 for (long j= 1; j <= N.NumRows(); j++, iter++) 1088 { 1089 if (!IsZero (N (j,i))) 1090 { 1091 factorsConsidered.append (iter.getItem()); 1092 buf= mulMod2 (buf, iter.getItem(), yToL); 1093 } 1094 } 1095 buf *= LC (F, x); 1096 buf= mod (buf, yToL); 1097 buf /= content (buf, x); 1098 if (fdivides (buf, F)) 1099 { 1100 F /= buf; 1101 F /= Lc (F); 1102 result.append (buf); 1103 bufFactors= Difference (bufFactors, factorsConsidered); 1104 } 1105 if (degree (F) <= 0) 1106 { 1107 G= F; 1108 factors= bufFactors; 1109 return result; 1110 } 1111 } 1112 G= F; 1113 factors= bufFactors; 1114 return result; 1115 } 1116 1117 CFList 1118 monicReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, 1119 int precision, const mat_zz_pE& N 1120 ) 1121 { 1122 Variable y= Variable (2); 1123 Variable x= Variable (1); 1124 CanonicalForm F= G; 1125 CanonicalForm yToL= power (y, precision); 1126 CFList result; 1127 CFList bufFactors= factors; 1128 CFList factorsConsidered; 1129 for (long i= 1; i <= N.NumCols(); i++) 1130 { 1131 if (zeroOneVecs [i - 1] == 0) 1132 continue; 1133 CFListIterator iter= factors; 1134 CanonicalForm buf= 1; 1135 factorsConsidered= CFList(); 1136 for (long j= 1; j <= N.NumRows(); j++, iter++) 1137 { 1138 if (!IsZero (N (j,i))) 1139 { 1140 factorsConsidered.append (iter.getItem()); 1141 buf= mulMod2 (buf, iter.getItem(), yToL); 1142 } 1143 } 1144 CanonicalForm buf2= buf; 1145 buf *= LC (F, x); 1146 buf= mod (buf, yToL); 1147 buf /= content (buf, x); 1148 if (fdivides (buf, F)) 1149 { 1150 F /= buf; 1151 F /= Lc (F); 1152 result.append (buf2); 1153 bufFactors= Difference (bufFactors, factorsConsidered); 1154 } 1155 if (degree (F) <= 0) 1156 { 1157 G= F; 1158 factors= bufFactors; 1159 return result; 1160 } 1161 } 1162 G= F; 1163 factors= bufFactors; 1164 return result; 1165 } 1166 1167 CFList 1168 extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int 1169 precision, const mat_zz_p& N, const ExtensionInfo& info, 1170 const CanonicalForm& evaluation 1171 ) 1172 { 1173 Variable y= Variable (2); 1174 Variable x= Variable (1); 1175 Variable alpha= info.getAlpha(); 1176 Variable beta= info.getBeta(); 1177 int k= info.getGFDegree(); 1178 CanonicalForm gamma= info.getGamma(); 1179 CanonicalForm delta= info.getDelta(); 1180 CanonicalForm F= G; 1181 CanonicalForm yToL= power (y, precision); 1182 CFList result; 1183 CFList bufFactors= factors; 1184 CFList factorsConsidered; 1185 CanonicalForm buf2; 1186 for (long i= 1; i <= N.NumCols(); i++) 1187 { 1188 if (zeroOneVecs [i - 1] == 0) 1189 continue; 1190 CFListIterator iter= factors; 1191 CanonicalForm buf= 1; 1192 factorsConsidered= CFList(); 1193 for (long j= 1; j <= N.NumRows(); j++, iter++) 1194 { 1195 if (!IsZero (N (j,i))) 1196 { 1197 factorsConsidered.append (iter.getItem()); 1198 buf= mulMod2 (buf, iter.getItem(), yToL); 1199 } 1200 } 1201 buf *= LC (F, x); 1202 buf= mod (buf, yToL); 1203 buf /= content (buf, x); 1204 buf2= buf (y-evaluation, y); 1205 if (!k && beta == Variable (1)) 1206 { 1207 if (degree (buf2, alpha) < 1) 1208 { 1209 if (fdivides (buf, F)) 1210 { 1211 F /= buf; 1212 F /= Lc (F); 1213 result.append (buf2); 1214 bufFactors= Difference (bufFactors, factorsConsidered); 1215 } 1216 } 1217 } 1218 else 1219 { 1220 CFList source, dest; 1221 1222 if (!isInExtension (buf2, gamma, k, delta, source, dest)) 1223 { 1224 if (fdivides (buf, F)) 1225 { 1226 F /= buf; 1227 F /= Lc (F); 1228 result.append (buf2); 1229 bufFactors= Difference (bufFactors, factorsConsidered); 1230 } 1231 } 1232 } 1233 if (degree (F) <= 0) 1234 { 1235 G= F; 1236 factors= bufFactors; 1237 return result; 1238 } 1239 } 1240 G= F; 1241 factors= bufFactors; 1242 return result; 1243 } 1244 1245 CFList 1246 reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, 1247 int precision, const mat_zz_p& N) 1248 { 1249 Variable y= Variable (2); 1250 Variable x= Variable (1); 1251 CanonicalForm F= G; 1252 CanonicalForm yToL= power (y, precision); 1253 CFList result; 1254 CFList bufFactors= factors; 1255 CFList factorsConsidered; 1256 for (long i= 1; i <= N.NumCols(); i++) 1257 { 1258 if (zeroOneVecs [i - 1] == 0) 1259 continue; 1260 CFListIterator iter= factors; 1261 CanonicalForm buf= 1; 1262 factorsConsidered= CFList(); 1263 for (long j= 1; j <= N.NumRows(); j++, iter++) 1264 { 1265 if (!IsZero (N (j,i))) 1266 { 1267 factorsConsidered.append (iter.getItem()); 1268 buf= mulMod2 (buf, iter.getItem(), yToL); 1269 } 1270 } 1271 buf *= LC (F, x); 1272 buf= mod (buf, yToL); 1273 buf /= content (buf, x); 1274 if (fdivides (buf, F)) 1275 { 1276 F /= buf; 1277 F /= Lc (F); 1278 result.append (buf); 1279 bufFactors= Difference (bufFactors, factorsConsidered); 1280 } 1281 if (degree (F) <= 0) 1282 { 1283 G= F; 1284 factors= bufFactors; 1285 return result; 1286 } 1287 } 1288 G= F; 1289 factors= bufFactors; 1290 return result; 1291 } 1292 1293 void 1294 extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const 1295 CFList& factors, const int liftBound, int& factorsFound, 1296 int*& factorsFoundIndex, mat_zz_p& N, bool beenInThres, 1297 const ExtensionInfo& info, const CanonicalForm& evaluation 1298 ) 1299 { 1300 Variable y= Variable (2); 1301 Variable x= Variable (1); 1302 Variable alpha= info.getAlpha(); 1303 Variable beta= info.getBeta(); 1304 int k= info.getGFDegree(); 1305 CanonicalForm gamma= info.getGamma(); 1306 CanonicalForm delta= info.getDelta(); 1307 CanonicalForm yToL= power (y, liftBound); 1308 CFList source, dest; 1309 for (long i= 1; i <= N.NumCols(); i++) 1310 { 1311 if (factorsFoundIndex [i - 1] == 1) 1312 continue; 1313 CFListIterator iter= factors; 1314 CanonicalForm buf; 1315 CanonicalForm buf2; 1316 if (beenInThres) 1317 { 1318 int count= 1; 1319 while (count < i) 1320 { 1321 count++; 1322 iter++; 1323 } 1324 buf= iter.getItem(); 1325 } 1326 else 1327 { 1328 buf= 1; 1329 for (long j= 1; j <= N.NumRows(); j++, iter++) 1330 { 1331 if (!IsZero (N (j,i))) 1332 buf= mulMod2 (buf, iter.getItem(), yToL); 1333 } 1334 } 1335 buf *= LC (F, x); 1336 buf= mod (buf, yToL); 1337 buf /= content (buf, x); 1338 buf2= buf (y - evaluation, y); 1339 if (!k && beta == Variable (1)) 1340 { 1341 if (degree (buf2, alpha) < 1) 1342 { 1343 if (fdivides (buf, F)) 1344 { 1345 factorsFoundIndex[i - 1]= 1; 1346 factorsFound++; 1347 F /= buf; 1348 F /= Lc (F); 1349 buf2= mapDown (buf2, info, source, dest); 1350 reconstructedFactors.append (buf2); 1351 } 1352 } 1353 } 1354 else 1355 { 1356 CFList source, dest; 1357 if (!isInExtension (buf2, gamma, k, delta, source, dest)) 1358 { 1359 if (fdivides (buf, F)) 1360 { 1361 factorsFoundIndex[i - 1]= 1; 1362 factorsFound++; 1363 F /= buf; 1364 F /= Lc (F); 1365 buf2= mapDown (buf2, info, source, dest); 1366 reconstructedFactors.append (buf2); 1367 } 1368 } 1369 } 1370 if (degree (F) <= 0) 1371 return; 1372 if (factorsFound + 1 == N.NumCols()) 1373 { 1374 CanonicalForm tmp= F (y - evaluation, y); 1375 tmp= mapDown (tmp, info, source, dest); 1376 reconstructedFactors.append (tmp); 1377 return; 1378 } 1379 } 1380 } 1381 1382 //over Fp 1383 int 1384 liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int 1385 start, int liftBound, int minBound, CFList& factors, 1386 mat_zz_p& NTLN, CFList& diophant, CFMatrix& M, CFArray& 1387 Pi, CFArray& bufQ, bool& irreducible 1388 ) 1389 { 1390 CanonicalForm LCF= LC (F, 1); 1391 CFArray *A= new CFArray [factors.length() - 1]; 1392 bool wasInBounds= false; 1393 bool hitBound= false; 1394 int l= (minBound+1)*2; 1395 int stepSize= 2; 1396 int oldL= l/2; 1397 bool reduced= false; 1398 while (l <= liftBound) 1399 { 1400 1401 if (start) 1402 { 1403 henselLiftResume12 (F, factors, start, l, Pi, diophant, M); 1404 start= 0; 1405 } 1406 else 1407 { 1408 if (wasInBounds) 1409 henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M); 1410 else 1411 henselLift12 (F, factors, l, Pi, diophant, M); 1412 } 1413 1414 factors.insert (LCF); 1415 CFListIterator j= factors; 1416 j++; 1417 1418 for (int i= 0; i < factors.length() - 1; i++, j++) 1419 { 1420 if (!wasInBounds) 1421 { 1422 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ[i]); 1423 } 1424 else 1425 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i], bufQ[i]); 1426 } 1427 1428 for (int i= 0; i < sizeBounds; i++) 1429 { 1430 if (bounds [i] + 1 <= l/2) 1431 { 1432 wasInBounds= true; 1433 int k= tmin (bounds [i] + 1, l/2); 1434 CFMatrix C= CFMatrix (l - k, factors.length() - 1); 1435 for (int ii= 0; ii < factors.length() - 1; ii++) 1436 { 1437 CFArray buf; 1438 if (A[ii].size() - 1 >= i) 1439 buf= getCoeffs (A[ii] [i], k); 1440 writeInMatrix (C, buf, ii + 1, 0); 1441 } 1442 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 1443 mat_zz_p NTLK= (*NTLC)*NTLN; 1444 transpose (NTLK, NTLK); 1445 kernel (NTLK, NTLK); 1446 transpose (NTLK, NTLK); 1447 NTLN *= NTLK; 1448 1449 if (NTLN.NumCols() == 1) 1450 { 1451 irreducible= true; 1452 break; 1453 } 1454 if (isReduced (NTLN)) 1455 { 1456 reduced= true; 1457 break; 1458 } 1459 } 1460 } 1461 1462 if (irreducible) 1463 break; 1464 if (reduced) 1465 break; 1466 oldL= l; 1467 l += stepSize; 1468 stepSize *= 2; 1469 if (l > liftBound) 1470 { 1471 if (!hitBound) 1472 { 1473 l= liftBound; 1474 hitBound= true; 1475 } 1476 else 1477 break; 1478 } 1479 } 1480 delete [] A; 1481 return l; 1482 } 1483 1484 //over field extension 1485 int 1486 extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, 1487 int liftBound, int minBound, int start, CFList& 1488 factors, mat_zz_p& NTLN, CFList& diophant, 1489 CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool& 1490 irreducible, const CanonicalForm& evaluation, const 1491 ExtensionInfo& info, CFList& source, CFList& dest 1492 ) 1493 { 1494 bool GF= (CFFactory::gettype()==GaloisFieldDomain); 1495 CanonicalForm LCF= LC (F, 1); 1496 CFArray *A= new CFArray [factors.length() - 1]; 1497 bool wasInBounds= false; 1498 bool hitBound= false; 1499 int degMipo; 1500 Variable alpha; 1501 alpha= info.getAlpha(); 1502 degMipo= degree (getMipo (alpha)); 1503 1504 Variable gamma= info.getBeta(); 1505 CanonicalForm primElemAlpha= info.getGamma(); 1506 CanonicalForm imPrimElemAlpha= info.getDelta(); 1507 1508 int stepSize= 2; 1509 int l= ((minBound+1)/degMipo+1)*2; 1510 l= tmax (l, 2); 1511 if (start > l) 1512 l= start; 1513 int oldL= l/2; 1514 bool reduced= false; 1515 while (l <= liftBound) 1516 { 1517 if (start) 1518 { 1519 henselLiftResume12 (F, factors, start, l, Pi, diophant, M); 1520 start= 0; 1521 } 1522 else 1523 { 1524 if (wasInBounds) 1525 henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M); 1526 else 1527 henselLift12 (F, factors, l, Pi, diophant, M); 1528 } 1529 1530 Variable y= F.mvar(); 1531 Variable x= Variable (1); 1532 1533 factors.insert (LCF); 1534 1535 if (GF) 1536 setCharacteristic (getCharacteristic()); 1537 1538 CanonicalForm powX= power (y-gamma, l); 1539 CFMatrix Mat= CFMatrix (l*degMipo, l*degMipo); 1540 for (int i= 0; i < l*degMipo; i++) 1541 { 1542 1543 CanonicalForm imBasis= mod (power (y, i), powX); 1544 imBasis= imBasis (power (y, degMipo), y); 1545 imBasis= imBasis (y, gamma); 1546 CFIterator iter= imBasis; 1547 for (; iter.hasTerms(); iter++) 1548 Mat (iter.exp()+ 1, i+1)= iter.coeff(); 1549 } 1550 1551 mat_zz_p* NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat); 1552 *NTLMat= inv (*NTLMat); 1553 1554 if (GF) 1555 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 1556 1557 CFListIterator j= factors; 1558 j++; 1559 1560 for (int i= 0; i < factors.length() - 1; i++, j++) 1561 { 1562 if (!wasInBounds) 1563 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ[i]); 1564 else 1565 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i], bufQ[i]); 1566 } 1567 1568 for (int i= 0; i < sizeBounds; i++) 1569 { 1570 if (bounds [i] + 1 <= (l/2)*degMipo) 1571 { 1572 wasInBounds= true; 1573 int k= tmin (bounds [i] + 1, (l/2)*degMipo); 1574 CFMatrix C= CFMatrix (l*degMipo - k, factors.length() - 1); 1575 1576 for (int ii= 0; ii < factors.length() - 1; ii++) 1577 { 1578 CFArray buf; 1579 if (A[ii].size() - 1 >= i) 1580 { 1581 if (GF) 1582 { 1583 A [ii] [i]= A [ii] [i] (y-evaluation, y); 1584 setCharacteristic (getCharacteristic()); 1585 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha); 1586 if (alpha != gamma) 1587 A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 1588 gamma, source, dest 1589 ); 1590 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat); 1591 } 1592 else 1593 { 1594 A [ii] [i]= A [ii] [i] (y-evaluation, y); 1595 if (alpha != gamma) 1596 A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 1597 gamma, source, dest 1598 ); 1599 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat); 1600 } 1601 } 1602 writeInMatrix (C, buf, ii + 1, 0); 1603 if (GF) 1604 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 1605 } 1606 1607 if (GF) 1608 setCharacteristic(getCharacteristic()); 1609 1610 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 1611 mat_zz_p NTLK= (*NTLC)*NTLN; 1612 transpose (NTLK, NTLK); 1613 kernel (NTLK, NTLK); 1614 transpose (NTLK, NTLK); 1615 NTLN *= NTLK; 1616 1617 if (GF) 1618 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 1619 1620 if (NTLN.NumCols() == 1) 1621 { 1622 irreducible= true; 1623 break; 1624 } 1625 if (isReduced (NTLN)) 1626 { 1627 reduced= true; 1628 break; 1629 } 1630 } 1631 } 1632 1633 if (NTLN.NumCols() == 1) 1634 { 1635 irreducible= true; 1636 break; 1637 } 1638 if (reduced) 1639 break; 1640 oldL= l; 1641 l += stepSize; 1642 stepSize *= 2; 1643 if (l > liftBound) 1644 { 1645 if (!hitBound) 1646 { 1647 l= liftBound; 1648 hitBound= true; 1649 } 1650 else 1651 break; 1652 } 1653 } 1654 delete [] A; 1655 return l; 1656 } 1657 1658 // over Fq 1659 int 1660 liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, 1661 int start, int liftBound, int minBound, CFList& factors, 1662 mat_zz_pE& NTLN, CFList& diophant, CFMatrix& M, CFArray& 1663 Pi, CFArray& bufQ, bool& irreducible 1664 ) 1665 { 1666 bool GF= (CFFactory::gettype () == GaloisFieldDomain); 1667 CanonicalForm LCF= LC (F, 1); 1668 CFArray *A= new CFArray [factors.length() - 1]; 1669 bool wasInBounds= false; 1670 bool hitBound= false; 1671 int l= (minBound+1)*2; 1672 int stepSize= 2; 1673 int oldL= l/2; 1674 bool reduced= false; 1675 while (l <= liftBound) 1676 { 1677 if (start) 1678 { 1679 henselLiftResume12 (F, factors, start, l, Pi, diophant, M); 1680 start= 0; 1681 } 1682 else 1683 { 1684 if (wasInBounds) 1685 henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M); 1686 else 1687 henselLift12 (F, factors, l, Pi, diophant, M); 1688 } 1689 1690 factors.insert (LCF); 1691 CFListIterator j= factors; 1692 j++; 1693 1694 for (int i= 0; i < factors.length() - 1; i++, j++) 1695 { 1696 if (l == (minBound+1)*2) 1697 { 1698 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ[i]); 1699 } 1700 else 1701 { 1702 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i], 1703 bufQ[i] 1704 ); 1705 } 1706 } 1707 1708 for (int i= 0; i < sizeBounds; i++) 1709 { 1710 if (bounds [i] + 1 <= l/2) 1711 { 1712 wasInBounds= true; 1713 int k= tmin (bounds [i] + 1, l/2); 1714 CFMatrix C= CFMatrix (l - k, factors.length() - 1); 1715 for (int ii= 0; ii < factors.length() - 1; ii++) 1716 { 1717 CFArray buf; 1718 if (A[ii].size() - 1 >= i) 1719 buf= getCoeffs (A[ii] [i], k); 1720 writeInMatrix (C, buf, ii + 1, 0); 1721 } 1722 1723 mat_zz_pE* NTLC= convertFacCFMatrix2NTLmat_zz_pE(C); 1724 mat_zz_pE NTLK= (*NTLC)*NTLN; 1725 transpose (NTLK, NTLK); 1726 kernel (NTLK, NTLK); 1727 transpose (NTLK, NTLK); 1728 NTLN *= NTLK; 1729 1730 if (NTLN.NumCols() == 1) 1731 { 1732 irreducible= true; 1733 break; 1734 } 1735 if (isReduced (NTLN)) 1736 { 1737 reduced= true; 1738 break; 1739 } 1740 } 1741 } 1742 1743 if (NTLN.NumCols() == 1) 1744 { 1745 irreducible= true; 1746 break; 1747 } 1748 if (reduced) 1749 break; 1750 oldL= l; 1751 l += stepSize; 1752 stepSize *= 2; 1753 if (l > liftBound) 1754 { 1755 if (!hitBound) 1756 { 1757 l= liftBound; 1758 hitBound= true; 1759 } 1760 else 1761 break; 1762 } 1763 } 1764 delete [] A; 1765 return l; 1766 } 1767 1768 int 1769 liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds, 1770 int start, int liftBound, int minBound, CFList& 1771 factors, mat_zz_p& NTLN, CFList& diophant, CFMatrix& 1772 M, CFArray& Pi, CFArray& bufQ, bool& irreducible, 1773 const Variable& alpha 1774 ) 1775 { 1776 bool GF= (CFFactory::gettype () == GaloisFieldDomain); 1777 CanonicalForm LCF= LC (F, 1); 1778 CFArray *A= new CFArray [factors.length() - 1]; 1779 bool wasInBounds= false; 1780 int l= (minBound+1)*2; 1781 int oldL= l/2; 1782 int stepSize= 2; 1783 bool hitBound= false; 1784 int extensionDeg= degree (getMipo (alpha)); 1785 bool reduced= false; 1786 while (l <= liftBound) 1787 { 1788 if (start) 1789 { 1790 henselLiftResume12 (F, factors, start, l, Pi, diophant, M); 1791 start= 0; 1792 } 1793 else 1794 { 1795 if (wasInBounds) 1796 henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M); 1797 else 1798 henselLift12 (F, factors, l, Pi, diophant, M); 1799 } 1800 1801 factors.insert (LCF); 1802 CFListIterator j= factors; 1803 j++; 1804 1805 for (int i= 0; i < factors.length() - 1; i++, j++) 1806 { 1807 if (l == (minBound+1)*2) 1808 { 1809 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ[i]); 1810 } 1811 else 1812 { 1813 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i], 1814 bufQ[i] 1815 ); 1816 } 1817 } 1818 1819 for (int i= 0; i < sizeBounds; i++) 1820 { 1821 if (bounds [i] + 1 <= l/2) 1822 { 1823 wasInBounds= true; 1824 int k= tmin (bounds [i] + 1, l/2); 1825 CFMatrix C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1); 1826 for (int ii= 0; ii < factors.length() - 1; ii++) 1827 { 1828 CFArray buf; 1829 if (A[ii].size() - 1 >= i) 1830 buf= getCoeffs (A[ii] [i], k, alpha); 1831 writeInMatrix (C, buf, ii + 1, 0); 1832 } 1833 1834 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 1835 mat_zz_p NTLK= (*NTLC)*NTLN; 1836 transpose (NTLK, NTLK); 1837 kernel (NTLK, NTLK); 1838 transpose (NTLK, NTLK); 1839 NTLN *= NTLK; 1840 1841 if (NTLN.NumCols() == 1) 1842 { 1843 irreducible= true; 1844 break; 1845 } 1846 if (isReduced (NTLN)) 1847 { 1848 reduced= true; 1849 break; 1850 } 1851 } 1852 } 1853 1854 if (NTLN.NumCols() == 1) 1855 { 1856 irreducible= true; 1857 break; 1858 } 1859 if (reduced) 1860 break; 1861 oldL= l; 1862 l += stepSize; 1863 stepSize *= 2; 1864 if (l > liftBound) 1865 { 1866 if (!hitBound) 1867 { 1868 l= liftBound; 1869 hitBound= true; 1870 } 1871 else 1872 break; 1873 } 1874 } 1875 delete [] A; 1876 return l; 1877 } 1878 1879 CFList 1880 increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound, 1881 int oldNumCols, int oldL, int precision 1882 ) 1883 { 1884 bool irreducible= false; 1885 int d; 1886 int* bounds= computeBounds (F, d); 1887 CFArray * A= new CFArray [factors.length()]; 1888 CFArray bufQ= CFArray (factors.length()); 1889 mat_zz_p NTLN; 1890 ident (NTLN, factors.length()); 1891 int minBound= bounds[0]; 1892 for (int i= 1; i < d; i++) 1893 { 1894 if (bounds[i] != 0) 1895 minBound= tmin (minBound, bounds[i]); 1896 } 1897 int l= tmax (2*(minBound + 1), oldL); 1898 int oldL2= l/2; 1899 int stepSize= 2; 1900 bool useOldQs= false; 1901 bool hitBound= false; 1902 while (l <= precision) 1903 { 1904 CFListIterator j= factors; 1905 if (useOldQs) 1906 { 1907 for (int i= 0; i < factors.length(); i++, j++) 1908 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL2, bufQ[i], 1909 bufQ[i] 1910 ); 1911 } 1912 else 1913 { 1914 for (int i= 0; i < factors.length(); i++, j++) 1915 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 1916 } 1917 useOldQs= true; 1918 for (int i= 0; i < d; i++) 1919 { 1920 if (bounds [i] + 1 <= l/2) 1921 { 1922 int k= tmin (bounds [i] + 1, l/2); 1923 CFMatrix C= CFMatrix (l - k, factors.length()); 1924 for (int ii= 0; ii < factors.length(); ii++) 1925 { 1926 CFArray buf; 1927 if (A[ii].size() - 1 >= i) 1928 buf= getCoeffs (A[ii] [i], k); 1929 writeInMatrix (C, buf, ii + 1, 0); 1930 } 1931 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 1932 mat_zz_p NTLK= (*NTLC)*NTLN; 1933 transpose (NTLK, NTLK); 1934 kernel (NTLK, NTLK); 1935 transpose (NTLK, NTLK); 1936 NTLN *= NTLK; 1937 if (NTLN.NumCols() == 1) 1938 { 1939 irreducible= true; 1940 delete [] A; 1941 delete [] bounds; 1942 CanonicalForm G= F; 1943 F= 1; 1944 return CFList (G); 1945 } 1946 } 1947 } 1948 1949 if (NTLN.NumCols() < oldNumCols - factorsFound) 1950 { 1951 if (isReduced (NTLN)) 1952 { 1953 int d= degree (F) + 1; 1954 int * factorsFoundIndex= new int [NTLN.NumCols()]; 1955 for (long i= 0; i < NTLN.NumCols(); i++) 1956 factorsFoundIndex[i]= 0; 1957 int factorsFound2= 0; 1958 CFList result; 1959 CanonicalForm bufF= F; 1960 reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2, 1961 factorsFoundIndex, NTLN, false 1962 ); 1963 F= bufF; 1964 if (result.length() > 0) 1965 { 1966 delete [] factorsFoundIndex; 1967 delete [] A; 1968 delete [] bounds; 1969 return result; 1970 } 1971 delete [] factorsFoundIndex; 1972 } 1973 else if (l == precision) 1974 { 1975 CanonicalForm bufF= F; 1976 int * zeroOne= extractZeroOneVecs (NTLN); 1977 CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN); 1978 F= bufF; 1979 delete [] zeroOne; 1980 delete [] A; 1981 delete [] bounds; 1982 return result; 1983 } 1984 } 1985 oldL2= l; 1986 l += stepSize; 1987 stepSize *= 2; 1988 if (l > precision) 1989 { 1990 if (!hitBound) 1991 { 1992 l= precision; 1993 hitBound= true; 1994 } 1995 else 1996 break; 1997 } 1998 } 1999 delete [] bounds; 2000 delete [] A; 2001 return CFList(); 2002 } 2003 2004 CFList 2005 increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound, 2006 int oldNumCols, int oldL, const Variable& alpha, 2007 int precision 2008 ) 2009 { 2010 bool irreducible= false; 2011 int d; 2012 int* bounds= computeBounds (F, d); 2013 CFArray * A= new CFArray [factors.length()]; 2014 CFArray bufQ= CFArray (factors.length()); 2015 mat_zz_pE NTLN; 2016 ident (NTLN, factors.length()); 2017 int minBound= bounds[0]; 2018 for (int i= 1; i < d; i++) 2019 { 2020 if (bounds[i] != 0) 2021 minBound= tmin (minBound, bounds[i]); 2022 } 2023 int l= tmax (2*(minBound + 1), oldL); 2024 int oldL2= l/2; 2025 int stepSize= 2; 2026 bool useOldQs= false; 2027 bool hitBound= false; 2028 while (l <= precision) 2029 { 2030 CFListIterator j= factors; 2031 if (useOldQs) 2032 { 2033 for (int i= 0; i < factors.length(); i++, j++) 2034 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL2, bufQ[i], 2035 bufQ[i] 2036 ); 2037 } 2038 else 2039 { 2040 for (int i= 0; i < factors.length(); i++, j++) 2041 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 2042 } 2043 useOldQs= true; 2044 for (int i= 0; i < d; i++) 2045 { 2046 if (bounds [i] + 1 <= l/2) 2047 { 2048 int k= tmin (bounds [i] + 1, l/2); 2049 CFMatrix C= CFMatrix (l - k, factors.length()); 2050 for (int ii= 0; ii < factors.length(); ii++) 2051 { 2052 CFArray buf; 2053 if (A[ii].size() - 1 >= i) 2054 buf= getCoeffs (A[ii] [i], k); 2055 writeInMatrix (C, buf, ii + 1, 0); 2056 } 2057 mat_zz_pE* NTLC= convertFacCFMatrix2NTLmat_zz_pE(C); 2058 mat_zz_pE NTLK= (*NTLC)*NTLN; 2059 transpose (NTLK, NTLK); 2060 kernel (NTLK, NTLK); 2061 transpose (NTLK, NTLK); 2062 NTLN *= NTLK; 2063 if (NTLN.NumCols() == 1) 2064 { 2065 irreducible= true; 2066 delete [] A; 2067 delete [] bounds; 2068 return CFList (F); 2069 } 2070 } 2071 } 2072 2073 if (NTLN.NumCols() < oldNumCols - factorsFound) 2074 { 2075 if (isReduced (NTLN)) 2076 { 2077 int d= degree (F) + 1; 2078 int * factorsFoundIndex= new int [NTLN.NumCols()]; 2079 for (long i= 0; i < NTLN.NumCols(); i++) 2080 factorsFoundIndex[i]= 0; 2081 int factorsFound2= 0; 2082 CFList result; 2083 CanonicalForm bufF= F; 2084 reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2, 2085 factorsFoundIndex, NTLN, false); 2086 if (result.length() == NTLN.NumCols()) 2087 { 2088 delete [] factorsFoundIndex; 2089 delete [] A; 2090 delete [] bounds; 2091 return result; 2092 } 2093 delete [] factorsFoundIndex; 2094 } 2095 else if (l == precision) 2096 { 2097 CanonicalForm bufF= F; 2098 int * zeroOne= extractZeroOneVecs (NTLN); 2099 CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN); 2100 F= bufF; 2101 delete [] zeroOne; 2102 delete [] A; 2103 delete [] bounds; 2104 return result; 2105 } 2106 } 2107 oldL2= l; 2108 l += stepSize; 2109 stepSize *= 2; 2110 if (l > precision) 2111 { 2112 if (!hitBound) 2113 { 2114 l= precision; 2115 hitBound= true; 2116 } 2117 else 2118 break; 2119 } 2120 } 2121 delete [] bounds; 2122 delete [] A; 2123 return CFList(); 2124 } 2125 2126 //over field extension 2127 CFList 2128 extIncreasePrecision (CanonicalForm& F, CFList& factors, int factorsFound, 2129 int oldNumCols, int oldL, const CanonicalForm& evaluation, 2130 const ExtensionInfo& info, CFList& source, CFList& dest, 2131 int precision 2132 ) 2133 { 2134 bool GF= (CFFactory::gettype()==GaloisFieldDomain); 2135 int degMipo= degree (getMipo (info.getAlpha())); 2136 Variable alpha= info.getAlpha(); 2137 bool irreducible= false; 2138 int d; 2139 int* bounds= computeBounds (F, d); 2140 2141 CFArray * A= new CFArray [factors.length()]; 2142 CFArray bufQ= CFArray (factors.length()); 2143 zz_p::init (getCharacteristic()); 2144 mat_zz_p NTLN; 2145 ident (NTLN, factors.length()); 2146 int minBound= bounds[0]; 2147 for (int i= 1; i < d; i++) 2148 { 2149 if (bounds[i] != 0) 2150 minBound= tmin (minBound, bounds[i]); 2151 } 2152 int l= tmax (oldL, 2*((minBound+1)/degMipo+1)); 2153 int oldL2= l/2; 2154 int stepSize= 2; 2155 bool useOldQs= false; 2156 bool hitBound= false; 2157 Variable gamma= info.getBeta(); 2158 CanonicalForm primElemAlpha= info.getGamma(); 2159 CanonicalForm imPrimElemAlpha= info.getDelta(); 2160 while (l <= precision) 2161 { 2162 CFListIterator j= factors; 2163 if (GF) 2164 setCharacteristic (getCharacteristic()); 2165 Variable y= F.mvar(); 2166 CanonicalForm powX= power (y-gamma, l); 2167 CFMatrix Mat= CFMatrix (l*degMipo, l*degMipo); 2168 for (int i= 0; i < l*degMipo; i++) 2169 { 2170 2171 CanonicalForm imBasis= mod (power (y, i), powX); 2172 imBasis= imBasis (power (y, degMipo), y); 2173 imBasis= imBasis (y, gamma); 2174 CFIterator iter= imBasis; 2175 for (; iter.hasTerms(); iter++) 2176 Mat (iter.exp()+ 1, i+1)= iter.coeff(); 2177 } 2178 2179 mat_zz_p* NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat); 2180 *NTLMat= inv (*NTLMat); 2181 if (GF) 2182 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 2183 2184 if (useOldQs) 2185 { 2186 for (int i= 0; i < factors.length(); i++, j++) 2187 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL2, bufQ[i], 2188 bufQ[i] 2189 ); 2190 } 2191 else 2192 { 2193 for (int i= 0; i < factors.length(); i++, j++) 2194 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 2195 } 2196 useOldQs= true; 2197 for (int i= 0; i < d; i++) 2198 { 2199 if (bounds [i] + 1 <= (l/2)*degMipo) 2200 { 2201 int k= tmin (bounds [i] + 1, (l/2)*degMipo); 2202 CFMatrix C= CFMatrix (l*degMipo - k, factors.length()); 2203 for (int ii= 0; ii < factors.length(); ii++) 2204 { 2205 CFArray buf; 2206 if (A[ii].size() - 1 >= i) 2207 { 2208 if (GF) 2209 { 2210 A[ii] [i]= A [ii] [i] (y-evaluation, y); 2211 setCharacteristic (getCharacteristic()); 2212 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha); 2213 if (alpha != gamma) 2214 A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 2215 gamma, source, dest 2216 ); 2217 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat); 2218 } 2219 else 2220 { 2221 A [ii] [i]= A [ii] [i] (y-evaluation, y); 2222 if (alpha != gamma) 2223 A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 2224 gamma, source, dest 2225 ); 2226 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat); 2227 } 2228 } 2229 writeInMatrix (C, buf, ii + 1, 0); 2230 if (GF) 2231 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 2232 } 2233 2234 if (GF) 2235 setCharacteristic(getCharacteristic()); 2236 2237 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 2238 mat_zz_p NTLK= (*NTLC)*NTLN; 2239 transpose (NTLK, NTLK); 2240 kernel (NTLK, NTLK); 2241 transpose (NTLK, NTLK); 2242 NTLN *= NTLK; 2243 2244 if (GF) 2245 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 2246 2247 if (NTLN.NumCols() == 1) 2248 { 2249 irreducible= true; 2250 Variable y= Variable (2); 2251 CanonicalForm tmp= F (y - evaluation, y); 2252 CFList source, dest; 2253 tmp= mapDown (tmp, info, source, dest); 2254 delete [] A; 2255 delete [] bounds; 2256 return CFList (tmp); 2257 } 2258 } 2259 } 2260 2261 if (NTLN.NumCols() < oldNumCols - factorsFound) 2262 { 2263 if (isReduced (NTLN)) 2264 { 2265 int d= degree (F) + 1; 2266 int * factorsFoundIndex= new int [NTLN.NumCols()]; 2267 for (long i= 0; i < NTLN.NumCols(); i++) 2268 factorsFoundIndex[i]= 0; 2269 int factorsFound2= 0; 2270 CFList result; 2271 CanonicalForm bufF= F; 2272 extReconstructionTry (result, bufF, factors, degree (F)+1, factorsFound2, 2273 factorsFoundIndex, NTLN, false, info, evaluation 2274 ); 2275 if (result.length() == NTLN.NumCols()) 2276 { 2277 delete [] factorsFoundIndex; 2278 delete [] A; 2279 delete [] bounds; 2280 return result; 2281 } 2282 delete [] factorsFoundIndex; 2283 } 2284 else if (l == precision) 2285 { 2286 CanonicalForm bufF= F; 2287 int * zeroOne= extractZeroOneVecs (NTLN); 2288 CFList result= extReconstruction (bufF, factors, zeroOne, precision, 2289 NTLN, info, evaluation 2290 ); 2291 F= bufF; 2292 delete [] zeroOne; 2293 delete [] A; 2294 delete [] bounds; 2295 return result; 2296 } 2297 } 2298 oldL2= l; 2299 l += stepSize; 2300 stepSize *= 2; 2301 if (l > precision) 2302 { 2303 if (!hitBound) 2304 { 2305 hitBound= true; 2306 l= precision; 2307 } 2308 else 2309 break; 2310 } 2311 } 2312 delete [] bounds; 2313 delete [] A; 2314 return CFList(); 2315 } 2316 2317 CFList 2318 increasePrecision2 (const CanonicalForm& F, CFList& factors, 2319 const Variable& alpha, int precision) 2320 { 2321 bool irreducible= false; 2322 int d; 2323 int* bounds= computeBounds (F, d); 2324 CFArray * A= new CFArray [factors.length()]; 2325 CFArray bufQ= CFArray (factors.length()); 2326 zz_p::init (getCharacteristic()); 2327 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha)); 2328 zz_pE::init (NTLMipo); 2329 mat_zz_pE NTLN; 2330 ident (NTLN, factors.length()); 2331 int minBound= bounds[0]; 2332 for (int i= 1; i < d; i++) 2333 { 2334 if (bounds[i] != 0) 2335 minBound= tmin (minBound, bounds[i]); 2336 } 2337 int l= tmin (2*(minBound + 1), precision); 2338 int oldL= l/2; 2339 int stepSize= 2; 2340 bool useOldQs= false; 2341 bool hitBound= false; 2342 Variable y= Variable (2); 2343 while (l <= precision) 2344 { 2345 CFListIterator j= factors; 2346 if (useOldQs) 2347 { 2348 for (int i= 0; i < factors.length(); i++, j++) 2349 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i], bufQ[i]); 2350 } 2351 else 2352 { 2353 for (int i= 0; i < factors.length(); i++, j++) 2354 { 2355 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 2356 } 2357 } 2358 useOldQs= true; 2359 for (int i= 0; i < d; i++) 2360 { 2361 if (bounds [i] + 1 <= l/2) 2362 { 2363 int k= tmin (bounds [i] + 1, l/2); 2364 CFMatrix C= CFMatrix (l - k, factors.length()); 2365 for (int ii= 0; ii < factors.length(); ii++) 2366 { 2367 CFArray buf; 2368 if (A[ii].size() - 1 >= i) 2369 buf= getCoeffs (A[ii] [i], k); 2370 writeInMatrix (C, buf, ii + 1, 0); 2371 } 2372 mat_zz_pE* NTLC= convertFacCFMatrix2NTLmat_zz_pE(C); 2373 mat_zz_pE NTLK= (*NTLC)*NTLN; 2374 transpose (NTLK, NTLK); 2375 kernel (NTLK, NTLK); 2376 transpose (NTLK, NTLK); 2377 NTLN *= NTLK; 2378 if (NTLN.NumCols() == 1) 2379 { 2380 irreducible= true; 2381 delete [] A; 2382 delete [] bounds; 2383 return CFList (F); 2384 } 2385 } 2386 } 2387 2388 if (isReduced (NTLN) || l == precision) 2389 { 2390 CanonicalForm bufF= F; 2391 int * zeroOne= extractZeroOneVecs (NTLN); 2392 CFList bufFactors= factors; 2393 CFList result= monicReconstruction (bufF, factors, zeroOne, precision, 2394 NTLN 2395 ); 2396 if (result.length() != NTLN.NumCols() && l != precision) 2397 factors= bufFactors; 2398 if (result.length() == NTLN.NumCols()) 2399 { 2400 delete [] zeroOne; 2401 delete [] A; 2402 delete [] bounds; 2403 return result; 2404 } 2405 if (l == precision) 2406 { 2407 delete [] zeroOne; 2408 delete [] A; 2409 delete [] bounds; 2410 return Union (result, factors); 2411 } 2412 } 2413 oldL= l; 2414 l += stepSize; 2415 stepSize *= 2; 2416 if (l > precision) 2417 { 2418 if (!hitBound) 2419 { 2420 l= precision; 2421 hitBound= true; 2422 } 2423 else 2424 break; 2425 } 2426 } 2427 delete [] bounds; 2428 delete [] A; 2429 return CFList(); 2430 } 2431 2432 2433 CFList 2434 increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int factorsFound, 2435 int oldNumCols, int oldL, const Variable& alpha, 2436 int precision 2437 ) 2438 { 2439 bool irreducible= false; 2440 int d; 2441 int* bounds= computeBounds (F, d); 2442 int extensionDeg= degree (getMipo (alpha)); 2443 CFArray * A= new CFArray [factors.length()]; 2444 CFArray bufQ= CFArray (factors.length()); 2445 mat_zz_p NTLN; 2446 ident (NTLN, factors.length()); 2447 int minBound= bounds[0]; 2448 for (int i= 1; i < d; i++) 2449 { 2450 if (bounds[i] != 0) 2451 minBound= tmin (minBound, bounds[i]); 2452 } 2453 int l= tmax (2*(minBound + 1), oldL); 2454 int oldL2= l/2; 2455 int stepSize= 2; 2456 bool useOldQs= false; 2457 bool hitBound= false; 2458 while (l <= precision) 2459 { 2460 CFListIterator j= factors; 2461 if (useOldQs) 2462 { 2463 for (int i= 0; i < factors.length(); i++, j++) 2464 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL2, bufQ[i], 2465 bufQ[i] 2466 ); 2467 } 2468 else 2469 { 2470 for (int i= 0; i < factors.length(); i++, j++) 2471 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 2472 } 2473 useOldQs= true; 2474 for (int i= 0; i < d; i++) 2475 { 2476 if (bounds [i] + 1 <= l/2) 2477 { 2478 int k= tmin (bounds [i] + 1, l/2); 2479 CFMatrix C= CFMatrix ((l - k)*extensionDeg, factors.length()); 2480 for (int ii= 0; ii < factors.length(); ii++) 2481 { 2482 CFArray buf; 2483 if (A[ii].size() - 1 >= i) 2484 buf= getCoeffs (A[ii] [i], k, alpha); 2485 writeInMatrix (C, buf, ii + 1, 0); 2486 } 2487 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 2488 mat_zz_p NTLK= (*NTLC)*NTLN; 2489 transpose (NTLK, NTLK); 2490 kernel (NTLK, NTLK); 2491 transpose (NTLK, NTLK); 2492 NTLN *= NTLK; 2493 if (NTLN.NumCols() == 1) 2494 { 2495 irreducible= true; 2496 delete [] A; 2497 delete [] bounds; 2498 return CFList (F); 2499 } 2500 } 2501 } 2502 2503 if (NTLN.NumCols() < oldNumCols - factorsFound) 2504 { 2505 if (isReduced (NTLN)) 2506 { 2507 int d= degree (F) + 1; 2508 int * factorsFoundIndex= new int [NTLN.NumCols()]; 2509 for (long i= 0; i < NTLN.NumCols(); i++) 2510 factorsFoundIndex[i]= 0; 2511 int factorsFound2= 0; 2512 CFList result; 2513 CanonicalForm bufF= F; 2514 reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2, 2515 factorsFoundIndex, NTLN, false 2516 ); 2517 if (result.length() == NTLN.NumCols()) 2518 { 2519 delete [] factorsFoundIndex; 2520 delete [] A; 2521 delete [] bounds; 2522 return result; 2523 } 2524 delete [] factorsFoundIndex; 2525 } 2526 else if (l == precision) 2527 { 2528 CanonicalForm bufF= F; 2529 int * zeroOne= extractZeroOneVecs (NTLN); 2530 CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN); 2531 F= bufF; 2532 delete [] zeroOne; 2533 delete [] A; 2534 delete [] bounds; 2535 return result; 2536 } 2537 } 2538 oldL2= l; 2539 l += stepSize; 2540 stepSize *= 2; 2541 if (l > precision) 2542 { 2543 if (!hitBound) 2544 { 2545 hitBound= true; 2546 l= precision; 2547 } 2548 else 2549 break; 2550 } 2551 } 2552 delete [] bounds; 2553 delete [] A; 2554 return CFList(); 2555 } 2556 2557 CFList 2558 increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int 2559 l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN 2560 ) 2561 { 2562 CFList result= CFList(); 2563 bool irreducible= false; 2564 CFArray * A= new CFArray [factors.length()]; 2565 int oldL2= oldL/2; 2566 bool hitBound= false; 2567 if (NTLN.NumRows() != factors.length()) //refined factors 2568 { 2569 ident (NTLN, factors.length()); 2570 bufQ= CFArray (factors.length()); 2571 } 2572 bool useOldQs= false; 2573 while (oldL <= l) 2574 { 2575 CFListIterator j= factors; 2576 if (useOldQs) 2577 { 2578 for (int i= 0; i < factors.length(); i++, j++) 2579 A[i]= logarithmicDerivative (F, j.getItem(), oldL, oldL2, bufQ[i], 2580 bufQ[i] 2581 ); 2582 } 2583 else 2584 { 2585 for (int i= 0; i < factors.length(); i++, j++) 2586 A[i]= logarithmicDerivative (F, j.getItem(), oldL, bufQ [i]); 2587 } 2588 useOldQs= true; 2589 2590 for (int i= 0; i < d; i++) 2591 { 2592 if (bounds [i] + 1 <= oldL/2) 2593 { 2594 int k= tmin (bounds [i] + 1, oldL/2); 2595 CFMatrix C= CFMatrix (oldL - k, factors.length()); 2596 for (int ii= 0; ii < factors.length(); ii++) 2597 { 2598 CFArray buf; 2599 if (A[ii].size() - 1 >= i) 2600 buf= getCoeffs (A[ii] [i], k); 2601 writeInMatrix (C, buf, ii + 1, 0); 2602 } 2603 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 2604 mat_zz_p NTLK= (*NTLC)*NTLN; 2605 transpose (NTLK, NTLK); 2606 kernel (NTLK, NTLK); 2607 transpose (NTLK, NTLK); 2608 NTLN *= NTLK; 2609 if (NTLN.NumCols() == 1) 2610 { 2611 irreducible= true; 2612 delete [] A; 2613 return CFList (F); 2614 } 2615 } 2616 } 2617 if (NTLN.NumCols() == 1) 2618 { 2619 irreducible= true; 2620 delete [] A; 2621 return CFList (F); 2622 } 2623 int * zeroOneVecs; 2624 zeroOneVecs= extractZeroOneVecs (NTLN); 2625 CanonicalForm bufF= F; 2626 CFList bufUniFactors= factors; 2627 result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN); 2628 delete [] zeroOneVecs; 2629 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0) 2630 { 2631 F= bufF; 2632 factors= bufUniFactors; 2633 delete [] A; 2634 return result; 2635 } 2636 2637 result= CFList(); 2638 oldL2= oldL; 2639 oldL *= 2; 2640 if (oldL > l) 2641 { 2642 if (!hitBound) 2643 { 2644 oldL= l; 2645 hitBound= true; 2646 } 2647 else 2648 break; 2649 } 2650 } 2651 delete [] A; 2652 return result; 2653 } 2654 2655 CFList 2656 increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int 2657 l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN 2658 ) 2659 { 2660 CFList result= CFList(); 2661 bool irreducible= false; 2662 CFArray * A= new CFArray [factors.length()]; 2663 int oldL2= oldL/2; 2664 bool hitBound= false; 2665 bool useOldQs= false; 2666 if (NTLN.NumRows() != factors.length()) //refined factors 2667 ident (NTLN, factors.length()); 2668 while (oldL <= l) 2669 { 2670 CFListIterator j= factors; 2671 if (useOldQs) 2672 { 2673 for (int i= 0; i < factors.length(); i++, j++) 2674 A[i]= logarithmicDerivative (F, j.getItem(), oldL, oldL2, bufQ[i], 2675 bufQ[i] 2676 ); 2677 } 2678 else 2679 { 2680 for (int i= 0; i < factors.length(); i++, j++) 2681 A[i]= logarithmicDerivative (F, j.getItem(), oldL, bufQ [i]); 2682 } 2683 useOldQs= true; 2684 2685 for (int i= 0; i < d; i++) 2686 { 2687 if (bounds [i] + 1 <= oldL/2) 2688 { 2689 int k= tmin (bounds [i] + 1, oldL/2); 2690 CFMatrix C= CFMatrix (oldL - k, factors.length()); 2691 for (int ii= 0; ii < factors.length(); ii++) 2692 { 2693 CFArray buf; 2694 if (A[ii].size() - 1 >= i) 2695 buf= getCoeffs (A[ii] [i], k); 2696 writeInMatrix (C, buf, ii + 1, 0); 2697 } 2698 mat_zz_pE* NTLC= convertFacCFMatrix2NTLmat_zz_pE(C); 2699 mat_zz_pE NTLK= (*NTLC)*NTLN; 2700 transpose (NTLK, NTLK); 2701 kernel (NTLK, NTLK); 2702 transpose (NTLK, NTLK); 2703 NTLN *= NTLK; 2704 if (NTLN.NumCols() == 1) 2705 { 2706 irreducible= true; 2707 delete [] A; 2708 return CFList (F); 2709 } 2710 } 2711 } 2712 if (NTLN.NumCols() == 1) 2713 { 2714 irreducible= true; 2715 delete [] A; 2716 return CFList (F); 2717 } 2718 2719 int * zeroOneVecs; 2720 zeroOneVecs= extractZeroOneVecs (NTLN); 2721 CanonicalForm bufF= F; 2722 CFList bufUniFactors= factors; 2723 result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN); 2724 delete [] zeroOneVecs; 2725 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0) 2726 { 2727 F= bufF; 2728 factors= bufUniFactors; 2729 delete [] A; 2730 return result; 2731 } 2732 2733 result= CFList(); 2734 oldL2= oldL; 2735 oldL *= 2; 2736 if (oldL > l) 2737 { 2738 if (!hitBound) 2739 { 2740 oldL= l; 2741 hitBound= true; 2742 } 2743 else 2744 break; 2745 } 2746 } 2747 delete [] A; 2748 return result; 2749 } 2750 2751 //over field extension 2752 CFList 2753 extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d, 2754 int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const 2755 CanonicalForm& evaluation, const ExtensionInfo& info, 2756 CFList& source, CFList& dest 2757 ) 2758 { 2759 CFList result= CFList(); 2760 bool irreducible= false; 2761 CFArray * A= new CFArray [factors.length()]; 2762 int oldL2= oldL/2; //be careful 2763 bool hitBound= false; 2764 bool useOldQs= false; 2765 bool GF= (CFFactory::gettype()==GaloisFieldDomain); 2766 int degMipo= degree (getMipo (info.getAlpha())); 2767 Variable alpha= info.getAlpha(); 2768 2769 Variable gamma= info.getBeta(); 2770 CanonicalForm primElemAlpha= info.getGamma(); 2771 CanonicalForm imPrimElemAlpha= info.getDelta(); 2772 bool reduced= false; 2773 if (NTLN.NumRows() != factors.length()) //refined factors 2774 ident (NTLN, factors.length()); 2775 while (oldL <= l) 2776 { 2777 CFListIterator j= factors; 2778 if (GF) 2779 setCharacteristic (getCharacteristic()); 2780 Variable y= F.mvar(); 2781 CanonicalForm powX= power (y-gamma, oldL); 2782 CFMatrix Mat= CFMatrix (oldL*degMipo, oldL*degMipo); 2783 for (int i= 0; i < oldL*degMipo; i++) 2784 { 2785 2786 CanonicalForm imBasis= mod (power (y, i), powX); 2787 imBasis= imBasis (power (y, degMipo), y); 2788 imBasis= imBasis (y, gamma); 2789 int ind= oldL*degMipo - 1; 2790 CFIterator iter= imBasis; 2791 for (; iter.hasTerms(); iter++) 2792 Mat (iter.exp()+ 1, i+1)= iter.coeff(); 2793 } 2794 2795 mat_zz_p* NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat); 2796 *NTLMat= inv (*NTLMat); 2797 if (GF) 2798 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 2799 2800 if (useOldQs) 2801 { 2802 for (int i= 0; i < factors.length(); i++, j++) 2803 A[i]= logarithmicDerivative (F, j.getItem(), oldL, oldL2, bufQ[i], 2804 bufQ[i]); 2805 } 2806 else 2807 { 2808 for (int i= 0; i < factors.length(); i++, j++) 2809 A[i]= logarithmicDerivative (F, j.getItem(), oldL, bufQ [i]); 2810 } 2811 useOldQs= true; 2812 2813 for (int i= 0; i < d; i++) 2814 { 2815 if (bounds [i] + 1 <= oldL/2) 2816 { 2817 int k= tmin (bounds [i] + 1, oldL/2); 2818 CFMatrix C= CFMatrix (oldL*degMipo - k, factors.length()); 2819 for (int ii= 0; ii < factors.length(); ii++) 2820 { 2821 CFArray buf; 2822 if (A[ii].size() - 1 >= i) 2823 { 2824 if (GF) 2825 { 2826 A [ii] [i]= A [ii] [i] (y-evaluation, y); 2827 setCharacteristic (getCharacteristic()); 2828 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha); 2829 if (alpha != gamma) 2830 A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 2831 gamma, source, dest 2832 ); 2833 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat); 2834 } 2835 else 2836 { 2837 A [ii] [i]= A [ii] [i] (y-evaluation, y); 2838 if (alpha != gamma) 2839 A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 2840 gamma, source, dest 2841 ); 2842 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat); 2843 } 2844 } 2845 writeInMatrix (C, buf, ii + 1, 0); 2846 if (GF) 2847 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 2848 } 2849 2850 if (GF) 2851 setCharacteristic(getCharacteristic()); 2852 2853 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 2854 mat_zz_p NTLK= (*NTLC)*NTLN; 2855 transpose (NTLK, NTLK); 2856 kernel (NTLK, NTLK); 2857 transpose (NTLK, NTLK); 2858 NTLN *= NTLK; 2859 2860 if (GF) 2861 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 2862 2863 if (NTLN.NumCols() == 1) 2864 { 2865 irreducible= true; 2866 Variable y= Variable (2); 2867 CanonicalForm tmp= F (y - evaluation, y); 2868 CFList source, dest; 2869 tmp= mapDown (tmp, info, source, dest); 2870 delete [] A; 2871 return CFList (tmp); 2872 } 2873 } 2874 } 2875 if (NTLN.NumCols() == 1) 2876 { 2877 irreducible= true; 2878 Variable y= Variable (2); 2879 CanonicalForm tmp= F (y - evaluation, y); 2880 CFList source, dest; 2881 tmp= mapDown (tmp, info, source, dest); 2882 delete [] A; 2883 return CFList (tmp); 2884 } 2885 2886 int * zeroOneVecs; 2887 zeroOneVecs= extractZeroOneVecs (NTLN); 2888 CanonicalForm bufF= F; 2889 CFList bufUniFactors= factors; 2890 result= extReconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN, 2891 info, evaluation 2892 ); 2893 delete [] zeroOneVecs; 2894 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0) 2895 { 2896 F= bufF; 2897 factors= bufUniFactors; 2898 return result; 2899 } 2900 2901 if (isReduced (NTLN)) 2902 { 2903 int factorsFound= 0; 2904 CanonicalForm bufF= F; 2905 int* factorsFoundIndex= new int [NTLN.NumCols()]; 2906 for (long i= 0; i < NTLN.NumCols(); i++) 2907 factorsFoundIndex[i]= 0; 2908 extReconstructionTry (result, bufF, factors, l, factorsFound, 2909 factorsFoundIndex, NTLN, false, info, evaluation 2910 ); 2911 if (NTLN.NumCols() == result.length()) 2912 { 2913 delete [] A; 2914 delete [] factorsFoundIndex; 2915 return result; 2916 } 2917 } 2918 result= CFList(); 2919 oldL2= oldL; 2920 oldL *= 2; 2921 if (oldL > l) 2922 { 2923 if (!hitBound) 2924 { 2925 oldL= l; 2926 hitBound= true; 2927 } 2928 else 2929 break; 2930 } 2931 } 2932 delete [] A; 2933 return result; 2934 } 2935 2936 CFList 2937 increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l, 2938 int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN, 2939 const Variable& alpha 2940 ) 2941 { 2942 CFList result= CFList(); 2943 bool irreducible= false; 2944 CFArray * A= new CFArray [factors.length()]; 2945 int extensionDeg= degree (getMipo (alpha)); 2946 int oldL2= oldL/2; 2947 bool hitBound= false; 2948 bool useOldQs= false; 2949 if (NTLN.NumRows() != factors.length()) //refined factors 2950 { 2951 int minBound= bounds [0]; 2952 for (int i= 1; i < d; i++) 2953 { 2954 if (bounds [i] != 0) 2955 minBound= tmin (minBound, bounds [i]); 2956 } 2957 oldL= 2*(minBound+1); 2958 oldL2= minBound + 1; 2959 ident (NTLN, factors.length()); 2960 } 2961 while (oldL <= l) 2962 { 2963 CFListIterator j= factors; 2964 if (useOldQs) 2965 { 2966 for (int i= 0; i < factors.length(); i++, j++) 2967 A[i]= logarithmicDerivative (F, j.getItem(), oldL, oldL2, bufQ[i], 2968 bufQ[i] 2969 ); 2970 } 2971 else 2972 { 2973 for (int i= 0; i < factors.length(); i++, j++) 2974 A[i]= logarithmicDerivative (F, j.getItem(), oldL, bufQ [i]); 2975 } 2976 useOldQs= true; 2977 2978 for (int i= 0; i < d; i++) 2979 { 2980 if (bounds [i] + 1 <= oldL/2) 2981 { 2982 int k= tmin (bounds [i] + 1, oldL/2); 2983 CFMatrix C= CFMatrix ((oldL - k)*extensionDeg, factors.length()); 2984 for (int ii= 0; ii < factors.length(); ii++) 2985 { 2986 CFArray buf; 2987 if (A[ii].size() - 1 >= i) 2988 buf= getCoeffs (A[ii] [i], k, alpha); 2989 writeInMatrix (C, buf, ii + 1, 0); 2990 } 2991 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 2992 mat_zz_p NTLK= (*NTLC)*NTLN; 2993 transpose (NTLK, NTLK); 2994 kernel (NTLK, NTLK); 2995 transpose (NTLK, NTLK); 2996 NTLN *= NTLK; 2997 if (NTLN.NumCols() == 1) 2998 { 2999 irreducible= true; 3000 delete [] A; 3001 return CFList (F); 3002 } 3003 } 3004 } 3005 3006 int * zeroOneVecs; 3007 zeroOneVecs= extractZeroOneVecs (NTLN); 3008 3009 CanonicalForm bufF= F; 3010 CFList bufUniFactors= factors; 3011 result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN); 3012 delete [] zeroOneVecs; 3013 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0) 3014 { 3015 F= bufF; 3016 factors= bufUniFactors; 3017 delete [] A; 3018 return result; 3019 } 3020 3021 result= CFList(); 3022 oldL2= oldL; 3023 oldL *= 2; 3024 if (oldL > l) 3025 { 3026 if (!hitBound) 3027 { 3028 oldL= l; 3029 hitBound= true; 3030 } 3031 else 3032 break; 3033 } 3034 } 3035 delete [] A; 3036 return result; 3037 } 3038 3039 CFList 3040 furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& 3041 factors, int l, int liftBound, int d, int* 3042 bounds, mat_zz_p& NTLN, CFList& diophant, 3043 CFMatrix& M, CFArray& Pi, CFArray& bufQ 3044 ) 3045 { 3046 CanonicalForm LCF= LC (F, 1); 3047 CFList result; 3048 bool irreducible= false; 3049 CFList bufFactors= factors; 3050 CFArray *A = new CFArray [bufFactors.length()]; 3051 bool useOldQs= false; 3052 bool hitBound= false; 3053 int oldL= l; 3054 int stepSize= 8; //TODO choose better step size? 3055 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2); 3056 if (NTLN.NumRows() != factors.length()) //refined factors 3057 ident (NTLN, factors.length()); 3058 while (l <= liftBound) 3059 { 3060 bufFactors.insert (LCF); 3061 henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M); 3062 bufFactors.insert (LCF); 3063 bufFactors.removeFirst(); 3064 CFListIterator j= bufFactors; 3065 if (useOldQs) 3066 { 3067 for (int i= 0; i < bufFactors.length(); i++, j++) 3068 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i],bufQ[i]); 3069 } 3070 else 3071 { 3072 for (int i= 0; i < bufFactors.length(); i++, j++) 3073 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 3074 } 3075 for (int i= 0; i < d; i++) 3076 { 3077 if (bounds [i] + 1 <= l/2) 3078 { 3079 int k= tmin (bounds [i] + 1, l/2); 3080 CFMatrix C= CFMatrix (l - k, bufFactors.length()); 3081 for (int ii= 0; ii < bufFactors.length(); ii++) 3082 { 3083 CFArray buf; 3084 if (A[ii].size() - 1 >= i) 3085 buf= getCoeffs (A[ii] [i], k); 3086 writeInMatrix (C, buf, ii + 1, 0); 3087 } 3088 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 3089 mat_zz_p NTLK= (*NTLC)*NTLN; 3090 transpose (NTLK, NTLK); 3091 kernel (NTLK, NTLK); 3092 transpose (NTLK, NTLK); 3093 NTLN *= NTLK; 3094 if (NTLN.NumCols() == 1) 3095 { 3096 irreducible= true; 3097 break; 3098 } 3099 } 3100 } 3101 3102 if (NTLN.NumCols() == 1) 3103 { 3104 irreducible= true; 3105 break; 3106 } 3107 3108 int * zeroOneVecs= extractZeroOneVecs (NTLN); 3109 CanonicalForm bufF= F; 3110 result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN); 3111 delete [] zeroOneVecs; 3112 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l) 3113 { 3114 F= bufF; 3115 factors= bufFactors; 3116 delete [] A; 3117 return result; 3118 } 3119 3120 if (isReduced (NTLN)) 3121 { 3122 int factorsFound= 0; 3123 CanonicalForm bufF= F; 3124 int* factorsFoundIndex= new int [NTLN.NumCols()]; 3125 for (long i= 0; i < NTLN.NumCols(); i++) 3126 factorsFoundIndex[i]= 0; 3127 if (l < liftBound) 3128 reconstructionTry (result, bufF, bufFactors, l, factorsFound, 3129 factorsFoundIndex, NTLN, false 3130 ); 3131 else 3132 reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 + 3133 degree (LCF), factorsFound, factorsFoundIndex, 3134 NTLN, false 3135 ); 3136 3137 if (NTLN.NumCols() == result.length()) 3138 { 3139 delete [] A; 3140 delete [] factorsFoundIndex; 3141 return result; 3142 } 3143 delete [] factorsFoundIndex; 3144 } 3145 result= CFList(); 3146 oldL= l; 3147 stepSize *= 2; 3148 l += stepSize; 3149 if (l > liftBound) 3150 { 3151 if (!hitBound) 3152 { 3153 l= liftBound; 3154 hitBound= true; 3155 } 3156 else 3157 break; 3158 } 3159 } 3160 if (irreducible) 3161 { 3162 delete [] A; 3163 return CFList (F); 3164 } 3165 delete [] A; 3166 factors= bufFactors; 3167 return CFList(); 3168 } 3169 3170 //Fq 3171 CFList 3172 furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& 3173 factors, int l, int liftBound, int d, int* 3174 bounds, mat_zz_pE& NTLN, CFList& diophant, 3175 CFMatrix& M, CFArray& Pi, CFArray& bufQ 3176 ) 3177 { 3178 CanonicalForm LCF= LC (F, 1); 3179 CFList result; 3180 bool irreducible= false; 3181 CFList bufFactors= factors; 3182 CFArray *A = new CFArray [bufFactors.length()]; 3183 bool useOldQs= false; 3184 bool hitBound= false; 3185 int oldL= l; 3186 int stepSize= 8; //TODO choose better step size? 3187 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2); 3188 if (NTLN.NumRows() != factors.length()) //refined factors 3189 ident (NTLN, factors.length()); 3190 while (l <= liftBound) 3191 { 3192 bufFactors.insert (LCF); 3193 henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M); 3194 CFListIterator j= bufFactors; 3195 if (useOldQs) 3196 { 3197 for (int i= 0; i < bufFactors.length(); i++, j++) 3198 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i],bufQ[i]); 3199 } 3200 else 3201 { 3202 for (int i= 0; i < bufFactors.length(); i++, j++) 3203 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 3204 } 3205 for (int i= 0; i < d; i++) 3206 { 3207 if (bounds [i] + 1 <= l/2) 3208 { 3209 int k= tmin (bounds [i] + 1, l/2); 3210 CFMatrix C= CFMatrix (l - k, bufFactors.length()); 3211 for (int ii= 0; ii < bufFactors.length(); ii++) 3212 { 3213 CFArray buf; 3214 if (A[ii].size() - 1 >= i) 3215 buf= getCoeffs (A[ii] [i], k); 3216 writeInMatrix (C, buf, ii + 1, 0); 3217 } 3218 mat_zz_pE* NTLC= convertFacCFMatrix2NTLmat_zz_pE(C); 3219 mat_zz_pE NTLK= (*NTLC)*NTLN; 3220 transpose (NTLK, NTLK); 3221 kernel (NTLK, NTLK); 3222 transpose (NTLK, NTLK); 3223 NTLN *= NTLK; 3224 if (NTLN.NumCols() == 1) 3225 { 3226 irreducible= true; 3227 break; 3228 } 3229 } 3230 } 3231 if (NTLN.NumCols() == 1) 3232 { 3233 irreducible= true; 3234 break; 3235 } 3236 3237 int * zeroOneVecs= extractZeroOneVecs (NTLN); 3238 CanonicalForm bufF= F; 3239 result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN); 3240 delete [] zeroOneVecs; 3241 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l) 3242 { 3243 F= bufF; 3244 factors= bufFactors; 3245 delete [] A; 3246 return result; 3247 } 3248 3249 if (isReduced (NTLN)) 3250 { 3251 int factorsFound= 0; 3252 CanonicalForm bufF= F; 3253 int* factorsFoundIndex= new int [NTLN.NumCols()]; 3254 for (long i= 0; i < NTLN.NumCols(); i++) 3255 factorsFoundIndex[i]= 0; 3256 if (l < liftBound) 3257 reconstructionTry (result, bufF, bufFactors, l, factorsFound, 3258 factorsFoundIndex, NTLN, false 3259 ); 3260 else 3261 reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 + 3262 degree (LCF), factorsFound, factorsFoundIndex, 3263 NTLN, false 3264 ); 3265 if (NTLN.NumCols() == result.length()) 3266 { 3267 delete [] A; 3268 delete [] factorsFoundIndex; 3269 return result; 3270 } 3271 delete [] factorsFoundIndex; 3272 } 3273 result= CFList(); 3274 oldL= l; 3275 stepSize *= 2; 3276 l += stepSize; 3277 if (l > liftBound) 3278 { 3279 if (!hitBound) 3280 { 3281 l= liftBound; 3282 hitBound= true; 3283 } 3284 else 3285 break; 3286 } 3287 } 3288 if (irreducible) 3289 { 3290 delete [] A; 3291 return CFList (F); 3292 } 3293 delete [] A; 3294 factors= bufFactors; 3295 return CFList(); 3296 } 3297 3298 //over field extension 3299 CFList 3300 extFurtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& factors, int l, 3301 int liftBound, int d, int* bounds, 3302 mat_zz_p& NTLN, CFList& diophant, 3303 CFMatrix& M, CFArray& Pi, CFArray& bufQ, 3304 const CanonicalForm& evaluation, const 3305 ExtensionInfo& info, CFList& source, 3306 CFList& dest 3307 ) 3308 { 3309 CanonicalForm LCF= LC (F, 1); 3310 CFList result; 3311 bool irreducible= false; 3312 CFList bufFactors= factors; 3313 CFArray *A = new CFArray [bufFactors.length()]; 3314 bool useOldQs= false; 3315 bool hitBound= false; 3316 bool GF= (CFFactory::gettype()==GaloisFieldDomain); 3317 int degMipo= degree (getMipo (info.getAlpha())); 3318 Variable alpha= info.getAlpha(); 3319 int oldL= l; //be careful 3320 int stepSize= 8; 3321 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2); 3322 bool reduced= false; 3323 Variable gamma= info.getBeta(); 3324 CanonicalForm primElemAlpha= info.getGamma(); 3325 CanonicalForm imPrimElemAlpha= info.getDelta(); 3326 if (NTLN.NumRows() != factors.length()) //refined factors 3327 ident (NTLN, factors.length()); 3328 while (l <= liftBound) 3329 { 3330 bufFactors.insert (LCF); 3331 henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M); 3332 3333 if (GF) 3334 setCharacteristic (getCharacteristic()); 3335 3336 Variable y= F.mvar(); 3337 CanonicalForm powX= power (y-gamma, l); 3338 CFMatrix Mat= CFMatrix (l*degMipo, l*degMipo); 3339 for (int i= 0; i < l*degMipo; i++) 3340 { 3341 3342 CanonicalForm imBasis= mod (power (y, i), powX); 3343 imBasis= imBasis (power (y, degMipo), y); 3344 imBasis= imBasis (y, gamma); 3345 CFIterator iter= imBasis; 3346 for (; iter.hasTerms(); iter++) 3347 Mat (iter.exp()+ 1, i+1)= iter.coeff(); 3348 } 3349 3350 mat_zz_p* NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat); 3351 *NTLMat= inv (*NTLMat); 3352 3353 if (GF) 3354 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 3355 3356 CFListIterator j= bufFactors; 3357 if (useOldQs) 3358 { 3359 for (int i= 0; i < bufFactors.length(); i++, j++) 3360 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i],bufQ[i]); 3361 } 3362 else 3363 { 3364 for (int i= 0; i < bufFactors.length(); i++, j++) 3365 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 3366 } 3367 for (int i= 0; i < d; i++) 3368 { 3369 if (bounds [i] + 1 <= l/2) 3370 { 3371 int k= tmin (bounds [i] + 1, l/2); 3372 CFMatrix C= CFMatrix (l*degMipo - k, bufFactors.length()); 3373 for (int ii= 0; ii < bufFactors.length(); ii++) 3374 { 3375 CFArray buf; 3376 if (A[ii].size() - 1 >= i) 3377 { 3378 if (GF) 3379 { 3380 A [ii] [i]= A [ii] [i] (y-evaluation, y); 3381 setCharacteristic (getCharacteristic()); 3382 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha); 3383 if (alpha != gamma) 3384 A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 3385 gamma, source, dest 3386 ); 3387 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat); 3388 } 3389 else 3390 { 3391 A [ii] [i]= A [ii] [i] (y-evaluation, y); 3392 if (alpha != gamma) 3393 A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha, 3394 gamma, source, dest 3395 ); 3396 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat); 3397 } 3398 } 3399 writeInMatrix (C, buf, ii + 1, 0); 3400 if (GF) 3401 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 3402 } 3403 3404 if (GF) 3405 setCharacteristic(getCharacteristic()); 3406 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 3407 mat_zz_p NTLK= (*NTLC)*NTLN; 3408 transpose (NTLK, NTLK); 3409 kernel (NTLK, NTLK); 3410 transpose (NTLK, NTLK); 3411 NTLN *= NTLK; 3412 if (GF) 3413 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 3414 3415 if (NTLN.NumCols() == 1) 3416 { 3417 irreducible= true; 3418 break; 3419 } 3420 } 3421 } 3422 if (NTLN.NumCols() == 1) 3423 { 3424 irreducible= true; 3425 break; 3426 } 3427 3428 int * zeroOneVecs= extractZeroOneVecs (NTLN); 3429 CanonicalForm bufF= F; 3430 result= extReconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN, info, 3431 evaluation 3432 ); 3433 delete [] zeroOneVecs; 3434 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l) 3435 { 3436 F= bufF; 3437 factors= bufFactors; 3438 delete [] A; 3439 return result; 3440 } 3441 3442 if (isReduced (NTLN)) 3443 { 3444 int factorsFound= 0; 3445 CanonicalForm bufF= F; 3446 int* factorsFoundIndex= new int [NTLN.NumCols()]; 3447 for (long i= 0; i < NTLN.NumCols(); i++) 3448 factorsFoundIndex[i]= 0; 3449 if (l < degree (bufF) + 1 + degree (LCF)) 3450 extReconstructionTry (result, bufF, bufFactors, l, factorsFound, 3451 factorsFoundIndex, NTLN, false, info, evaluation 3452 ); 3453 else 3454 extReconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 + 3455 degree (LCF), factorsFound, factorsFoundIndex, 3456 NTLN, false, info, evaluation 3457 ); 3458 if (NTLN.NumCols() == result.length()) 3459 { 3460 delete [] A; 3461 delete [] factorsFoundIndex; 3462 return result; 3463 } 3464 delete [] factorsFoundIndex; 3465 } 3466 result= CFList(); 3467 oldL= l; 3468 stepSize *= 2; 3469 l += stepSize; 3470 if (l > liftBound) 3471 { 3472 if (!hitBound) 3473 { 3474 l= liftBound; 3475 hitBound= true; 3476 } 3477 else 3478 break; 3479 } 3480 } 3481 if (irreducible) 3482 { 3483 delete [] A; 3484 Variable y= Variable (2); 3485 CanonicalForm tmp= F (y - evaluation, y); 3486 CFList source, dest; 3487 tmp= mapDown (tmp, info, source, dest); 3488 return CFList (tmp); 3489 } 3490 delete [] A; 3491 factors= bufFactors; 3492 return CFList(); 3493 } 3494 3495 CFList 3496 furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int 3497 l, int liftBound, int d, int* bounds, 3498 mat_zz_p& NTLN, CFList& diophant, 3499 CFMatrix& M, CFArray& Pi, CFArray& bufQ, 3500 const Variable& alpha 3501 ) 3502 { 3503 CanonicalForm LCF= LC (F, 1); 3504 CFList result; 3505 bool irreducible= false; 3506 CFList bufFactors= factors; 3507 CFArray *A = new CFArray [bufFactors.length()]; 3508 bool useOldQs= false; 3509 int extensionDeg= degree (getMipo (alpha)); 3510 bool hitBound= false; 3511 int oldL= l; 3512 int stepSize= 8; //TODO choose better step size? 3513 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2); 3514 bool reduced= false; 3515 if (NTLN.NumRows() != factors.length()) //refined factors 3516 ident (NTLN, factors.length()); 3517 while (l <= liftBound) 3518 { 3519 bufFactors.insert (LCF); 3520 henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M); 3521 CFListIterator j= bufFactors; 3522 if (useOldQs) 3523 { 3524 for (int i= 0; i < bufFactors.length(); i++, j++) 3525 A[i]= logarithmicDerivative (F, j.getItem(), l, oldL, bufQ[i],bufQ[i]); 3526 } 3527 else 3528 { 3529 for (int i= 0; i < bufFactors.length(); i++, j++) 3530 A[i]= logarithmicDerivative (F, j.getItem(), l, bufQ [i]); 3531 } 3532 for (int i= 0; i < d; i++) 3533 { 3534 if (bounds [i] + 1 <= l/2) 3535 { 3536 int k= tmin (bounds [i] + 1, l/2); 3537 CFMatrix C= CFMatrix ((l - k)*extensionDeg, bufFactors.length()); 3538 for (int ii= 0; ii < bufFactors.length(); ii++) 3539 { 3540 CFArray buf; 3541 if (A[ii].size() - 1 >= i) 3542 buf= getCoeffs (A[ii] [i], k, alpha); 3543 writeInMatrix (C, buf, ii + 1, 0); 3544 } 3545 mat_zz_p* NTLC= convertFacCFMatrix2NTLmat_zz_p(C); 3546 mat_zz_p NTLK= (*NTLC)*NTLN; 3547 transpose (NTLK, NTLK); 3548 kernel (NTLK, NTLK); 3549 transpose (NTLK, NTLK); 3550 NTLN *= NTLK; 3551 if (NTLN.NumCols() == 1) 3552 { 3553 irreducible= true; 3554 break; 3555 } 3556 } 3557 } 3558 if (NTLN.NumCols() == 1) 3559 { 3560 irreducible= true; 3561 break; 3562 } 3563 3564 int * zeroOneVecs= extractZeroOneVecs (NTLN); 3565 CanonicalForm bufF= F; 3566 result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN); 3567 delete [] zeroOneVecs; 3568 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l) 3569 { 3570 F= bufF; 3571 factors= bufFactors; 3572 delete [] A; 3573 return result; 3574 } 3575 3576 if (isReduced (NTLN)) 3577 { 3578 int factorsFound= 0; 3579 CanonicalForm bufF= F; 3580 int* factorsFoundIndex= new int [NTLN.NumCols()]; 3581 for (long i= 0; i < NTLN.NumCols(); i++) 3582 factorsFoundIndex[i]= 0; 3583 if (l < degree (bufF) + 1 + degree (LCF)) 3584 reconstructionTry (result, bufF, bufFactors, l, factorsFound, 3585 factorsFoundIndex, NTLN, false 3586 ); 3587 else 3588 reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 + 3589 degree (LCF), factorsFound, factorsFoundIndex, 3590 NTLN, false 3591 ); 3592 if (NTLN.NumCols() == result.length()) 3593 { 3594 delete [] A; 3595 delete [] factorsFoundIndex; 3596 return result; 3597 } 3598 delete [] factorsFoundIndex; 3599 } 3600 result= CFList(); 3601 oldL= l; 3602 stepSize *= 2; 3603 l += stepSize; 3604 if (l > liftBound) 3605 { 3606 if (!hitBound) 3607 { 3608 l= liftBound; 3609 hitBound= true; 3610 } 3611 else 3612 break; 3613 } 3614 } 3615 if (irreducible) 3616 { 3617 delete [] A; 3618 return CFList (F); 3619 } 3620 delete [] A; 3621 factors= bufFactors; 3622 return CFList(); 3623 } 3624 3625 void 3626 refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int 3627 liftBound, int l, CFList& factors, CFMatrix& M, CFArray& 3628 Pi, CFList& diophant 3629 ) 3630 { 3631 CFList bufFactors; 3632 Variable y= Variable (2); 3633 CanonicalForm LCF= LC (F, 1); 3634 for (long i= 1; i <= NTLN.NumCols(); i++) 3635 { 3636 CFListIterator iter= factors; 3637 CanonicalForm buf= 1; 3638 for (long j= 1; j <= NTLN.NumRows(); j++, iter++) 3639 { 3640 if (!IsZero (NTLN (j,i))) 3641 buf= mulNTL (buf, mod (iter.getItem(), y)); 3642 } 3643 bufFactors.append (buf); 3644 } 3645 factors= bufFactors; 3646 M= CFMatrix (liftBound, factors.length()); 3647 Pi= CFArray(); 3648 diophant= CFList(); 3649 factors.insert (LCF); 3650 henselLift12 (F, factors, l, Pi, diophant, M); 3651 } 3652 3653 void 3654 refineAndRestartLift (const CanonicalForm& F, const mat_zz_pE& NTLN, int 3655 liftBound, int l, CFList& factors, CFMatrix& M, CFArray& 3656 Pi, CFList& diophant 3657 ) 3658 { 3659 CFList bufFactors; 3660 Variable y= Variable (2); 3661 CanonicalForm LCF= LC (F, 1); 3662 for (long i= 1; i <= NTLN.NumCols(); i++) 3663 { 3664 CFListIterator iter= factors; 3665 CanonicalForm buf= 1; 3666 for (long j= 1; j <= NTLN.NumRows(); j++, iter++) 3667 { 3668 if (!IsZero (NTLN (j,i))) 3669 buf= mulNTL (buf, mod (iter.getItem(), y)); 3670 } 3671 bufFactors.append (buf); 3672 } 3673 factors= bufFactors; 3674 M= CFMatrix (liftBound, factors.length()); 3675 Pi= CFArray(); 3676 diophant= CFList(); 3677 factors.insert (LCF); 3678 henselLift12 (F, factors, l, Pi, diophant, M); 3679 } 3680 3681 CFList 3682 earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N, 3683 CanonicalForm& bufF, CFList& factors, int& l, 3684 int& factorsFound, bool beenInThres, CFMatrix& M, 3685 CFArray& Pi, CFList& diophant 3686 ) 3687 { 3688 bufF= F; 3689 factorsFound= 0; 3690 CanonicalForm LCF= LC (F, 1); 3691 CFList result; 3692 int smallFactorDeg= 11; 3693 mat_zz_p NTLN= N; 3694 int * factorsFoundIndex= new int [NTLN.NumCols()]; 3695 for (long i= 0; i < NTLN.NumCols(); i++) 3696 factorsFoundIndex [i]= 0; 3697 3698 if (degree (F) + 1 > smallFactorDeg) 3699 { 3700 if (l < smallFactorDeg) 3701 { 3702 factors.insert (LCF); 3703 henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M); 3704 l= smallFactorDeg; 3705 } 3706 reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound, 3707 factorsFoundIndex, NTLN, beenInThres 3708 ); 3709 if (result.length() == NTLN.NumCols()) 3710 { 3711 delete [] factorsFoundIndex; 3712 return result; 3713 } 3714 } 3715 3716 if (l < degree (bufF)/2+2) 3717 { 3718 factors.insert (LCF); 3719 henselLiftResume12 (F, factors, l, degree (bufF)/2 + 2, Pi, diophant, M); 3720 l= degree (bufF)/2 + 2; 3721 } 3722 reconstructionTry (result, bufF, factors, degree (bufF)/2 + 2, 3723 factorsFound, factorsFoundIndex, NTLN, beenInThres 3724 ); 3725 if (result.length() == NTLN.NumCols()) 3726 { 3727 delete [] factorsFoundIndex; 3728 return result; 3729 } 3730 3731 if (l < degree (F) + 1) 3732 { 3733 factors.insert (LCF); 3734 henselLiftResume12 (F, factors, l, degree (bufF) + 1, Pi, diophant, M); 3735 l= degree (bufF) + 1; 3736 } 3737 reconstructionTry (result, bufF, factors, degree (bufF) + 1, factorsFound, 3738 factorsFoundIndex, NTLN, beenInThres 3739 ); 3740 if (result.length() == NTLN.NumCols()) 3741 { 3742 delete [] factorsFoundIndex; 3743 return result; 3744 } 3745 delete [] factorsFoundIndex; 3746 return result; 3747 } 3748 3749 CFList 3750 earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_pE& N, 3751 CanonicalForm& bufF, CFList& factors, int& l, 3752 int& factorsFound, bool beenInThres, CFMatrix& M, 3753 CFArray& Pi, CFList& diophant 3754 ) 3755 { 3756 bufF= F; 3757 factorsFound= 0; 3758 CanonicalForm LCF= LC (F, 1); 3759 CFList result; 3760 int smallFactorDeg= 11; 3761 mat_zz_pE NTLN= N; 3762 int * factorsFoundIndex= new int [NTLN.NumCols()]; 3763 for (long i= 0; i < NTLN.NumCols(); i++) 3764 factorsFoundIndex [i]= 0; 3765 if (degree (F) + 1 > smallFactorDeg) 3766 { 3767 if (l < smallFactorDeg) 3768 { 3769 factors.insert (LCF); 3770 henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M); 3771 l= smallFactorDeg; 3772 } 3773 reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound, 3774 factorsFoundIndex, NTLN, beenInThres 3775 ); 3776 if (result.length() == NTLN.NumCols()) 3777 { 3778 delete [] factorsFoundIndex; 3779 return result; 3780 } 3781 } 3782 3783 if (l < degree (bufF)/2+2) 3784 { 3785 factors.insert (LCF); 3786 henselLiftResume12 (F, factors, l, degree (bufF)/2 + 2, Pi, diophant, M); 3787 l= degree (bufF)/2 + 2; 3788 } 3789 reconstructionTry (result, bufF, factors, degree (bufF)/2 + 2, 3790 factorsFound, factorsFoundIndex, NTLN, beenInThres 3791 ); 3792 if (result.length() == NTLN.NumCols()) 3793 { 3794 delete [] factorsFoundIndex; 3795 return result; 3796 } 3797 3798 if (l < degree (F) + 1) 3799 { 3800 factors.insert (LCF); 3801 henselLiftResume12 (F, factors, l, degree (bufF) + 1, Pi, diophant, M); 3802 l= degree (bufF) + 1; 3803 } 3804 reconstructionTry (result, bufF, factors, degree (bufF) + 1, factorsFound, 3805 factorsFoundIndex, NTLN, beenInThres 3806 ); 3807 if (result.length() == NTLN.NumCols()) 3808 { 3809 delete [] factorsFoundIndex; 3810 return result; 3811 } 3812 delete [] factorsFoundIndex; 3813 return result; 3814 } 3815 3816 //over field extension 3817 CFList 3818 extEarlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N, 3819 CanonicalForm& bufF, CFList& factors, int& l, 3820 int& factorsFound, bool beenInThres, CFMatrix& 3821 M, CFArray& Pi, CFList& diophant, const 3822 ExtensionInfo& info, const CanonicalForm& 3823 evaluation 3824 ) 3825 { 3826 bufF= F; 3827 factorsFound= 0; 3828 CanonicalForm LCF= LC (F, 1); 3829 CFList result; 3830 int smallFactorDeg= 11; 3831 mat_zz_p NTLN= N; 3832 int * factorsFoundIndex= new int [NTLN.NumCols()]; 3833 for (long i= 0; i < NTLN.NumCols(); i++) 3834 factorsFoundIndex [i]= 0; 3835 3836 if (degree (F) + 1 > smallFactorDeg) 3837 { 3838 if (l < smallFactorDeg) 3839 { 3840 factors.insert (LCF); 3841 henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M); 3842 l= smallFactorDeg; 3843 } 3844 extReconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound, 3845 factorsFoundIndex, NTLN, beenInThres, info, 3846 evaluation 3847 ); 3848 if (result.length() == NTLN.NumCols()) 3849 { 3850 delete [] factorsFoundIndex; 3851 return result; 3852 } 3853 } 3854 3855 if (l < degree (bufF)/2+2) 3856 { 3857 factors.insert (LCF); 3858 henselLiftResume12 (F, factors, l, degree (bufF)/2 + 2, Pi, diophant, M); 3859 l= degree (bufF)/2 + 2; 3860 } 3861 extReconstructionTry (result, bufF, factors, degree (bufF)/2 + 2, 3862 factorsFound, factorsFoundIndex, NTLN, beenInThres, info, 3863 evaluation 3864 ); 3865 if (result.length() == NTLN.NumCols()) 3866 { 3867 delete [] factorsFoundIndex; 3868 return result; 3869 } 3870 3871 if (l < degree (bufF) + 1) 3872 { 3873 factors.insert (LCF); 3874 henselLiftResume12 (F, factors, l, degree (bufF) + 1, Pi, diophant, M); 3875 l= degree (bufF) + 1; 3876 } 3877 3878 extReconstructionTry (result, bufF, factors, degree (bufF) + 1, factorsFound, 3879 factorsFoundIndex, NTLN, beenInThres, info, evaluation 3880 ); 3881 if (result.length() == NTLN.NumCols()) 3882 { 3883 delete [] factorsFoundIndex; 3884 return result; 3885 } 3886 delete [] factorsFoundIndex; 3887 return result; 3888 } 3889 3890 CFList 3891 sieveSmallFactors (const CanonicalForm& G, CFList& uniFactors, DegreePattern& 3892 degPat, CanonicalForm& H, CFList& diophant, CFArray& Pi, 3893 CFMatrix& M, bool& success, int d 3894 ) 3895 { 3896 CanonicalForm F= G; 3897 CFList bufUniFactors= uniFactors; 3898 bufUniFactors.insert (LC (F, 1)); 3899 int smallFactorDeg= d; 3900 DegreePattern degs= degPat; 3901 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant, M); 3902 int adaptedLiftBound; 3903 success= false; 3904 CFList earlyFactors= earlyFactorDetection (F, bufUniFactors, adaptedLiftBound, 3905 degs, success, smallFactorDeg 3906 ); 3907 if (degs.getLength() == 1) 3908 { 3909 degPat= degs; 3910 return earlyFactors; 3911 } 3912 if (success) 3913 { 3914 H= F; 3915 return earlyFactors; 3916 } 3917 int sizeOldF= size (F); 3918 int sizeF; 3919 CFList result; 3920 CanonicalForm bufF= F; 3921 if (earlyFactors.length() > 0) 3922 { 3923 for (CFListIterator i= earlyFactors; i.hasItem(); i++) 3924 bufF /= i.getItem(); 3925 } 3926 3927 if (size (bufF) < sizeOldF) 3928 { 3929 H= bufF; 3930 success= true; 3931 return earlyFactors; 3932 } 3933 else 3934 { 3935 uniFactors= bufUniFactors; 3936 return CFList(); 3937 } 3938 } 3939 3940 CFList 3941 extSieveSmallFactors (const CanonicalForm& G, CFList& uniFactors, DegreePattern& 3942 degPat, CanonicalForm& H, CFList& diophant, CFArray& Pi, 3943 CFMatrix& M, bool& success, int d, const CanonicalForm& 3944 evaluation, const ExtensionInfo& info 3945 ) 3946 { 3947 CanonicalForm F= G; 3948 CFList bufUniFactors= uniFactors; 3949 bufUniFactors.insert (LC (F, 1)); 3950 int smallFactorDeg= d; 3951 DegreePattern degs= degPat; 3952 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant, M); 3953 int adaptedLiftBound; 3954 success= false; 3955 CFList earlyFactors= extEarlyFactorDetection (F, bufUniFactors, 3956 adaptedLiftBound, degs, success, 3957 info, evaluation, smallFactorDeg 3958 ); 3959 if (degs.getLength() == 1) 3960 { 3961 degPat= degs; 3962 return earlyFactors; 3963 } 3964 if (success) 3965 { 3966 H= F; 3967 return earlyFactors; 3968 } 3969 Variable y= F.mvar(); 3970 CanonicalForm shiftedF= F (y - evaluation, y); 3971 int sizeOldF= size (shiftedF); 3972 int sizeF; 3973 CFList result; 3974 CanonicalForm bufF= shiftedF; 3975 if (earlyFactors.length() > 0) 3976 { 3977 for (CFListIterator i= earlyFactors; i.hasItem(); i++) 3978 { 3979 bufF /= i.getItem(); 3980 result.append (i.getItem()); 3981 } 3982 } 3983 3984 if (size (bufF) < sizeOldF) 3985 { 3986 H= bufF (y + evaluation, y); //shift back to zero 3987 success= true; 3988 return result; 3989 } 3990 else 3991 { 3992 uniFactors= bufUniFactors; 3993 return CFList(); 3994 } 3995 } 3996 3997 CFList 3998 henselLiftAndLatticeRecombi (const CanonicalForm& G, const CFList& uniFactors, 3999 const Variable& alpha, const DegreePattern& degPat 4000 ) 4001 { 4002 DegreePattern degs= degPat; 4003 CanonicalForm F= G; 4004 CanonicalForm LCF= LC (F, 1); 4005 Variable y= F.mvar(); 4006 Variable x= Variable (1); 4007 int d; 4008 int* bounds= computeBounds (F, d); 4009 4010 int minBound= bounds[0]; 4011 for (int i= 1; i < d; i++) 4012 { 4013 if (bounds[i] != 0) 4014 minBound= tmin (minBound, bounds[i]); 4015 } 4016 4017 CFList bufUniFactors= uniFactors; 4018 CFArray Pi; 4019 CFList diophant; 4020 int liftBound= 2*totaldegree (F) - 1; 4021 CFMatrix M= CFMatrix (liftBound, bufUniFactors.length()); 4022 4023 CFList smallFactors; 4024 CanonicalForm H; 4025 bool success; 4026 smallFactors= sieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi, M, 4027 success, 2*(minBound + 1) 4028 ); 4029 4030 if (smallFactors.length() > 0) 4031 { 4032 if (smallFactors.length() == 1) 4033 { 4034 if (smallFactors.getFirst() == F) 4035 { 4036 delete [] bounds; 4037 return CFList (G); 4038 } 4039 } 4040 if (degs.getLength() <= 1) 4041 { 4042 delete [] bounds; 4043 return smallFactors; 4044 } 4045 } 4046 4047 int index; 4048 for (CFListIterator i= smallFactors; i.hasItem(); i++) 4049 { 4050 index= 1; 4051 CanonicalForm tmp1, tmp2; 4052 tmp1= mod (i.getItem(),y); 4053 tmp1 /= Lc (tmp1); 4054 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++) 4055 { 4056 tmp2= mod (j.getItem(), y); 4057 tmp2 /= Lc (tmp2); 4058 if (tmp1 == tmp2) 4059 { 4060 index++; 4061 j.remove(index); 4062 break; 4063 } 4064 } 4065 } 4066 4067 if (bufUniFactors.isEmpty()) 4068 { 4069 delete [] bounds; 4070 return smallFactors; 4071 } 4072 4073 if (success) 4074 { 4075 F= H; 4076 delete [] bounds; 4077 bounds= computeBounds (F, d); 4078 LCF= LC (F, 1); 4079 4080 minBound= bounds[0]; 4081 for (int i= 1; i < d; i++) 4082 { 4083 if (bounds[i] != 0) 4084 minBound= tmin (minBound, bounds[i]); 4085 } 4086 Pi= CFArray(); 4087 diophant= CFList(); 4088 liftBound= 2*totaldegree (F) - 1; 4089 M= CFMatrix (liftBound, bufUniFactors.length()); 4090 DegreePattern bufDegs= DegreePattern (bufUniFactors); 4091 degs.intersect (bufDegs); 4092 degs.refine(); 4093 if (degs.getLength() <= 1) 4094 { 4095 smallFactors.append (F); 4096 delete [] bounds; 4097 return smallFactors; 4098 } 4099 } 4100 4101 bool reduceFq2Fp= (degree (F) > getCharacteristic()); 4102 bufUniFactors.insert (LCF); 4103 int l= 1; 4104 4105 zz_p::init (getCharacteristic()); 4106 mat_zz_p NTLN; 4107 if (alpha.level() != 1) 4108 { 4109 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha)); 4110 zz_pE::init (NTLMipo); 4111 } 4112 mat_zz_pE NTLNe; 4113 if (alpha.level() == 1) 4114 ident (NTLN, bufUniFactors.length() - 1); 4115 else 4116 { 4117 if (reduceFq2Fp) 4118 ident (NTLN, bufUniFactors.length() - 1); 4119 else 4120 ident (NTLNe, bufUniFactors.length() - 1); 4121 } 4122 bool wasInBounds= false; 4123 bool irreducible= false; 4124 CFArray bufQ= CFArray (bufUniFactors.length() - 1); 4125 4126 int oldL; 4127 if (success) 4128 { 4129 int start= 0; 4130 if (alpha.level() == 1) 4131 oldL= liftAndComputeLattice (F, bounds, d, start, liftBound, minBound, 4132 bufUniFactors, NTLN, diophant, M, Pi, bufQ, 4133 irreducible 4134 ); 4135 else 4136 { 4137 if (reduceFq2Fp) 4138 oldL= liftAndComputeLatticeFq2Fp (F, bounds, d, start, liftBound, 4139 minBound, bufUniFactors, NTLN, 4140 diophant, M, Pi, bufQ, irreducible, 4141 alpha 4142 ); 4143 else 4144 oldL= liftAndComputeLattice (F, bounds, d, start, liftBound, minBound, 4145 bufUniFactors, NTLNe, diophant, M, Pi, bufQ, 4146 irreducible 4147 ); 4148 } 4149 } 4150 else 4151 { 4152 if (alpha.level() == 1) 4153 oldL= liftAndComputeLattice (F, bounds, d, 2*(minBound + 1), liftBound, 4154 minBound, bufUniFactors, NTLN, diophant, M, 4155 Pi, bufQ, irreducible 4156 ); 4157 else 4158 { 4159 if (reduceFq2Fp) 4160 oldL= liftAndComputeLatticeFq2Fp (F, bounds, d, 2*(minBound + 1), 4161 liftBound, minBound, bufUniFactors, 4162 NTLN, diophant, M, Pi, bufQ, 4163 irreducible, alpha 4164 ); 4165 else 4166 oldL= liftAndComputeLattice (F, bounds, d, 2*(minBound + 1), liftBound, 4167 minBound, bufUniFactors, NTLNe, diophant, 4168 M, Pi, bufQ, irreducible 4169 ); 4170 } 4171 } 4172 4173 bufUniFactors.removeFirst(); 4174 if (oldL > liftBound) 4175 { 4176 delete [] bounds; 4177 return Union (smallFactors, 4178 factorRecombination (bufUniFactors, F, 4179 power (y, degree (F) + 1 + degree (LCF)), 4180 degs, 1, bufUniFactors.length()/2 4181 ) 4182 ); 4183 } 4184 4185 l= oldL; 4186 if (irreducible) 4187 { 4188 delete [] bounds; 4189 return Union (CFList (F), smallFactors); 4190 } 4191 4192 CanonicalForm yToL= power (y,l); 4193 4194 CFList result; 4195 if (l >= degree (F) + 1) 4196 { 4197 int * factorsFoundIndex; 4198 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4199 { 4200 factorsFoundIndex= new int [NTLN.NumCols()]; 4201 for (long i= 0; i < NTLN.NumCols(); i++) 4202 factorsFoundIndex[i]= 0; 4203 } 4204 else 4205 { 4206 factorsFoundIndex= new int [NTLNe.NumCols()]; 4207 for (long i= 0; i < NTLNe.NumCols(); i++) 4208 factorsFoundIndex[i]= 0; 4209 } 4210 int factorsFound= 0; 4211 CanonicalForm bufF= F; 4212 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4213 reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1, 4214 factorsFound, factorsFoundIndex, NTLN, false 4215 ); 4216 else 4217 reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1, 4218 factorsFound, factorsFoundIndex, NTLNe, false 4219 ); 4220 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4221 { 4222 if (result.length() == NTLN.NumCols()) 4223 { 4224 delete [] factorsFoundIndex; 4225 delete [] bounds; 4226 return Union (result, smallFactors); 4227 } 4228 } 4229 else 4230 { 4231 if (result.length() == NTLNe.NumCols()) 4232 { 4233 delete [] factorsFoundIndex; 4234 delete [] bounds; 4235 return Union (result, smallFactors); 4236 } 4237 } 4238 delete [] factorsFoundIndex; 4239 } 4240 if (l >= liftBound) 4241 { 4242 int * factorsFoundIndex; 4243 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4244 { 4245 factorsFoundIndex= new int [NTLN.NumCols()]; 4246 for (long i= 0; i < NTLN.NumCols(); i++) 4247 factorsFoundIndex[i]= 0; 4248 } 4249 else 4250 { 4251 factorsFoundIndex= new int [NTLNe.NumCols()]; 4252 for (long i= 0; i < NTLNe.NumCols(); i++) 4253 factorsFoundIndex[i]= 0; 4254 } 4255 CanonicalForm bufF= F; 4256 int factorsFound= 0; 4257 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4258 reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree 4259 (LCF), factorsFound, factorsFoundIndex, NTLN, false 4260 ); 4261 else 4262 reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree 4263 (LCF), factorsFound, factorsFoundIndex, NTLNe, false 4264 ); 4265 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4266 { 4267 if (result.length() == NTLN.NumCols()) 4268 { 4269 delete [] factorsFoundIndex; 4270 delete [] bounds; 4271 return Union (result, smallFactors); 4272 } 4273 } 4274 else 4275 { 4276 if (result.length() == NTLNe.NumCols()) 4277 { 4278 delete [] factorsFoundIndex; 4279 delete [] bounds; 4280 return Union (result, smallFactors); 4281 } 4282 } 4283 delete [] factorsFoundIndex; 4284 } 4285 4286 result= CFList(); 4287 bool beenInThres= false; 4288 int thres= 100; 4289 if (l <= thres) 4290 { 4291 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4292 { 4293 if (NTLN.NumCols() < bufUniFactors.length()) 4294 { 4295 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi, 4296 diophant 4297 ); 4298 beenInThres= true; 4299 } 4300 } 4301 else 4302 { 4303 if (NTLNe.NumCols() < bufUniFactors.length()) 4304 { 4305 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi, 4306 diophant 4307 ); 4308 beenInThres= true; 4309 } 4310 } 4311 } 4312 4313 CanonicalForm bufF= F; 4314 int factorsFound= 0; 4315 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4316 { 4317 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l, 4318 factorsFound, beenInThres, M, Pi, 4319 diophant 4320 ); 4321 4322 if (result.length() == NTLN.NumCols()) 4323 { 4324 delete [] bounds; 4325 return Union (result, smallFactors); 4326 } 4327 } 4328 else 4329 { 4330 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l, 4331 factorsFound, beenInThres, M, Pi, 4332 diophant 4333 ); 4334 4335 if (result.length() == NTLNe.NumCols()) 4336 { 4337 delete [] bounds; 4338 return Union (result, smallFactors); 4339 } 4340 } 4341 4342 if (result.length() > 0) 4343 { 4344 if (beenInThres) 4345 { 4346 int index; 4347 for (CFListIterator i= result; i.hasItem(); i++) 4348 { 4349 index= 1; 4350 CanonicalForm tmp1, tmp2; 4351 tmp1= mod (i.getItem(), y); 4352 tmp1 /= Lc (tmp1); 4353 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++) 4354 { 4355 tmp2= mod (j.getItem(), y); 4356 tmp2 /= Lc (tmp2); 4357 if (tmp1 == tmp2) 4358 { 4359 index++; 4360 j.remove(index); 4361 break; 4362 } 4363 } 4364 } 4365 } 4366 else 4367 { 4368 int * zeroOne= extractZeroOneVecs (NTLN); 4369 CFList bufBufUniFactors= bufUniFactors; 4370 for (int i= 0; i < NTLN.NumCols(); i++) 4371 { 4372 if (zeroOne [i] == 0) 4373 continue; 4374 CFListIterator iter= bufUniFactors; 4375 CanonicalForm buf= 1; 4376 CFList factorsConsidered; 4377 for (int j= 0; j < NTLN.NumRows(); j++, iter++) 4378 { 4379 if (!IsZero (NTLN (j + 1,i + 1))) 4380 { 4381 factorsConsidered.append (iter.getItem()); 4382 buf *= mod (iter.getItem(), y); 4383 } 4384 } 4385 buf /= Lc (buf); 4386 for (CFListIterator iter2= result; iter2.hasItem(); iter2++) 4387 { 4388 CanonicalForm tmp= mod (iter2.getItem(), y); 4389 tmp /= Lc (tmp); 4390 if (tmp == buf) 4391 { 4392 bufBufUniFactors= Difference (bufBufUniFactors, factorsConsidered); 4393 break; 4394 } 4395 } 4396 } 4397 bufUniFactors= bufBufUniFactors; 4398 delete [] zeroOne; 4399 } 4400 4401 int oldNumCols; 4402 CFList resultBufF; 4403 irreducible= false; 4404 4405 if (alpha.level() == 1) 4406 { 4407 oldNumCols= NTLN.NumCols(); 4408 resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound, 4409 oldNumCols, oldL, l 4410 ); 4411 } 4412 else 4413 { 4414 if (reduceFq2Fp) 4415 { 4416 oldNumCols= NTLN.NumCols(); 4417 4418 resultBufF= increasePrecisionFq2Fp (bufF, bufUniFactors, factorsFound, 4419 oldNumCols, oldL, alpha, l 4420 ); 4421 } 4422 else 4423 { 4424 oldNumCols= NTLNe.NumCols(); 4425 4426 resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound, 4427 oldNumCols, oldL, alpha, l 4428 ); 4429 } 4430 } 4431 4432 if (bufUniFactors.isEmpty() || degree (bufF) <= 0) 4433 { 4434 delete [] bounds; 4435 result= Union (resultBufF, result); 4436 return Union (result, smallFactors); 4437 } 4438 4439 for (CFListIterator i= bufUniFactors; i.hasItem(); i++) 4440 i.getItem()= mod (i.getItem(), y); 4441 4442 result= Union (result, resultBufF); 4443 result= Union (result, smallFactors); 4444 delete [] bounds; 4445 DegreePattern bufDegs= DegreePattern (bufUniFactors); 4446 degs.intersect (bufDegs); 4447 degs.refine(); 4448 if (degs.getLength() == 1 || bufUniFactors.length() == 1) 4449 { 4450 result.append (bufF); 4451 return result; 4452 } 4453 return Union (result, henselLiftAndLatticeRecombi (bufF, bufUniFactors, 4454 alpha, degs 4455 ) 4456 ); 4457 } 4458 4459 if (l < liftBound) 4460 { 4461 if (alpha.level() == 1) 4462 { 4463 result=increasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ, 4464 NTLN 4465 ); 4466 } 4467 else 4468 { 4469 if (reduceFq2Fp) 4470 { 4471 result=increasePrecisionFq2Fp (F, bufUniFactors, oldL, l, d, bounds, 4472 bufQ, NTLN, alpha 4473 ); 4474 } 4475 else 4476 { 4477 result=increasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ, 4478 NTLNe 4479 ); 4480 } 4481 } 4482 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4483 { 4484 if (result.length()== NTLN.NumCols()) 4485 { 4486 delete [] bounds; 4487 result= Union (result, smallFactors); 4488 return result; 4489 } 4490 } 4491 else 4492 { 4493 if (result.length()== NTLNe.NumCols()) 4494 { 4495 delete [] bounds; 4496 result= Union (result, smallFactors); 4497 return result; 4498 } 4499 } 4500 4501 if (result.isEmpty()) 4502 { 4503 if (alpha.level() == 1) 4504 result= furtherLiftingAndIncreasePrecision (F,bufUniFactors, l, 4505 liftBound, d, bounds, NTLN, 4506 diophant, M, Pi, bufQ 4507 ); 4508 else 4509 { 4510 if (reduceFq2Fp) 4511 result= furtherLiftingAndIncreasePrecisionFq2Fp (F,bufUniFactors, l, 4512 liftBound, d, bounds, 4513 NTLN, diophant, M, 4514 Pi, bufQ, alpha 4515 ); 4516 else 4517 result= furtherLiftingAndIncreasePrecision (F,bufUniFactors, l, 4518 liftBound, d, bounds, 4519 NTLNe, diophant, M, 4520 Pi, bufQ 4521 ); 4522 } 4523 4524 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp)) 4525 { 4526 if (result.length() == NTLN.NumCols()) 4527 { 4528 delete [] bounds; 4529 result= Union (result, smallFactors); 4530 return result; 4531 } 4532 } 4533 else 4534 { 4535 if (result.length() == NTLNe.NumCols()) 4536 { 4537 delete [] bounds; 4538 result= Union (result, smallFactors); 4539 return result; 4540 } 4541 } 4542 } 4543 } 4544 4545 DEBOUTLN (cerr, "lattice recombination failed"); 4546 4547 DegreePattern bufDegs= DegreePattern (bufUniFactors); 4548 degs.intersect (bufDegs); 4549 degs.refine(); 4550 4551 delete [] bounds; 4552 bounds= computeBounds (F, d); 4553 minBound= bounds[0]; 4554 for (int i= 1; i < d; i++) 4555 { 4556 if (bounds[i] != 0) 4557 minBound= tmin (minBound, bounds[i]); 4558 } 4559 4560 if (minBound > 16 || result.length() == 0) 4561 { 4562 result= Union (result, smallFactors); 4563 CanonicalForm MODl= power (y, degree (F) + 1 + degree (LC (F, 1))); 4564 delete [] bounds; 4565 return Union (result, factorRecombination (bufUniFactors, F, MODl, degs, 1, 4566 bufUniFactors.length()/2 4567 ) 4568 ); 4569 } 4570 else 4571 { 4572 result= Union (result, smallFactors); 4573 for (CFListIterator i= bufUniFactors; i.hasItem(); i++) 4574 i.getItem()= mod (i.getItem(), y); 4575 delete [] bounds; 4576 return Union (result, henselLiftAndLatticeRecombi (F, bufUniFactors, alpha, 4577 degs 4578 ) 4579 ); 4580 } 4581 } 4582 4583 ExtensionInfo 4584 init4ext (const ExtensionInfo& info, const CanonicalForm& evaluation, 4585 int& degMipo 4586 ) 4587 { 4588 bool GF= (CFFactory::gettype() == GaloisFieldDomain); 4589 Variable alpha= info.getAlpha(); 4590 if (GF) 4591 { 4592 degMipo= getGFDegree(); 4593 CanonicalForm GFMipo= gf_mipo; 4594 setCharacteristic (getCharacteristic()); 4595 GFMipo.mapinto(); 4596 alpha= rootOf (GFMipo); 4597 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 4598 } 4599 else 4600 { 4601 alpha= info.getAlpha(); 4602 degMipo= degree (getMipo (alpha)); 4603 } 4604 4605 Variable gamma; 4606 CanonicalForm primElemAlpha, imPrimElemAlpha; 4607 if ((!GF && evaluation != alpha) || (GF && evaluation != getGFGenerator())) 4608 { 4609 CanonicalForm bufEvaluation; 4610 if (GF) 4611 { 4612 setCharacteristic (getCharacteristic()); 4613 bufEvaluation= GF2FalphaRep (evaluation, alpha); 4614 } 4615 else 4616 bufEvaluation= evaluation; 4617 CanonicalForm mipo= findMinPoly (bufEvaluation, alpha); 4618 gamma= rootOf (mipo); 4619 Variable V_buf; 4620 bool fail; 4621 primElemAlpha= primitiveElement (alpha, V_buf, fail); 4622 imPrimElemAlpha= map (primElemAlpha, alpha, bufEvaluation, gamma); 4623 4624 if (GF) 4625 setCharacteristic (getCharacteristic(), degMipo, info.getGFName()); 4626 } 4627 else 4628 gamma= alpha; 4629 ExtensionInfo info2= ExtensionInfo (alpha, gamma, primElemAlpha, 4630 imPrimElemAlpha, 1, info.getGFName(), true 4631 ); 4632 4633 return info2; 4634 } 4635 4636 CFList 4637 extHenselLiftAndLatticeRecombi(const CanonicalForm& G, const CFList& uniFactors, 4638 const ExtensionInfo& extInfo, const 4639 DegreePattern& degPat, const CanonicalForm& eval 4640 ) 4641 { 4642 bool GF= (CFFactory::gettype()==GaloisFieldDomain); 4643 CanonicalForm evaluation= eval; 4644 ExtensionInfo info= extInfo; 4645 Variable alpha; 4646 DegreePattern degs= degPat; 4647 CanonicalForm F= G; 4648 Variable x= Variable (1); 4649 Variable y= F.mvar(); 4650 CFList bufUniFactors= uniFactors; 4651 4652 4653 int degMipo; 4654 ExtensionInfo info2= init4ext (info, evaluation, degMipo); 4655 4656 CFList source, dest; 4657 CanonicalForm LCF= LC (F, 1); 4658 4659 int d; 4660 int* bounds= computeBounds (F, d); 4661 int minBound= bounds[0]; 4662 for (int i= 1; i < d; i++) 4663 { 4664 if (bounds[i] != 0) 4665 minBound= tmin (minBound, bounds[i]); 4666 } 4667 4668 4669 CFArray Pi; 4670 CFList diophant; 4671 int liftBound= tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 + 4672 degree (LC (F, 1))); 4673 CFMatrix M= CFMatrix (liftBound, bufUniFactors.length()); 4674 4675 CFList smallFactors; 4676 CanonicalForm H; 4677 bool success; 4678 smallFactors= extSieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi, 4679 M, success, minBound + 1, evaluation, info 4680 ); 4681 4682 if (smallFactors.length() > 0) 4683 { 4684 if (smallFactors.length() == 1) 4685 { 4686 if (smallFactors.getFirst() == F) 4687 { 4688 delete [] bounds; 4689 CFList source, dest; 4690 CanonicalForm tmp= G (y - evaluation, y); 4691 tmp= mapDown (tmp, info, source, dest); 4692 return CFList (tmp); 4693 } 4694 } 4695 if (degs.getLength() <= 1) 4696 { 4697 delete [] bounds; 4698 return smallFactors; 4699 } 4700 } 4701 4702 int index; 4703 for (CFListIterator i= smallFactors; i.hasItem(); i++) 4704 { 4705 index= 1; 4706 CanonicalForm tmp1, tmp2; 4707 tmp1= mod (i.getItem(), y - evaluation); 4708 tmp1 /= Lc (tmp1); 4709 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++) 4710 { 4711 tmp2= mod (j.getItem(), y); 4712 tmp2 /= Lc (tmp2); 4713 if (tmp1 == tmp2) 4714 { 4715 index++; 4716 j.remove(index); 4717 break; 4718 } 4719 } 4720 } 4721 4722 if (bufUniFactors.isEmpty()) 4723 { 4724 delete [] bounds; 4725 return smallFactors; 4726 } 4727 4728 if (success) 4729 { 4730 F= H; 4731 delete [] bounds; 4732 bounds= computeBounds (F, d); 4733 LCF= LC (F, 1); 4734 4735 minBound= bounds[0]; 4736 for (int i= 1; i < d; i++) 4737 { 4738 if (bounds[i] != 0) 4739 minBound= tmin (minBound, bounds[i]); 4740 } 4741 Pi= CFArray(); 4742 diophant= CFList(); 4743 liftBound=tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 + 4744 degree (LC (F, 1))); 4745 M= CFMatrix (liftBound, bufUniFactors.length()); 4746 DegreePattern bufDegs= DegreePattern (bufUniFactors); 4747 degs.intersect (bufDegs); 4748 degs.refine(); 4749 if (degs.getLength() <= 1) 4750 { 4751 delete [] bounds; 4752 CFList source, dest; 4753 CanonicalForm tmp= F (y - evaluation, y); 4754 tmp= mapDown (tmp, info, source, dest); 4755 smallFactors.append (tmp); 4756 return smallFactors; 4757 } 4758 } 4759 4760 bufUniFactors.insert (LCF); 4761 int l= 1; 4762 4763 zz_p::init (getCharacteristic()); 4764 zz_pX NTLMipo; 4765 mat_zz_p NTLN; 4766 4767 ident (NTLN, bufUniFactors.length() - 1); 4768 bool wasInBounds= false; 4769 bool irreducible= false; 4770 CFArray bufQ= CFArray (bufUniFactors.length() - 1); 4771 4772 int oldL; 4773 if (success) 4774 { 4775 int start= 0; 4776 oldL= extLiftAndComputeLattice (F, bounds, d, liftBound, minBound, start, 4777 bufUniFactors, NTLN, diophant, M, Pi, bufQ, 4778 irreducible, evaluation, info2, source, dest 4779 ); 4780 } 4781 else 4782 { 4783 oldL= extLiftAndComputeLattice (F, bounds, d, liftBound, minBound, 4784 minBound + 1, bufUniFactors, NTLN, diophant, 4785 M, Pi, bufQ, irreducible, evaluation, info2, 4786 source, dest 4787 ); 4788 } 4789 4790 bufUniFactors.removeFirst(); 4791 if (oldL > liftBound) 4792 { 4793 delete [] bounds; 4794 return Union (smallFactors, extFactorRecombination 4795 (bufUniFactors, F, 4796 power (y, degree (F) + 1 + degree (LCF)),info, 4797 degs, evaluation, 1, bufUniFactors.length()/2 4798 ) 4799 ); 4800 } 4801 4802 l= oldL; 4803 if (irreducible) 4804 { 4805 delete [] bounds; 4806 CFList source, dest; 4807 CanonicalForm tmp= F (y - evaluation, y); 4808 tmp= mapDown (tmp, info, source, dest); 4809 return Union (CFList (tmp), smallFactors); 4810 } 4811 4812 CanonicalForm yToL= power (y,l); 4813 4814 CFList result; 4815 if (l >= degree (F) + 1) 4816 { 4817 int * factorsFoundIndex; 4818 4819 factorsFoundIndex= new int [NTLN.NumCols()]; 4820 for (long i= 0; i < NTLN.NumCols(); i++) 4821 factorsFoundIndex[i]= 0; 4822 4823 int factorsFound= 0; 4824 CanonicalForm bufF= F; 4825 4826 extReconstructionTry (result, bufF, bufUniFactors, degree (F) + 1, 4827 factorsFound, factorsFoundIndex, NTLN, false, info, 4828 evaluation 4829 ); 4830 4831 if (result.length() == NTLN.NumCols()) 4832 { 4833 delete [] factorsFoundIndex; 4834 delete [] bounds; 4835 return Union (result, smallFactors); 4836 } 4837 4838 delete [] factorsFoundIndex; 4839 } 4840 if (l >= liftBound) 4841 { 4842 int * factorsFoundIndex; 4843 factorsFoundIndex= new int [NTLN.NumCols()]; 4844 for (long i= 0; i < NTLN.NumCols(); i++) 4845 factorsFoundIndex[i]= 0; 4846 CanonicalForm bufF= F; 4847 int factorsFound= 0; 4848 4849 extReconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree 4850 (LCF), factorsFound, factorsFoundIndex, NTLN, false, 4851 info, evaluation 4852 ); 4853 4854 if (result.length() == NTLN.NumCols()) 4855 { 4856 delete [] factorsFoundIndex; 4857 delete [] bounds; 4858 return Union (result, smallFactors); 4859 } 4860 delete [] factorsFoundIndex; 4861 } 4862 4863 result= CFList(); 4864 bool beenInThres= false; 4865 int thres= 100; 4866 if (l <= thres && bufUniFactors.length() > NTLN.NumCols()) 4867 { 4868 refineAndRestartLift (F, NTLN, 2*totaldegree (F)-1, l, bufUniFactors, M, Pi, 4869 diophant 4870 ); 4871 beenInThres= true; 4872 } 4873 4874 4875 CanonicalForm bufF= F; 4876 int factorsFound= 0; 4877 4878 result= extEarlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l, 4879 factorsFound, beenInThres, M, Pi, 4880 diophant, info, evaluation 4881 ); 4882 4883 if (result.length() == NTLN.NumCols()) 4884 { 4885 delete [] bounds; 4886 return Union (result, smallFactors); 4887 } 4888 4889 if (result.length() > 0) 4890 { 4891 if (beenInThres) 4892 { 4893 int index; 4894 for (CFListIterator i= result; i.hasItem(); i++) 4895 { 4896 index= 1; 4897 CanonicalForm tmp1, tmp2; 4898 tmp1= mod (i.getItem(), y-evaluation); 4899 tmp1 /= Lc (tmp1); 4900 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++) 4901 { 4902 tmp2= mod (j.getItem(), y); 4903 tmp2 /= Lc (tmp2); 4904 if (tmp1 == tmp2) 4905 { 4906 index++; 4907 j.remove(index); 4908 break; 4909 } 4910 } 4911 } 4912 } 4913 else 4914 { 4915 int * zeroOne= extractZeroOneVecs (NTLN); 4916 CFList bufBufUniFactors= bufUniFactors; 4917 for (int i= 0; i < NTLN.NumCols(); i++) 4918 { 4919 if (zeroOne [i] == 0) 4920 continue; 4921 CFListIterator iter= bufUniFactors; 4922 CanonicalForm buf= 1; 4923 CFList factorsConsidered; 4924 for (int j= 0; j < NTLN.NumRows(); j++, iter++) 4925 { 4926 if (!IsZero (NTLN (j + 1,i + 1))) 4927 { 4928 factorsConsidered.append (iter.getItem()); 4929 buf *= mod (iter.getItem(), y); 4930 } 4931 } 4932 buf /= Lc (buf); 4933 for (CFListIterator iter2= result; iter2.hasItem(); iter2++) 4934 { 4935 CanonicalForm tmp= mod (iter2.getItem(), y - evaluation); 4936 tmp /= Lc (tmp); 4937 if (tmp == buf) 4938 { 4939 bufBufUniFactors= Difference (bufBufUniFactors, factorsConsidered); 4940 break; 4941 } 4942 } 4943 } 4944 bufUniFactors= bufBufUniFactors; 4945 delete [] zeroOne; 4946 } 4947 4948 int oldNumCols; 4949 CFList resultBufF; 4950 irreducible= false; 4951 4952 oldNumCols= NTLN.NumCols(); 4953 resultBufF= extIncreasePrecision (bufF, bufUniFactors, factorsFound, 4954 oldNumCols, oldL, evaluation, info2, 4955 source, dest, l 4956 ); 4957 4958 if (bufUniFactors.isEmpty() || degree (bufF) <= 0) 4959 { 4960 delete [] bounds; 4961 result= Union (resultBufF, result); 4962 return Union (result, smallFactors); 4963 } 4964 4965 for (CFListIterator i= bufUniFactors; i.hasItem(); i++) 4966 i.getItem()= mod (i.getItem(), y); 4967 4968 delete [] bounds; 4969 CFList bufResult; 4970 DegreePattern bufDegs= DegreePattern (bufUniFactors); 4971 degs.intersect (bufDegs); 4972 degs.refine(); 4973 result= Union (result, smallFactors); 4974 if (degs.getLength() == 1 || bufUniFactors.length() == 1) 4975 { 4976 result.append (bufF); 4977 return result; 4978 } 4979 return Union (result, extHenselLiftAndLatticeRecombi (bufF, bufUniFactors, 4980 info, degs, evaluation 4981 ) 4982 ); 4983 } 4984 4985 if (l/degMipo < liftBound) 4986 { 4987 result=extIncreasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ, 4988 NTLN, evaluation, info2, source, dest 4989 ); 4990 4991 if (result.length()== NTLN.NumCols()) 4992 { 4993 delete [] bounds; 4994 result= Union (result, smallFactors); 4995 return result; 4996 } 4997 4998 if (result.isEmpty()) 4999 { 5000 result= extFurtherLiftingAndIncreasePrecision (F,bufUniFactors, l, 5001 liftBound, d, bounds, NTLN, 5002 diophant, M, Pi, bufQ, 5003 evaluation, info2, source, 5004 dest 5005 ); 5006 if (result.length()== NTLN.NumCols()) 5007 { 5008 delete [] bounds; 5009 result= Union (result, smallFactors); 5010 return result; 5011 } 5012 } 5013 } 5014 5015 DEBOUTLN (cerr, "lattice recombination failed"); 5016 5017 DegreePattern bufDegs= DegreePattern (bufUniFactors); 5018 degs.intersect (bufDegs); 5019 degs.refine(); 5020 5021 delete [] bounds; 5022 bounds= computeBounds (F, d); 5023 minBound= bounds[0]; 5024 for (int i= 1; i < d; i++) 5025 { 5026 if (bounds[i] != 0) 5027 minBound= tmin (minBound, bounds[i]); 5028 } 5029 5030 if (minBound > 16 || result.length() == 0) 5031 { 5032 result= Union (result, smallFactors); 5033 CanonicalForm MODl= power (y, degree (F) + 1 + degree (LC (F, 1))); 5034 delete [] bounds; 5035 return Union (result, extFactorRecombination (bufUniFactors, F, MODl, info, 5036 degs, evaluation, 1, 5037 bufUniFactors.length()/2 5038 ) 5039 ); 5040 } 5041 else 5042 { 5043 result= Union (result, smallFactors); 5044 for (CFListIterator i= bufUniFactors; i.hasItem(); i++) 5045 i.getItem()= mod (i.getItem(), y); 5046 delete [] bounds; 5047 return Union (result, extHenselLiftAndLatticeRecombi (F, bufUniFactors, 5048 info, degs, evaluation 5049 ) 5050 ); 5051 } 805 5052 } 806 5053 … … 930 5177 } 931 5178 932 bool fail ;5179 bool fail= false; 933 5180 CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf; 934 5181 CFList uniFactors, list, bufUniFactors; … … 946 5193 // degree pattern therefore usually less combinations have to be tried during 947 5194 // the recombination process 948 int factorNums= 5; 949 double logarithm= (double) ilog2 (totaldegree (A)); 950 logarithm /= log2exp; 951 logarithm= ceil (logarithm); 952 if (factorNums < (int) logarithm) 953 factorNums= (int) logarithm; 5195 int factorNums= 3; 954 5196 int subCheck1= substituteCheck (A, x); 955 5197 int subCheck2= substituteCheck (A, y); … … 967 5209 if (fail && (i == 0)) 968 5210 { 969 if (!derivXZero) 970 bufEvaluation= evalPoint (buf, bufAeval, alpha, list, GF, fail); 971 else 972 fail= true; 973 974 if (!fail) 975 { 5211 if (!derivXZero && !fail2) 5212 { 5213 bufEvaluation= bufEvaluation2; 976 5214 int dummy= subCheck2; 977 5215 subCheck2= subCheck1; 978 5216 subCheck1= dummy; 979 5217 A= buf; 5218 bufAeval= bufAeval2; 980 5219 swap2= true; 981 } 5220 fail= false; 5221 } 5222 else 5223 fail= true; 982 5224 } 983 5225 … … 1106 5348 if (bufUniFactors.length() < uniFactors.length()) 1107 5349 { 1108 uniFactors= bufUniFactors; 1109 Aeval= bufAeval; 1110 evaluation= bufEvaluation; 5350 if (!evaluation.isZero()) 5351 { 5352 uniFactors= bufUniFactors; 5353 Aeval= bufAeval; 5354 evaluation= bufEvaluation; 5355 } 1111 5356 } 1112 5357 } … … 1118 5363 if (!derivXZero && !fail2) 1119 5364 { 1120 if ( uniFactors.length() > uniFactors2.length() ||5365 if (!evaluation.isZero() && (uniFactors.length() > uniFactors2.length() || 1121 5366 (uniFactors.length() == uniFactors2.length() 1122 && degs.getLength() > degs2.getLength())) 5367 && degs.getLength() > degs2.getLength()))) 1123 5368 { 1124 5369 degs= degs2; … … 1136 5381 { 1137 5382 CFList source, dest; 1138 ExtensionInfo info2= ExtensionInfo (beta, alpha, delta, gamma, k, 1139 info.getGFName(), info.isInExtension()); 1140 appendMapDown (factors, A, info2, source, dest); 5383 appendMapDown (factors, A, info, source, dest); 1141 5384 } 1142 5385 else … … 1150 5393 A= A (y + evaluation, y); 1151 5394 1152 int liftBound; 1153 if (degree (A, y) == degree (LC (A, x))) 1154 liftBound= degree (LC (A, x)) + 1; 1155 else 1156 liftBound= degree (A, y) + 1 + degree (LC(A, x)); 5395 int liftBound= liftBound= degree (A, y) + 1 + degree (LC(A, x)); 5396 5397 int boundsLength; 5398 int * bounds= computeBounds (A (y - evaluation, y), boundsLength); 5399 int minBound= bounds[0]; 5400 for (int i= 1; i < boundsLength; i++) 5401 { 5402 if (bounds[i] != 0) 5403 minBound= tmin (minBound, bounds[i]); 5404 } 5405 5406 int degMipo= 1; 5407 if (extension && alpha.level() != 1 && k==1) 5408 degMipo= degree (getMipo (alpha)); 1157 5409 1158 5410 DEBOUTLN (cerr, "uniFactors= " << uniFactors); 1159 bool earlySuccess= false; 1160 CFList earlyFactors; 1161 TIMING_START (fac_hensel_lift); 1162 uniFactors= henselLiftAndEarly 5411 5412 if (GF && !extension || (GF && extension && k != 1)) 5413 { 5414 bool earlySuccess= false; 5415 CFList earlyFactors; 5416 TIMING_START (fac_hensel_lift); 5417 uniFactors= henselLiftAndEarly 1163 5418 (A, earlySuccess, earlyFactors, degs, liftBound, 1164 5419 uniFactors, info, evaluation); 1165 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); 1166 DEBOUTLN (cerr, "lifted factors= " << uniFactors); 1167 1168 CanonicalForm MODl= power (y, liftBound); 1169 TIMING_START (fac_factor_recombination); 1170 if (!extension) 1171 factors= factorRecombination (uniFactors, A, MODl, degs); 5420 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); 5421 DEBOUTLN (cerr, "lifted factors= " << uniFactors); 5422 5423 CanonicalForm MODl= power (y, liftBound); 5424 5425 if (extension) 5426 factors= extFactorRecombination (uniFactors, A, MODl, info, degs, 5427 evaluation, 1, uniFactors.length()/2); 5428 else 5429 factors= factorRecombination (uniFactors, A, MODl, degs, 1, 5430 uniFactors.length()/2); 5431 5432 if (earlySuccess) 5433 factors= Union (earlyFactors, factors); 5434 else if (!earlySuccess && degs.getLength() == 1) 5435 factors= earlyFactors; 5436 } 5437 else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32) 5438 { 5439 TIMING_START (fac_hensel_lift); 5440 if (extension) 5441 { 5442 CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs, 5443 evaluation 5444 ); 5445 factors= Union (lll, factors); 5446 } 5447 else if (alpha.level() == 1 && !GF) 5448 { 5449 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs); 5450 factors= Union (lll, factors); 5451 } 5452 else if (!extension && (alpha != Variable (1) || GF)) 5453 { 5454 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs); 5455 factors= Union (lll, factors); 5456 } 5457 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); 5458 DEBOUTLN (cerr, "lifted factors= " << uniFactors); 5459 } 1172 5460 else 1173 factors= extFactorRecombination (uniFactors, A, MODl, info, degs, 1174 evaluation); 1175 TIMING_END_AND_PRINT (fac_factor_recombination, 1176 "time for factor recombination: "); 1177 if (earlySuccess) 1178 factors= Union (earlyFactors, factors); 1179 else if (!earlySuccess && degs.getLength() == 1) 1180 factors= earlyFactors; 1181 5461 { 5462 bool earlySuccess= false; 5463 CFList earlyFactors; 5464 TIMING_START (fac_hensel_lift); 5465 uniFactors= henselLiftAndEarly 5466 (A, earlySuccess, earlyFactors, degs, liftBound, 5467 uniFactors, info, evaluation); 5468 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); 5469 DEBOUTLN (cerr, "lifted factors= " << uniFactors); 5470 5471 CanonicalForm MODl= power (y, liftBound); 5472 if (!extension) 5473 { 5474 factors= factorRecombination (uniFactors, A, MODl, degs, 1, 3); 5475 5476 int oldUniFactorsLength= uniFactors.length(); 5477 if (degree (A) > 0) 5478 { 5479 CFList tmp; 5480 if (alpha.level() == 1) 5481 tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1, 5482 liftBound 5483 ); 5484 else 5485 { 5486 if (degree (A) > getCharacteristic()) 5487 tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(), 5488 1, alpha, liftBound 5489 ); 5490 else 5491 tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1, 5492 alpha, liftBound 5493 ); 5494 } 5495 factors= Union (factors, tmp); 5496 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0 5497 && uniFactors.length() != oldUniFactorsLength) 5498 ) 5499 { 5500 DegreePattern bufDegs= DegreePattern (uniFactors); 5501 degs.intersect (bufDegs); 5502 degs.refine (); 5503 factors= Union (factors, factorRecombination (uniFactors, A, MODl, 5504 degs, 4, 5505 uniFactors.length()/2 5506 ) 5507 ); 5508 } 5509 } 5510 } 5511 else 5512 { 5513 if (beta.level() != 1 || k > 1) 5514 { 5515 if (k > 1) 5516 { 5517 factors= extFactorRecombination (uniFactors, A, MODl, info, degs, 5518 evaluation, 1, uniFactors.length()/2 5519 ); 5520 } 5521 else 5522 { 5523 factors= extFactorRecombination (uniFactors, A, MODl, info, degs, 5524 evaluation, 1, 3 5525 ); 5526 if (degree (A) > 0) 5527 { 5528 CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound); 5529 DegreePattern bufDegs= DegreePattern (tmp); 5530 degs.intersect (bufDegs); 5531 degs.refine (); 5532 factors= Union (factors, extFactorRecombination (tmp, A, MODl, info, 5533 degs, evaluation, 5534 1, tmp.length()/2 5535 ) 5536 ); 5537 } 5538 } 5539 } 5540 else 5541 { 5542 factors= extFactorRecombination (uniFactors, A, MODl, info, degs, 5543 evaluation, 1, 3 5544 ); 5545 int oldUniFactorsLength= uniFactors.length(); 5546 if (degree (A) > 0) 5547 { 5548 int degMipo; 5549 ExtensionInfo info2= init4ext (info, evaluation, degMipo); 5550 5551 CFList source, dest; 5552 CFList tmp= extIncreasePrecision (A, uniFactors, 0, 5553 uniFactors.length(), 1, evaluation, 5554 info2, source, dest, liftBound 5555 ); 5556 factors= Union (factors, tmp); 5557 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0 5558 && uniFactors.length() != oldUniFactorsLength) 5559 ) 5560 { 5561 DegreePattern bufDegs= DegreePattern (uniFactors); 5562 degs.intersect (bufDegs); 5563 degs.refine (); 5564 factors= Union (factors,extFactorRecombination (uniFactors, A, MODl, 5565 info, degs, evaluation, 5566 4, uniFactors.length()/2 5567 ) 5568 ); 5569 } 5570 } 5571 } 5572 } 5573 5574 if (earlySuccess) 5575 factors= Union (earlyFactors, factors); 5576 else if (!earlySuccess && degs.getLength() == 1) 5577 factors= earlyFactors; 5578 } 5579 delete [] bounds; 1182 5580 if (!extension) 1183 5581 { … … 1215 5613 setCharacteristic (getCharacteristic(), 2, 'Z'); 1216 5614 A= A.mapinto(); 1217 ExtensionInfo info = ExtensionInfo (extension);1218 factors= biFactorize (A, info );5615 ExtensionInfo info2= ExtensionInfo (extension); 5616 factors= biFactorize (A, info2); 1219 5617 1220 5618 Variable vBuf= rootOf (gf_mipo); … … 1225 5623 else // not able to pass to GF, pass to F_p(\alpha) 1226 5624 { 1227 CanonicalForm mipo= randomIrredpoly ( 3, Variable (1));5625 CanonicalForm mipo= randomIrredpoly (2, Variable (1)); 1228 5626 Variable v= rootOf (mipo); 1229 ExtensionInfo info = ExtensionInfo (v);1230 factors= biFactorize (A, info );5627 ExtensionInfo info2= ExtensionInfo (v); 5628 factors= biFactorize (A, info2); 1231 5629 } 1232 5630 return factors; … … 1240 5638 CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1)); 1241 5639 Variable v= rootOf (mipo); 1242 ExtensionInfo info = ExtensionInfo (v);1243 factors= biFactorize (A, info );5640 ExtensionInfo info2= ExtensionInfo (v); 5641 factors= biFactorize (A, info2); 1244 5642 } 1245 5643 else … … 1247 5645 if (beta == Variable (1)) 1248 5646 { 1249 Variable v= chooseExtension ( A, alpha);5647 Variable v= chooseExtension (alpha, beta, k); 1250 5648 CanonicalForm primElem, imPrimElem; 1251 5649 bool primFail= false; … … 1261 5659 CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem, 1262 5660 source, dest); 1263 ExtensionInfo info = ExtensionInfo (v, alpha, imPrimElem, primElem);1264 factors= biFactorize (bufA, info );5661 ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem); 5662 factors= biFactorize (bufA, info2); 1265 5663 } 1266 5664 else 1267 5665 { 1268 Variable v= chooseExtension ( A, alpha);5666 Variable v= chooseExtension (alpha, beta, k); 1269 5667 CanonicalForm primElem, imPrimElem; 1270 5668 bool primFail= false; … … 1281 5679 dest= CFList(); 1282 5680 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest); 1283 ExtensionInfo info = ExtensionInfo (v, beta, imPrimElem, delta);1284 factors= biFactorize (bufA, info );5681 ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta); 5682 factors= biFactorize (bufA, info2); 1285 5683 } 1286 5684 } … … 1302 5700 A= GF2FalphaRep (A, vBuf); 1303 5701 setCharacteristic (p, extensionDeg, 'Z'); 1304 ExtensionInfo info = ExtensionInfo (extension);1305 factors= biFactorize (A.mapinto(), info );5702 ExtensionInfo info2= ExtensionInfo (extension); 5703 factors= biFactorize (A.mapinto(), info2); 1306 5704 } 1307 5705 else // not able to pass to another GF, pass to F_p(\alpha) … … 1310 5708 Variable vBuf= rootOf (gf_mipo); 1311 5709 A= GF2FalphaRep (A, vBuf); 1312 Variable v= chooseExtension ( A, beta);1313 ExtensionInfo info = ExtensionInfo (v, extension);1314 factors= biFactorize (A, info );5710 Variable v= chooseExtension (vBuf, beta, k); 5711 ExtensionInfo info2= ExtensionInfo (v, extension); 5712 factors= biFactorize (A, info2); 1315 5713 } 1316 5714 } … … 1321 5719 { 1322 5720 setCharacteristic (p, 2*extensionDeg, 'Z'); 1323 ExtensionInfo info = ExtensionInfo (k, cGFName, extension);1324 factors= biFactorize (GFMapUp (A, extensionDeg), info );5721 ExtensionInfo info2= ExtensionInfo (k, cGFName, extension); 5722 factors= biFactorize (GFMapUp (A, extensionDeg), info2); 1325 5723 setCharacteristic (p, extensionDeg, cGFName); 1326 5724 } … … 1330 5728 Variable v1= rootOf (gf_mipo); 1331 5729 A= GF2FalphaRep (A, v1); 1332 Variable v2= chooseExtension ( A, v1);5730 Variable v2= chooseExtension (v1, v1, k); 1333 5731 CanonicalForm primElem, imPrimElem; 1334 5732 bool primFail= false; … … 1344 5742 CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem, 1345 5743 source, dest); 1346 ExtensionInfo info = ExtensionInfo (v2, v1, imPrimElem, primElem);1347 factors= biFactorize (bufA, info );5744 ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem); 5745 factors= biFactorize (bufA, info2); 1348 5746 setCharacteristic (p, k, cGFName); 1349 5747 for (CFListIterator i= factors; i.hasItem(); i++) -
factory/facFqBivar.h
rf876a66 r11bf82 491 491 inline CFList 492 492 extFactorRecombination ( 493 const CFList& factors, ///< [in] list of lifted factors that are 494 ///< monic wrt Variable (1) 495 const CanonicalForm& F, ///< [in] poly to be factored 496 const CanonicalForm& M, ///< [in] Variable (2)^liftBound 497 const ExtensionInfo& info, ///< [in] contains information about 498 ///< extension 499 const CanonicalForm& eval ///< [in] evaluation point 493 CFList& factors, ///< [in,out] list of lifted factors that are 494 ///< monic wrt Variable (1), 495 ///< original factors-factors found 496 CanonicalForm& F, ///< [in,out] poly to be factored, 497 ///< F/factors found 498 const CanonicalForm& M, ///< [in] Variable (2)^liftBound 499 const ExtensionInfo& info,///< [in] contains information about 500 ///< extension 501 DegreePattern& degs, 502 const CanonicalForm& eval,///< [in] evaluation point 503 int s, ///< [in] algorithm starts checking subsets 504 ///< of size s 505 int thres ///< [in] threshold for the size of subsets 506 ///< which are checked, for a full factor 507 ///< recombination choose 508 ///< thres= factors.length()/2 500 509 ); 501 510 … … 507 516 inline CFList 508 517 factorRecombination ( 509 const CFList& factors, ///< [in] list of lifted factors 510 ///< that are monic wrt Variable (1) 511 const CanonicalForm& F, ///< [in] poly to be factored 512 const CanonicalForm& M, ///< [in] Variable (2)^liftBound 513 const DegreePattern& degs ///< [in] degree pattern 518 CFList& factors, ///< [in,out] list of lifted factors 519 ///< that are monic wrt Variable (1) 520 CanonicalForm& F, ///< [in,out] poly to be factored 521 const CanonicalForm& M,///< [in] Variable (2)^liftBound 522 DegreePattern& degs, ///< [in] degree pattern 523 int s, ///< [in] algorithm starts checking 524 ///< subsets of size s 525 int thres ///< [in] threshold for the size of 526 ///< subsets which are checked, for a 527 ///< full factor recombination choose 528 ///< thres= factors.length()/2 514 529 ); 515 530 … … 519 534 /// appropiate size 520 535 Variable chooseExtension ( 521 const CanonicalForm & A, ///< [in] some bivariate poly522 const Variable & beta ///< [in] some algebraic523 ///< variable536 const Variable & alpha, ///< [in] some algebraic variable 537 const Variable & beta, ///< [in] some algebraic variable 538 int k ///< [in] some int 524 539 ); 525 540 -
factory/facFqFactorize.cc
rf876a66 r11bf82 1889 1889 else // not able to pass to GF, pass to F_p(\alpha) 1890 1890 { 1891 Variable v= chooseExtension (A, beta); 1891 CanonicalForm mipo= randomIrredpoly (2, Variable (1)); 1892 Variable v= rootOf (mipo); 1892 1893 ExtensionInfo info= ExtensionInfo (v, extension); 1893 1894 factors= multiFactorize (A, info); … … 1910 1911 if (beta == Variable (1)) 1911 1912 { 1912 Variable v= chooseExtension ( A, alpha);1913 Variable v= chooseExtension (alpha, beta, k); 1913 1914 CanonicalForm primElem, imPrimElem; 1914 1915 bool primFail= false; … … 1929 1930 else 1930 1931 { 1931 Variable v= chooseExtension ( A, alpha);1932 Variable v= chooseExtension (alpha, beta, k); 1932 1933 CanonicalForm primElem, imPrimElem; 1933 1934 bool primFail= false; … … 1973 1974 Variable vBuf= rootOf (gf_mipo); 1974 1975 A= GF2FalphaRep (A, vBuf); 1975 Variable v= chooseExtension ( A, beta);1976 Variable v= chooseExtension (vBuf, beta, k); 1976 1977 ExtensionInfo info= ExtensionInfo (v, extension); 1977 1978 factors= multiFactorize (A, info); … … 1993 1994 Variable v1= rootOf (gf_mipo); 1994 1995 A= GF2FalphaRep (A, v1); 1995 Variable v2= chooseExtension ( A, v1);1996 Variable v2= chooseExtension (v1, v1, k); 1996 1997 CanonicalForm primElem, imPrimElem; 1997 1998 bool primFail= false; 1998 1999 Variable vBuf; 1999 primElem= primitiveElement (v1, v Buf, primFail);2000 primElem= primitiveElement (v1, v1, primFail); 2000 2001 if (primFail) 2001 2002 ; //ERROR -
factory/facHensel.cc
rf876a66 r11bf82 33 33 #include "NTLconvert.h" 34 34 35 static inline36 35 CanonicalForm 37 36 mulNTL (const CanonicalForm& F, const CanonicalForm& G) … … 65 64 } 66 65 67 static inline68 66 CanonicalForm 69 67 modNTL (const CanonicalForm& F, const CanonicalForm& G) … … 102 100 } 103 101 104 static inline105 102 CanonicalForm 106 103 divNTL (const CanonicalForm& F, const CanonicalForm& G) … … 139 136 } 140 137 141 /* static inline138 /* 142 139 void 143 140 divremNTL (const CanonicalForm& F, const CanonicalForm& G, CanonicalForm& Q, -
factory/facHensel.h
rf876a66 r11bf82 33 33 /// 34 34 /// @return @a mulNTL returns F*G 35 static inline36 35 CanonicalForm 37 36 mulNTL (const CanonicalForm& F, ///< [in] a univariate poly … … 43 42 /// 44 43 /// @return @a modNTL returns F mod G 45 static inline46 44 CanonicalForm 47 45 modNTL (const CanonicalForm& F, ///< [in] a univariate poly … … 53 51 /// 54 52 /// @return @a divNTL returns F/G 55 static inline56 53 CanonicalForm 57 54 divNTL (const CanonicalForm& F, ///< [in] a univariate poly … … 61 58 /*/// division with remainder of univariate polys over a finite field using NTL, 62 59 /// if we are in GF factory's default division with remainder is used. 63 static inline64 60 void 65 61 divremNTL (const CanonicalForm& F, ///< [in] a univariate poly
Note: See TracChangeset
for help on using the changeset viewer.
