Changeset ccd1b0 in git
 Timestamp:
 Jun 16, 2011, 2:22:22 PM (12 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
 Children:
 2f128f2c3244812fa0ad92434c4ccb623b9c7b56
 Parents:
 b2e4bd67738eae99b3545e3cbb442aa7d898ae9c
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

Singular/claptmpl.cc
rb2e4bd rccd1b0 59 59 template int tmin ( const int&, const int& ); 60 60 template int tabs ( const int& ); 61 62 template CanonicalForm prod ( const List<CanonicalForm> & ); 61 63 62 64 // place here your own template stuff, not instantiated by factory 
factory/facFqFactorize.cc
rb2e4bd rccd1b0 182 182 183 183 CFList 184 monicFactorRecombi (const CFList& factors,const CanonicalForm& F, const185 CanonicalForm& M, const DegreePattern& degs)186 {187 if (degs.getLength() == 1)188 return CFList(F);189 190 CFList T, S;191 192 T= factors;193 194 int s= 1;195 CFList result;196 CanonicalForm buf= F;197 CanonicalForm LCBuf= LC (buf, Variable (1));198 CanonicalForm g, gg;199 int * v= new int [T.length()];200 for (int i= 0; i < T.length(); i++)201 v[i]= 0;202 bool noSubset= false;203 CFArray TT;204 int subsetDeg;205 DegreePattern bufDegs1= degs, bufDegs2;206 TT= copy (factors);207 while (T.length() >= 2*s)208 {209 while (noSubset == false)210 {211 if (T.length() == s)212 {213 result.append (prodMod (T, M));214 delete [] v;215 return result;216 }217 S= subset (v, s, TT, noSubset);218 if (noSubset) break;219 subsetDeg= subsetDegree (S);220 if (!degs.find (subsetDeg))221 continue;222 else223 {224 g= prodMod0 (S, M);225 gg= mod (g*LCBuf, M); //univariate polys226 gg /= content (gg);227 if (fdivides (LC (gg), LCBuf))228 {229 g= prodMod (S, M);230 gg= mulMod2 (LCBuf, g, M);231 gg /= content (gg, Variable (1));232 if (fdivides (gg, buf))233 {234 result.append (g);235 buf /= gg;236 LCBuf= LC (buf, Variable(1));237 T= Difference (T, S);238 // compute new possible degree pattern239 bufDegs2= DegreePattern (T);240 bufDegs1.intersect (bufDegs2);241 bufDegs1.refine ();242 if (T.length() < 2*s  T.length() == s 243 bufDegs1.getLength() == 1)244 {245 result.append (prodMod (T, M));246 delete [] v;247 return result;248 }249 TT= copy (T);250 indexUpdate (v, s, T.length(), noSubset);251 if (noSubset) break;252 }253 }254 }255 }256 s++;257 if (T.length() < 2*s  T.length() == s)258 {259 result.append (prodMod (T, M));260 delete [] v;261 return result;262 }263 for (int i= 0; i < T.length(); i++)264 v[i]= 0;265 noSubset= false;266 }267 if (T.length() < 2*s)268 result.append (prodMod (T, M));269 270 delete [] v;271 return result;272 }273 274 CFList275 earlyMonicFactorDetect (CanonicalForm& F, CFList& factors,276 int& adaptedLiftBound, DegreePattern& degs,277 bool& success, int deg, const int bound)278 {279 DegreePattern bufDegs1= degs;280 DegreePattern bufDegs2;281 CFList result;282 CFList T= factors;283 CanonicalForm buf= F;284 CanonicalForm LCBuf= LC (buf, Variable (1));285 CanonicalForm g, gg;286 CanonicalForm M= power (F.mvar(), deg);287 int d= bound;288 int e= 0;289 adaptedLiftBound= 0;290 for (CFListIterator i= factors; i.hasItem(); i++)291 {292 if (!bufDegs1.find (degree (i.getItem(), 1)))293 continue;294 else295 {296 gg= i.getItem() (0, 1);297 gg *= LCBuf;298 gg= mod (gg, M);299 if (fdivides (LC (gg), LCBuf))300 {301 g= i.getItem();302 gg= mulMod2 (g, LCBuf, M);303 gg /= content (gg, Variable (1));304 if (fdivides (gg, buf))305 {306 result.append (g);307 CanonicalForm bufbuf= buf;308 buf /= gg;309 d = degree (gg) + degree (LC (gg, 1));310 e= tmax (e, degree (gg) + degree (LC (gg, 1)));311 LCBuf= LC (buf, Variable (1));312 T= Difference (T, CFList (i.getItem()));313 314 // compute new possible degree pattern315 bufDegs2= DegreePattern (T);316 bufDegs1.intersect (bufDegs2);317 bufDegs1.refine ();318 if (bufDegs1.getLength() <= 1)319 {320 result.append (prodMod (T, M));321 break;322 }323 }324 }325 }326 }327 adaptedLiftBound= d;328 329 if (adaptedLiftBound < deg)330 {331 factors= T;332 degs= bufDegs1;333 if (adaptedLiftBound < degree (F) + 1)334 {335 if (d == 1)336 {337 if (e + 1 > deg)338 {339 success= false;340 adaptedLiftBound= deg;341 }342 else343 {344 F= buf;345 success= true;346 if (e + 1 < degree (F) + 1)347 adaptedLiftBound= deg;348 else349 adaptedLiftBound= e + 1;350 }351 }352 else353 {354 success= true;355 F= buf;356 adaptedLiftBound= deg;357 }358 }359 else360 {361 F= buf;362 success= true;363 }364 }365 if (bufDegs1.getLength() <= 1)366 {367 degs= bufDegs1;368 if (!success)369 adaptedLiftBound= deg;370 }371 372 return result;373 }374 375 CFList biFactorizer (const CanonicalForm& F, const Variable& alpha,376 CanonicalForm& bivarEval, int& liftBound)377 {378 CanonicalForm A= F;379 bool GF= (CFFactory::gettype() == GaloisFieldDomain);380 381 if (A.isUnivariate())382 return uniFactorizer (F, alpha, GF);383 384 385 CFMap N;386 A= compress (A, N);387 Variable y= A.mvar();388 A /= Lc(A);389 390 if (y.level() > 2) return CFList (F);391 Variable x= Variable (1);392 393 //remove content and factorize content394 CanonicalForm contentAy= content (A, y);395 CanonicalForm contentAx= content (A, x);396 A= A/(contentAy*contentAx);397 CFList contentAyFactors= uniFactorizer (contentAy, alpha, GF);398 399 //trivial case400 CFList factors;401 if (A.inCoeffDomain())402 {403 append (factors, contentAyFactors);404 decompress (factors, N);405 bivarEval= N (y  bivarEval);406 return factors;407 }408 else if (A.isUnivariate())409 {410 if (A.mvar() == x)411 factors= uniFactorizer (A, alpha, GF);412 append (factors, contentAyFactors);413 decompress (factors, N);414 bivarEval= N (y  bivarEval);415 return factors;416 }417 bool fail;418 CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf;419 CFList uniFactors, list, bufUniFactors;420 DegreePattern degs;421 DegreePattern bufDegs;422 423 int factorNums= 5;424 double logarithm= (double) ilog2 (totaldegree (A));425 logarithm /= log2exp;426 logarithm= ceil (logarithm);427 if (factorNums < (int) logarithm)428 factorNums= (int) logarithm;429 for (int i= 0; i < factorNums; i++)430 {431 if (i == 0)432 Aeval= A (bivarEval, y);433 else if (i > 0 && contentAx.inCoeffDomain())434 {435 Aeval= A;436 evaluation= evalPoint (A, Aeval, alpha, list, GF, fail);437 }438 439 if (fail && (i != 0))440 break;441 442 // univariate factorization443 uniFactors= uniFactorizer (Aeval, alpha, GF);444 445 if (uniFactors.length() == 1)446 {447 append (factors, contentAyFactors);448 if (contentAyFactors.isEmpty())449 factors.append (F/lc(F));450 else451 {452 A= A (y  bivarEval, y);453 A= A/lc (A);454 if (!LC(A, 1).isOne())455 {456 CanonicalForm s,t;457 (void) extgcd (LC (A, 1), power (y, liftBound), s, t);458 A *= s;459 A= mod (A, power (y, liftBound));460 }461 factors.append (A);462 }463 decompress (factors, N);464 bivarEval= N (bivarEval);465 return factors;466 }467 468 // degree analysis469 degs= DegreePattern (uniFactors);470 471 if (i == 0)472 {473 bufAeval= Aeval;474 bufEvaluation= bivarEval;475 bufUniFactors= uniFactors;476 bufDegs= degs;477 if (!contentAx.inCoeffDomain())478 break;479 }480 else481 {482 bufDegs.intersect (degs);483 if (uniFactors.length() < bufUniFactors.length())484 {485 bufUniFactors= uniFactors;486 bufAeval= Aeval;487 bufEvaluation= evaluation;488 }489 }490 491 if (bufDegs.getLength() == 1)492 {493 append (factors, contentAyFactors);494 if (contentAyFactors.isEmpty())495 factors.append (F/lc(F));496 else497 {498 A= A (y  bivarEval, y);499 A= A/lc (A);500 if (!LC(A, 1).isOne())501 {502 CanonicalForm s,t;503 (void) extgcd (LC (A, 1), power (y, liftBound), s, t);504 A *= s;505 A= mod (A, power (y, liftBound));506 }507 factors.append (A);508 }509 decompress (factors, N);510 bivarEval= N (bivarEval);511 return factors;512 }513 list.append (evaluation);514 }515 516 bivarEval= y  bufEvaluation;517 A= A (y + bufEvaluation, y);518 bufUniFactors.insert (LC (A, x));519 520 // Hensel lifting521 CFList diophant;522 CFMatrix M= CFMatrix (liftBound, bufUniFactors.length()  1);523 CFArray Pi;524 bool earlySuccess= false;525 int newLiftBound= 0;526 CFList earlyFactors;527 int smallFactorDeg= 11; //tunable parameter528 if (smallFactorDeg >= liftBound)529 henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M);530 else if (smallFactorDeg >= degree (A, y) + 1)531 {532 henselLift12 (A, bufUniFactors, degree (A, y) + 1, Pi, diophant, M);533 earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound,534 bufDegs, earlySuccess,535 degree (A, y) + 1, liftBound);536 if (bufDegs.getLength() > 1 && !earlySuccess)537 {538 if (newLiftBound > degree (A, y) + 1)539 {540 liftBound= newLiftBound;541 bufUniFactors.insert (LC(A, x));542 henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,543 Pi, diophant, M);544 }545 }546 else if (earlySuccess)547 liftBound= newLiftBound;548 }549 else if (smallFactorDeg < degree (A, y) + 1)550 {551 henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);552 earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound,553 bufDegs, earlySuccess,554 smallFactorDeg, liftBound);555 if (bufDegs.getLength() > 1 && !earlySuccess)556 {557 bufUniFactors.insert (LC (A, x));558 henselLiftResume12 (A, bufUniFactors, smallFactorDeg, degree (A, y) +559 1, Pi, diophant, M);560 earlyFactors= earlyMonicFactorDetect (A, bufUniFactors, newLiftBound,561 bufDegs, earlySuccess,562 degree (A, y) + 1, liftBound);563 if (bufDegs.getLength() > 1 && !earlySuccess)564 {565 if (newLiftBound > degree (A, y) + 1)566 {567 if (newLiftBound < newLiftBound)568 liftBound= newLiftBound;569 bufUniFactors.insert (LC(A, x));570 henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,571 Pi, diophant, M);572 }573 }574 else if (earlySuccess)575 liftBound= newLiftBound;576 }577 else if (earlySuccess)578 liftBound= newLiftBound;579 }580 581 if (newLiftBound > 0)582 liftBound= newLiftBound;583 584 CanonicalForm MODl= power (y, liftBound);585 586 if (bufDegs.getLength() > 1)587 factors= monicFactorRecombi (bufUniFactors, A, MODl, bufDegs);588 589 if (earlySuccess)590 factors= Union (earlyFactors, factors);591 else if (!earlySuccess && bufDegs.getLength() == 1)592 factors= earlyFactors;593 594 decompressAppend (factors, contentAyFactors, N);595 596 bivarEval= N (bivarEval);597 598 return factors;599 }600 601 CFList602 184 extFactorRecombination (const CFList& factors, const CanonicalForm& F, 603 185 const CFList& M, const ExtensionInfo& info, … … 628 210 CFList result; 629 211 CanonicalForm buf; 630 if (beta != Variable (1)) 631 buf= mapDown (F, gamma, delta, alpha, source, dest); 632 else 633 buf= F; 212 213 buf= F; 634 214 635 215 CanonicalForm g, LCBuf= LC (buf, Variable (1)); … … 738 318 appendMapDown (result, buf, info, source, dest); 739 319 } 740 delete[] v;741 320 742 321 delete [] v; … … 1182 761 int l= F.level(); 1183 762 eval.insert (F); 763 bool bad= false; 1184 764 for (CFListIterator i= result; i.hasItem(); i++, l) 765 { 1185 766 eval.insert (eval.getFirst()(i.getItem(), l)); 767 if (degree (eval.getFirst(), l  1) != degree (F, l  1)) 768 { 769 if (!find (list, random)) 770 list.append (random); 771 result= CFList(); 772 eval= CFList(); 773 bad= true; 774 break; 775 } 776 } 777 778 if (bad) 779 continue; 1186 780 1187 781 if (degree (eval.getFirst()) != degree (F, 1)) … … 1231 825 static inline 1232 826 int newMainVariableSearch (CanonicalForm& A, CFList& Aeval, CFList& 1233 evaluation, const Variable& alpha, const int lev) 827 evaluation, const Variable& alpha, const int lev, 828 CanonicalForm& g 829 ) 1234 830 { 1235 831 Variable x= Variable (1); … … 1247 843 if (!derivI.isZero()) 1248 844 { 845 g= gcd (buf, derivI); 846 if (degree (g) > 0) 847 return 1; 848 1249 849 buf= swapvar (buf, x, Variable (i)); 1250 850 Aeval= CFList(); … … 1564 1164 1565 1165 CFList 1166 leadingCoeffReconstruction (const CanonicalForm& F, const CFList& factors, 1167 const CFList& M) 1168 { 1169 CanonicalForm buf= F; 1170 CanonicalForm LCBuf= LC (buf, 1); 1171 1172 CFList result; 1173 1174 for (CFListIterator i= factors; i.hasItem(); i++) 1175 { 1176 CanonicalForm tmp= i.getItem(); 1177 tmp= mulMod (tmp, LCBuf, M); 1178 tmp= tmp/content (tmp, 1); 1179 if (fdivides (tmp, buf)) 1180 { 1181 buf /= tmp; 1182 result.append (tmp); 1183 LCBuf= LC (buf, 1); 1184 } 1185 else //no onetoone correspondence 1186 return CFList(); 1187 } 1188 1189 return result; 1190 } 1191 1192 void 1193 gcdFreeBasis (CFFList& factors1, CFFList& factors2) 1194 { 1195 CanonicalForm g; 1196 int k= factors1.length(); 1197 int l= factors2.length(); 1198 int n= 1; 1199 int m; 1200 for (CFFListIterator i= factors1; (i.hasItem() && n < k); i++, n++) 1201 { 1202 m= 1; 1203 for (CFFListIterator j= factors2; (j.hasItem() && m < l); j++, m++) 1204 { 1205 CanonicalForm g= gcd (i.getItem().factor(), j.getItem().factor()); 1206 if (degree (g) > 0) 1207 { 1208 j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp()); 1209 i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp()); 1210 factors1.append (CFFactor (g, i.getItem().exp())); 1211 factors2.append (CFFactor (g, j.getItem().exp())); 1212 } 1213 } 1214 } 1215 } 1216 1217 CFList 1218 distributeContent (const CFList& L, const CFList* differentSecondVarFactors, 1219 int length, const CFList& factors 1220 ) 1221 { 1222 CFList l= L; 1223 CanonicalForm content= l.getFirst(); 1224 1225 if (content.inCoeffDomain()) 1226 return l; 1227 1228 if (l.length() == 1) 1229 { 1230 CFList result; 1231 for (int i= 0; i < length; i++) 1232 { 1233 if (differentSecondVarFactors[i].isEmpty()) 1234 continue; 1235 if (result.isEmpty()) 1236 { 1237 result= differentSecondVarFactors[i]; 1238 for (CFListIterator iter= result; iter.hasItem(); iter++) 1239 content /= iter.getItem(); 1240 } 1241 else 1242 { 1243 CFListIterator iter1= result; 1244 for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem(); 1245 iter2++, iter1++) 1246 { 1247 iter1.getItem() *= iter2.getItem(); 1248 content /= iter2.getItem(); 1249 } 1250 } 1251 } 1252 result.insert (content); 1253 return result; 1254 } 1255 1256 for (int i= 0; i < length; i++) 1257 { 1258 if (differentSecondVarFactors[i].isEmpty()) 1259 continue; 1260 CFListIterator iter1= l; 1261 iter1++; 1262 1263 Variable v= Variable (i + 3); 1264 for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem(); 1265 iter2++, iter1++) 1266 { 1267 if (degree (iter2.getItem(),v) == degree (iter1.getItem(),v)) 1268 continue; 1269 CanonicalForm tmp= iter1.getItem(); 1270 for (int j= tmp.level(); j > 1; j) 1271 { 1272 if (j == i + 3) 1273 continue; 1274 tmp= tmp (0, j); 1275 } 1276 CanonicalForm g= gcd (iter2.getItem(), content); 1277 if (degree (g) > 0) 1278 { 1279 iter2.getItem() /= tmp; 1280 content /= g; 1281 iter1.getItem() *= g; 1282 } 1283 } 1284 } 1285 1286 l.removeFirst(); 1287 l.insert (content); 1288 return l; 1289 } 1290 1291 static inline 1292 CFList evaluateAtZero (const CanonicalForm& F) 1293 { 1294 CFList result; 1295 CanonicalForm buf= F; 1296 result.insert (buf); 1297 for (int i= F.level(); i > 2; i) 1298 { 1299 buf= buf (0, i); 1300 result.insert (buf); 1301 } 1302 return result; 1303 } 1304 1305 int 1306 testFactors (const CanonicalForm& G, const CFList& uniFactors, 1307 const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors, 1308 CFFList*& bufSqrfFactors, CFList& evalSqrfPartF) 1309 { 1310 for (CFListIterator i= uniFactors; i.hasItem(); i++) 1311 { 1312 CanonicalForm tmp= i.getItem(); 1313 if (i.hasItem()) 1314 i++; 1315 else 1316 break; 1317 for (CFListIterator j= i; j.hasItem(); j++) 1318 { 1319 if (tmp == j.getItem()) 1320 return 0; 1321 } 1322 } 1323 1324 CanonicalForm F= G; 1325 CFFList sqrfFactorization= squarefreeFactorization (F, alpha); 1326 1327 sqrfPartF= 1; 1328 for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++) 1329 sqrfPartF *= i.getItem().factor(); 1330 1331 evalSqrfPartF= evaluateAtZero (sqrfPartF); 1332 1333 CanonicalForm test= evalSqrfPartF.getFirst() (0, 2); 1334 1335 if (degree (test) != degree (sqrfPartF, 1)) 1336 return 0; 1337 1338 CFFList sqrfFactors; 1339 CFList tmp2; 1340 int k= 0; 1341 factors= uniFactors; 1342 for (CFListIterator i= factors; i.hasItem(); i++, k++) 1343 { 1344 CanonicalForm tmp= 1; 1345 sqrfFactors= squarefreeFactorization (i.getItem(), alpha); 1346 1347 for (CFFListIterator j= sqrfFactors; j.hasItem(); j++) 1348 { 1349 tmp2.append (j.getItem().factor()); 1350 tmp *= j.getItem().factor(); 1351 } 1352 i.getItem()= tmp/Lc(tmp); 1353 bufSqrfFactors [k]= sqrfFactors; 1354 } 1355 1356 for (int i= 0; i < factors.length()  1; i++) 1357 { 1358 for (int k= i + 1; k < factors.length(); k++) 1359 { 1360 gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]); 1361 } 1362 } 1363 1364 factors= CFList(); 1365 for (int i= 0; i < uniFactors.length(); i++) 1366 { 1367 if (i == 0) 1368 { 1369 for (CFFListIterator k= bufSqrfFactors [i]; k.hasItem(); k++) 1370 { 1371 k.getItem()= CFFactor (k.getItem().factor()/Lc (k.getItem().factor()), 1372 k.getItem().exp()); 1373 factors.append (k.getItem().factor()); 1374 } 1375 } 1376 else 1377 { 1378 for (CFFListIterator k= bufSqrfFactors [i]; k.hasItem(); k++) 1379 { 1380 k.getItem()= CFFactor (k.getItem().factor()/Lc (k.getItem().factor()), 1381 k.getItem().exp()); 1382 if (!find (factors, k.getItem().factor())) 1383 factors.append (k.getItem().factor()); 1384 } 1385 } 1386 } 1387 1388 test= prod (factors); 1389 CanonicalForm tmp= evalSqrfPartF.getFirst() (0,2); 1390 if (test/Lc (test) != tmp/Lc (tmp)) 1391 return 0; 1392 else 1393 return 1; 1394 } 1395 1396 CFList 1397 precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors, 1398 const Variable& alpha, const CFList& evaluation, 1399 CFList* & differentSecondVarLCs, int length, 1400 Variable& y 1401 ) 1402 { 1403 y= Variable (1); 1404 if (LCF.inCoeffDomain()) 1405 { 1406 CFList result; 1407 for (int i= 1; i <= LCFFactors.length() + 1; i++) 1408 result.append (1); 1409 return result; 1410 } 1411 1412 CFMap N; 1413 CanonicalForm F= compress (LCF, N); 1414 if (LCF.isUnivariate()) 1415 { 1416 CFList result; 1417 int LCFLevel= LCF.level(); 1418 bool found= false; 1419 if (LCFLevel == 2) 1420 { 1421 //bivariate leading coefficients are already the true leading coefficients 1422 result= LCFFactors; 1423 Variable v= Variable (LCF.mvar()); 1424 CanonicalForm bla= 1; 1425 for (CFListIterator i= result; i.hasItem(); i++) 1426 { 1427 i.getItem()= i.getItem() (v+evaluation.getLast(), v); 1428 bla *= Lc (i.getItem()); 1429 } 1430 found= true; 1431 } 1432 else 1433 { 1434 for (int i= 0; i < length; i++) 1435 { 1436 for (CFListIterator j= differentSecondVarLCs[i]; j.hasItem(); j++) 1437 { 1438 if (j.getItem().level() == LCFLevel) 1439 { 1440 found= true; 1441 break; 1442 } 1443 } 1444 if (found) 1445 { 1446 result= differentSecondVarLCs [i]; 1447 break; 1448 } 1449 } 1450 if (!found) 1451 result= LCFFactors; 1452 } 1453 if (found) 1454 result.insert (Lc (LCF)); 1455 else 1456 result.append (LCF); 1457 return result; 1458 } 1459 1460 CFList factors= LCFFactors; 1461 1462 CFMap dummy; 1463 for (CFListIterator i= factors; i.hasItem(); i++) 1464 { 1465 i.getItem()= compress (i.getItem(), dummy); 1466 i.getItem()= i.getItem() (Variable (1) + evaluation.getLast(), Variable (1)); 1467 } 1468 1469 CanonicalForm sqrfPartF; 1470 CFFList * bufSqrfFactors= new CFFList [factors.length()]; 1471 CFList evalSqrfPartF; 1472 CanonicalForm bufContent; 1473 CFList bufFactors; 1474 int pass= testFactors (F, factors, alpha, sqrfPartF, 1475 bufFactors, bufSqrfFactors, evalSqrfPartF); 1476 1477 bool foundDifferent= false; 1478 Variable z; 1479 Variable x= y; 1480 int j= 0; 1481 if (!pass) 1482 { 1483 int lev; 1484 // LCF is nonconstant here 1485 for (int i= 1; i <= LCF.level(); i++) 1486 { 1487 if(degree (LCF, i) > 0) 1488 { 1489 lev= i  1; 1490 break; 1491 } 1492 } 1493 for (int i= 0; i < length; i++) 1494 { 1495 if (!differentSecondVarLCs [i].isEmpty()) 1496 { 1497 bool allConstant= true; 1498 for (CFListIterator iter= differentSecondVarLCs[i]; iter.hasItem(); 1499 iter++) 1500 { 1501 if (!iter.getItem().inCoeffDomain()) 1502 { 1503 allConstant= false; 1504 y= Variable (iter.getItem().level()); 1505 } 1506 } 1507 if (allConstant) 1508 continue; 1509 1510 bufFactors= differentSecondVarLCs [i]; 1511 for (CFListIterator iter= bufFactors; iter.hasItem(); iter++) 1512 iter.getItem()= swapvar (iter.getItem(), x, y); 1513 CanonicalForm bufF= F; 1514 z= Variable (y.level()  lev); 1515 bufF= swapvar (bufF, x, z); 1516 CFList bufBufFactors= bufFactors; 1517 pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors, 1518 bufSqrfFactors, evalSqrfPartF); 1519 if (pass) 1520 { 1521 foundDifferent= true; 1522 F= bufF; 1523 CFList l= factors; 1524 for (CFListIterator iter= l; iter.hasItem(); iter++) 1525 iter.getItem()= swapvar (iter.getItem(), x, y); 1526 differentSecondVarLCs [i]= l; 1527 j= i; 1528 break; 1529 } 1530 if (!pass && i == length  1) 1531 { 1532 CFList result; 1533 result.append (LCF); 1534 for (int k= 1; k <= factors.length(); k++) 1535 result.append (LCF); 1536 y= Variable (1); 1537 return result; 1538 } 1539 } 1540 } 1541 } 1542 if (!pass) 1543 { 1544 CFList result; 1545 result.append (LCF); 1546 for (int k= 1; k <= factors.length(); k++) 1547 result.append (LCF); 1548 y= Variable (1); 1549 return result; 1550 } 1551 else 1552 factors= bufFactors; 1553 1554 int liftBound= degree (sqrfPartF,2) + degree (LC (sqrfPartF, 1), 2) + 1; 1555 1556 int* liftBounds= liftingBounds (sqrfPartF, liftBound); 1557 1558 bufFactors= factors; 1559 factors.insert (LC (evalSqrfPartF.getFirst(), 1)); 1560 CFMatrix M= CFMatrix (liftBound, factors.length()  1); 1561 CFArray Pi; 1562 CFList diophant; 1563 henselLift12 (evalSqrfPartF.getFirst(), factors, liftBound, Pi, diophant, M, false); 1564 1565 if (sqrfPartF.level() > 2) 1566 factors= henselLift (evalSqrfPartF, factors, liftBounds, 1567 sqrfPartF.level()  1, false); 1568 1569 CFList MOD; 1570 for (int i= 0; i < sqrfPartF.level()  1; i++) 1571 MOD.append (power (Variable (i + 2), liftBounds [i])); 1572 1573 CFList interMedResult= leadingCoeffReconstruction (evalSqrfPartF.getLast(), 1574 factors, MOD); 1575 1576 CFList result; 1577 for (int i= 0; i < LCFFactors.length(); i++) 1578 { 1579 CanonicalForm tmp= 1; 1580 for (CFFListIterator k= bufSqrfFactors[i]; k.hasItem(); k++) 1581 { 1582 int pos= findItem (bufFactors, k.getItem().factor()); 1583 if (pos) 1584 tmp *= power (getItem (interMedResult, pos), k.getItem().exp()); 1585 } 1586 result.append (tmp); 1587 } 1588 1589 for (CFListIterator i= result; i.hasItem(); i++) 1590 { 1591 F /= i.getItem(); 1592 if (foundDifferent) 1593 i.getItem()= swapvar (i.getItem(), x, z); 1594 i.getItem()= N (i.getItem()); 1595 } 1596 1597 if (foundDifferent) 1598 { 1599 CFList l= differentSecondVarLCs [j]; 1600 for (CFListIterator i= l; i.hasItem(); i++) 1601 i.getItem()= swapvar (i.getItem(), y, z); 1602 differentSecondVarLCs [j]= l; 1603 F= swapvar (F, x, z); 1604 } 1605 1606 result.insert (N (F)); 1607 1608 result= distributeContent (result, differentSecondVarLCs, length, bufFactors); 1609 1610 if (!result.getFirst().inCoeffDomain()) 1611 { 1612 CFListIterator i= result; 1613 CanonicalForm tmp; 1614 if (foundDifferent) 1615 i.getItem()= swapvar (i.getItem(), Variable (2), y); 1616 1617 tmp= i.getItem(); 1618 1619 i++; 1620 for (; i.hasItem(); i++) 1621 { 1622 if (foundDifferent) 1623 i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp; 1624 else 1625 i.getItem() *= tmp; 1626 } 1627 } 1628 else 1629 y= Variable (1); 1630 1631 return result; 1632 } 1633 1634 void 1635 evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation, 1636 const CanonicalForm& A) 1637 { 1638 for (int i= A.level(); i > 2; i) 1639 { 1640 CanonicalForm tmp= A; 1641 CFList tmp2= CFList(); 1642 CFListIterator iter= evaluation; 1643 bool preserveDegree= true; 1644 for (int j= A.level(); j > 1; j, iter++) 1645 { 1646 if (j == i) 1647 continue; 1648 else 1649 { 1650 tmp= tmp (iter.getItem(), j); 1651 tmp2.insert (tmp); 1652 if ((degree (tmp, i) != degree (A, i))  1653 (degree (tmp, 1) != degree (A, 1))) 1654 { 1655 preserveDegree= false; 1656 break; 1657 } 1658 if (!content(tmp).inCoeffDomain()  !content(tmp,1).inCoeffDomain()) 1659 { 1660 preserveDegree= false; 1661 break; 1662 } 1663 } 1664 } 1665 if (preserveDegree) 1666 Aeval [i  3]= tmp2; 1667 else 1668 Aeval [i  3]= CFList(); 1669 } 1670 } 1671 1672 static inline 1673 CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint, 1674 const Variable& v) 1675 { 1676 CanonicalForm result= 1; 1677 for (CFListIterator i= l; i.hasItem(); i++) 1678 result *= i.getItem() (evalPoint, v); 1679 return result; 1680 } 1681 1682 //recombine bivariate factors in case one bivariate factorization yields less 1683 // factors than the other 1684 CFList 1685 recombination (const CFList& factors1, const CFList& factors2, int s, int thres, 1686 const CanonicalForm& evalPoint, const Variable& x) 1687 { 1688 CFList T, S; 1689 1690 T= factors1; 1691 CFList result; 1692 CanonicalForm buf; 1693 int * v= new int [T.length()]; 1694 for (int i= 0; i < T.length(); i++) 1695 v[i]= 0; 1696 bool nosubset= false; 1697 CFArray TT; 1698 TT= copy (factors1); 1699 while (T.length() >= 2*s && s <= thres) 1700 { 1701 while (nosubset == false) 1702 { 1703 if (T.length() == s) 1704 { 1705 delete [] v; 1706 result.append (prod (T)); 1707 return result; 1708 } 1709 S= subset (v, s, TT, nosubset); 1710 if (nosubset) break; 1711 buf= prodEval (S, evalPoint, x); 1712 buf /= Lc (buf); 1713 if (find (factors2, buf)) 1714 { 1715 T= Difference (T, S); 1716 result.append (prod (S)); 1717 TT= copy (T); 1718 indexUpdate (v, s, T.length(), nosubset); 1719 if (nosubset) break; 1720 } 1721 } 1722 s++; 1723 if (T.length() < 2*s  T.length() == s) 1724 { 1725 delete [] v; 1726 result.append (prod (T)); 1727 return result; 1728 } 1729 for (int i= 0; i < T.length(); i++) 1730 v[i]= 0; 1731 nosubset= false; 1732 } 1733 1734 delete [] v; 1735 if (T.length() < 2*s) 1736 { 1737 result.append (prod (T)); 1738 return result; 1739 } 1740 1741 return result; 1742 } 1743 1744 void 1745 factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval, 1746 const ExtensionInfo& info, 1747 int& minFactorsLength, bool& irred) 1748 { 1749 Variable x= Variable (1); 1750 minFactorsLength= 0; 1751 irred= false; 1752 for (int j= 0; j < A.level()  2; j++) 1753 { 1754 if (!Aeval[j].isEmpty()) 1755 { 1756 Variable v= Variable (Aeval[j].getFirst().level()); 1757 1758 CFList factors; 1759 if (CFFactory::gettype() == GaloisFieldDomain) 1760 factors= GFBiSqrfFactorize (Aeval[j].getFirst()); 1761 else if (info.getAlpha().level() == 1) 1762 factors= FpBiSqrfFactorize (Aeval[j].getFirst()); 1763 else 1764 factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha()); 1765 1766 factors.removeFirst(); 1767 if (minFactorsLength == 0) 1768 minFactorsLength= factors.length(); 1769 else 1770 minFactorsLength= tmin (minFactorsLength, factors.length()); 1771 1772 if (factors.length() == 1) 1773 { 1774 irred= true; 1775 return; 1776 } 1777 sortList (factors, x); 1778 Aeval [j]= factors; 1779 } 1780 } 1781 } 1782 1783 void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval, 1784 const CFList& uniFactors, const CFList& evaluation 1785 ) 1786 { 1787 for (int j= 0; j < A.level()  2; j++) 1788 { 1789 if (!Aeval[j].isEmpty()) 1790 { 1791 int i= A.level(); 1792 CanonicalForm evalPoint; 1793 for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i) 1794 { 1795 if (i == Aeval[j].getFirst().level()) 1796 { 1797 evalPoint= iter.getItem(); 1798 break; 1799 } 1800 } 1801 1802 Variable v= Variable (i); 1803 if (Aeval[j].length() > uniFactors.length()) 1804 Aeval[j]= recombination (Aeval[j], uniFactors, 1, 1805 Aeval[j].length()  uniFactors.length() + 1, 1806 evalPoint, v); 1807 1808 CFList l; 1809 CanonicalForm buf; 1810 for (CFListIterator iter1= uniFactors; iter1.hasItem(); iter1++) 1811 { 1812 for (CFListIterator iter2= Aeval[j]; iter2.hasItem(); iter2++) 1813 { 1814 buf= mod (iter2.getItem(), v  evalPoint); 1815 buf /= Lc (buf); 1816 if (iter1.getItem() == buf) 1817 { 1818 l.append (iter2.getItem()); 1819 break; 1820 } 1821 } 1822 } 1823 Aeval [j]= l; 1824 1825 CFList LCs; 1826 for (CFListIterator iter= Aeval[j]; iter.hasItem(); iter++) 1827 LCs.append (LC (iter.getItem() (v + evalPoint, v), 1)); 1828 normalize (LCs); 1829 Aeval[j]= LCs; 1830 } 1831 } 1832 } 1833 1834 CFList 1835 buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint, 1836 const Variable& y) 1837 { 1838 CFList result; 1839 CanonicalForm tmp; 1840 for (CFListIterator i= biFactors; i.hasItem(); i++) 1841 { 1842 tmp= mod (i.getItem(), y  evalPoint); 1843 tmp /= Lc (tmp); 1844 result.append (tmp); 1845 } 1846 return result; 1847 } 1848 1849 void refineBiFactors (const CanonicalForm& A, CFList& biFactors, 1850 CFList* const& Aeval, const CFList& evaluation, 1851 int minFactorsLength) 1852 { 1853 for (int j= 0; j < A.level()  2; j++) 1854 { 1855 if (Aeval[j].length() == minFactorsLength) 1856 { 1857 int i= A.level(); 1858 CanonicalForm evalPoint; 1859 for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i) 1860 { 1861 if (i == Aeval[j].getFirst().level()) 1862 { 1863 evalPoint= iter.getItem(); 1864 break; 1865 } 1866 } 1867 1868 Variable v= Variable (i); 1869 CFList list= buildUniFactors (Aeval[j], evalPoint, v); 1870 1871 Variable y= Variable (2); 1872 biFactors= recombination (biFactors, list, 1, 1873 biFactors.length()  list.length() + 1, 1874 evaluation.getLast(), y); 1875 return; 1876 } 1877 } 1878 } 1879 1880 void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs, 1881 const CFList& biFactors) 1882 { 1883 CFList l= leadingCoeffs; 1884 LCs [n3]= l; 1885 for (int i= n  1; i > 2; i) 1886 { 1887 for (CFListIterator j= l; j.hasItem(); j++) 1888 j.getItem()= j.getItem() (0, i + 1); 1889 LCs [i  3]= l; 1890 } 1891 l= LCs [0]; 1892 for (CFListIterator i= l; i.hasItem(); i++) 1893 i.getItem()= i.getItem() (0, 3); 1894 CFListIterator ii= biFactors; 1895 CFList normalizeFactor; 1896 for (CFListIterator i= l; i.hasItem(); i++, ii++) 1897 normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem())); 1898 for (int i= 0; i < n2; i++) 1899 { 1900 ii= normalizeFactor; 1901 for (CFListIterator j= LCs [i]; j.hasItem(); j++, ii++) 1902 j.getItem() *= ii.getItem(); 1903 } 1904 } 1905 1906 CFList recoverFactors (const CanonicalForm& F, const CFList& factors) 1907 { 1908 CFList result; 1909 CanonicalForm tmp; 1910 for (CFListIterator i= factors; i.hasItem(); i++) 1911 { 1912 tmp= i.getItem() / content (i.getItem(), 1); 1913 if (fdivides (tmp, F)) 1914 result.append (tmp); 1915 } 1916 return result; 1917 } 1918 1919 CFList 1920 extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F, 1921 const ExtensionInfo& info, 1922 const CFList& evaluation) 1923 { 1924 Variable alpha= info.getAlpha(); 1925 Variable beta= info.getBeta(); 1926 CanonicalForm gamma= info.getGamma(); 1927 CanonicalForm delta= info.getDelta(); 1928 int k= info.getGFDegree(); 1929 CFList source, dest; 1930 1931 int degMipoBeta= 1; 1932 if (!k && beta != Variable(1)) 1933 degMipoBeta= degree (getMipo (beta)); 1934 1935 CFList T, S; 1936 T= factors; 1937 int s= 1; 1938 CFList result; 1939 CanonicalForm buf= F; 1940 1941 CanonicalForm g; 1942 CanonicalForm buf2; 1943 int * v= new int [T.length()]; 1944 for (int i= 0; i < T.length(); i++) 1945 v[i]= 0; 1946 bool noSubset= false; 1947 CFArray TT; 1948 TT= copy (factors); 1949 bool recombination= false; 1950 bool trueFactor= false; 1951 while (T.length() >= 2*s) 1952 { 1953 while (noSubset == false) 1954 { 1955 if (T.length() == s) 1956 { 1957 delete [] v; 1958 if (recombination) 1959 { 1960 g= prod (T); 1961 T.removeFirst(); 1962 result.append (g/myContent (g)); 1963 g= reverseShift (g, evaluation); 1964 g /= Lc (g); 1965 appendTestMapDown (result, g, info, source, dest); 1966 return result; 1967 } 1968 else 1969 { 1970 buf= reverseShift (buf, evaluation); 1971 return CFList (buf); 1972 } 1973 } 1974 1975 S= subset (v, s, TT, noSubset); 1976 if (noSubset) break; 1977 1978 g= prod (S); 1979 g /= myContent (g); 1980 if (fdivides (g, buf)) 1981 { 1982 buf2= reverseShift (g, evaluation); 1983 buf2 /= Lc (buf2); 1984 if (!k && beta == Variable (1)) 1985 { 1986 if (degree (buf2, alpha) < degMipoBeta) 1987 { 1988 appendTestMapDown (result, buf2, info, source, dest); 1989 buf /= g; 1990 recombination= true; 1991 trueFactor= true; 1992 } 1993 } 1994 else 1995 { 1996 if (!isInExtension (buf2, gamma, k, delta, source, dest)) 1997 { 1998 appendTestMapDown (result, buf2, info, source, dest); 1999 buf /= g; 2000 recombination= true; 2001 trueFactor= true; 2002 } 2003 } 2004 if (trueFactor) 2005 { 2006 T= Difference (T, S); 2007 2008 if (T.length() < 2*s  T.length() == s) 2009 { 2010 delete [] v; 2011 buf= reverseShift (buf, evaluation); 2012 buf /= Lc (buf); 2013 appendTestMapDown (result, buf, info, source, dest); 2014 return result; 2015 } 2016 trueFactor= false; 2017 TT= copy (T); 2018 indexUpdate (v, s, T.length(), noSubset); 2019 if (noSubset) break; 2020 } 2021 } 2022 } 2023 s++; 2024 if (T.length() < 2*s  T.length() == s) 2025 { 2026 delete [] v; 2027 buf= reverseShift (buf, evaluation); 2028 appendTestMapDown (result, buf, info, source, dest); 2029 return result; 2030 } 2031 for (int i= 0; i < T.length(); i++) 2032 v[i]= 0; 2033 noSubset= false; 2034 } 2035 if (T.length() < 2*s) 2036 { 2037 buf= reverseShift (F, evaluation); 2038 appendMapDown (result, buf, info, source, dest); 2039 } 2040 2041 delete [] v; 2042 return result; 2043 } 2044 2045 CFList 1566 2046 extFactorize (const CanonicalForm& F, const ExtensionInfo& info); 1567 2047 … … 1670 2150 { 1671 2151 swapLevel= i; 1672 A= swapvar (A, x, z);2152 bufA= swapvar (A, x, z); 1673 2153 } 1674 2154 gcdDerivZ= gcd (bufA, derivZ); … … 1682 2162 normalize (factorsG); 1683 2163 return factorsG; 2164 } 2165 else 2166 { 2167 A= bufA; 2168 break; 1684 2169 } 1685 2170 } … … 1701 2186 if (factorNums < (int) logarithm) 1702 2187 factorNums= (int) logarithm; 2188 CFList* bufAeval2= new CFList [A.level()  2]; 2189 CFList* Aeval2= new CFList [A.level()  2]; 2190 int counter; 2191 int differentSecondVar= 0; 1703 2192 // several bivariate factorizations 1704 2193 for (int i= 0; i < factorNums; i++) 1705 2194 { 2195 counter= 0; 1706 2196 bufA= A; 1707 2197 bufAeval= CFList(); … … 1716 2206 level= swapLevel + 1; 1717 2207 1718 swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level); 2208 CanonicalForm g; 2209 swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g); 1719 2210 1720 2211 if (!swapLevel2) // need to pass to an extension … … 1723 2214 appendSwapDecompress (factors, contentAFactors, N, swapLevel, x); 1724 2215 normalize (factors); 2216 delete [] bufAeval2; 2217 delete [] Aeval2; 1725 2218 return factors; 1726 2219 } 1727 2220 else 1728 2221 { 2222 if (swapLevel2 == 1) 2223 { 2224 CFList factorsG= 2225 Union (multiFactorize (g, info), 2226 multiFactorize (A/g, info)); 2227 appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x); 2228 normalize (factorsG); 2229 delete [] bufAeval2; 2230 delete [] Aeval2; 2231 return factorsG; 2232 } 1729 2233 fail= false; 1730 2234 bufAeval= Aeval; … … 1737 2241 1738 2242 bivarEval= bufEvaluation.getLast(); 1739 bufEvaluation.removeLast(); 2243 2244 evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A); 2245 2246 for (int j= 0; j < A.level()  1; j++) 2247 { 2248 if (!bufAeval2[j].isEmpty()) 2249 counter++; 2250 } 1740 2251 1741 2252 bufLift= degree (A, y) + 1 + degree (LC(A, x), y); 1742 2253 1743 2254 TIMING_START (fac_bi_factorizer); 1744 bufBiFactors= biFactorizer (bufAeval.getFirst(), alpha, bivarEval, bufLift); 2255 if (!GF && alpha.level() == 1) 2256 bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst()); 2257 else if (GF) 2258 bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst()); 2259 else 2260 bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha); 1745 2261 TIMING_END_AND_PRINT (fac_bi_factorizer, 1746 2262 "time for bivariate factorization: "); 2263 bufBiFactors.removeFirst(); 1747 2264 1748 2265 if (bufBiFactors.length() == 1) … … 1757 2274 swapLevel2, x); 1758 2275 normalize (factors); 2276 delete [] bufAeval2; 2277 delete [] Aeval2; 1759 2278 return factors; 1760 2279 } 1761 2280 1762 bufEvaluation.append (bivarEval[0]);1763 2281 if (i == 0) 1764 2282 { … … 1767 2285 biFactors= bufBiFactors; 1768 2286 lift= bufLift; 2287 for (int j= 0; j < A.level()  2; j++) 2288 Aeval2 [j]= bufAeval2 [j]; 2289 differentSecondVar= counter; 1769 2290 } 1770 2291 else 1771 2292 { 1772 2293 if (bufBiFactors.length() < biFactors.length()  1773 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length()))) 2294 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length()))  2295 counter > differentSecondVar) 1774 2296 { 1775 2297 Aeval= bufAeval; … … 1777 2299 biFactors= bufBiFactors; 1778 2300 lift= bufLift; 2301 for (int j= 0; j < A.level()  2; j++) 2302 Aeval2 [j]= bufAeval2 [j]; 2303 differentSecondVar= counter; 1779 2304 } 1780 2305 } … … 1785 2310 } 1786 2311 2312 delete [] bufAeval2; 2313 2314 sortList (biFactors, x); 2315 2316 int minFactorsLength; 2317 bool irred= false; 2318 factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength, irred); 2319 2320 if (irred) 2321 { 2322 if (extension) 2323 { 2324 CFList source, dest; 2325 A= mapDown (A, info, source, dest); 2326 } 2327 factors.append (A); 2328 appendSwapDecompress (factors, contentAFactors, N, swapLevel, 2329 swapLevel2, x); 2330 normalize (factors); 2331 delete [] Aeval2; 2332 return factors; 2333 } 2334 2335 if (minFactorsLength == 0) 2336 minFactorsLength= biFactors.length(); 2337 else if (biFactors.length() > minFactorsLength) 2338 refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength); 2339 2340 CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y); 2341 2342 CFList * oldAeval= new CFList [A.level()  2]; //TODO use bufAeval2 for this 2343 for (int i= 0; i < A.level()  2; i++) 2344 oldAeval[i]= Aeval2[i]; 2345 2346 getLeadingCoeffs (A, Aeval2, uniFactors, evaluation); 2347 2348 CFList biFactorsLCs; 2349 for (CFListIterator i= biFactors; i.hasItem(); i++) 2350 biFactorsLCs.append (LC (i.getItem(), 1)); 2351 2352 1787 2353 //shifting to zero 1788 2354 A= shift2Zero (A, Aeval, evaluation); 1789 2355 1790 int* liftBounds; 1791 liftBounds= liftingBounds (A, lift); 1792 1793 CFList MOD; 1794 bool earlySuccess; 1795 CFList earlyFactors; 1796 TIMING_START (fac_hensel_lift); 1797 CFList liftedFactors= henselLiftAndEarly 1798 (A, MOD, liftBounds, earlySuccess, earlyFactors, 1799 Aeval, biFactors, evaluation, info); 1800 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); 1801 1802 if (!extension) 1803 { 1804 TIMING_START (fac_factor_recombination); 1805 factors= factorRecombination (A, liftedFactors, MOD); 1806 TIMING_END_AND_PRINT (fac_factor_recombination, 1807 "time for factor recombination: "); 1808 } 1809 else 1810 { 1811 TIMING_START (fac_factor_recombination); 1812 factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation); 1813 TIMING_END_AND_PRINT (fac_factor_recombination, 1814 "time for factor recombination: "); 1815 } 1816 1817 if (earlySuccess) 1818 factors= Union (factors, earlyFactors); 2356 CanonicalForm hh= Lc (Aeval.getFirst()); 2357 2358 for (CFListIterator i= Aeval; i.hasItem(); i++) 2359 i.getItem() /= hh; 2360 2361 A /= hh; 2362 2363 Variable v; 2364 CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha, 2365 evaluation, Aeval2, A.level()  2, v); 2366 2367 if (v.level() != 1) 2368 { 2369 A= swapvar (A, y, v); 2370 for (int i= 0; i < A.level()  2; i++) 2371 { 2372 if (oldAeval[i].isEmpty()) 2373 continue; 2374 if (oldAeval[i].getFirst().level() == v.level()) 2375 { 2376 biFactors= CFList(); 2377 for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++) 2378 biFactors.append (swapvar (iter.getItem(), v, y)); 2379 } 2380 } 2381 int i= A.level(); 2382 CanonicalForm evalPoint; 2383 for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i) 2384 { 2385 if (i == v.level()) 2386 { 2387 evalPoint= iter.getItem(); 2388 iter.getItem()= evaluation.getLast(); 2389 evaluation.removeLast(); 2390 evaluation.append (evalPoint); 2391 break; 2392 } 2393 } 2394 Aeval= evaluateAtZero (A); 2395 } 2396 2397 CFListIterator iter= biFactors; 2398 for (; iter.hasItem(); iter++) 2399 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y); 2400 2401 CanonicalForm oldA= A; 2402 CFList oldBiFactors= biFactors; 2403 if (!leadingCoeffs.getFirst().inCoeffDomain()) 2404 { 2405 CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length()  1); 2406 A *= tmp; 2407 Aeval= evaluateAtZero (A); 2408 tmp= leadingCoeffs.getFirst(); 2409 for (int i= A.level(); i > 2; i) 2410 tmp= tmp (0, i); 2411 if (!tmp.inCoeffDomain()) 2412 { 2413 for (CFListIterator i= biFactors; i.hasItem(); i++) 2414 { 2415 i.getItem() *= tmp/LC (i.getItem(), 1); 2416 i.getItem() /= Lc (i.getItem()); 2417 } 2418 } 2419 hh= Lc (Aeval.getFirst()); 2420 for (CFListIterator i= Aeval; i.hasItem(); i++) 2421 i.getItem() /= hh; 2422 2423 A /= hh; 2424 } 2425 2426 leadingCoeffs.removeFirst(); 2427 2428 //prepare leading coefficients 2429 CFList* leadingCoeffs2= new CFList [A.level()  2]; 2430 prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors); 2431 2432 CFArray Pi; 2433 CFList diophant; 2434 int* liftBounds= new int [A.level()  1]; 2435 int liftBoundsLength= A.level()  1; 2436 for (int i= 0; i < liftBoundsLength; i++) 2437 liftBounds [i]= degree (A, i + 2) + 1; 2438 2439 Aeval.removeFirst(); 2440 bool noOneToOne= false; 2441 factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant, 2442 Pi, liftBounds, liftBoundsLength, noOneToOne); 2443 2444 if (!noOneToOne) 2445 { 2446 int check= factors.length(); 2447 factors= recoverFactors (A, factors); 2448 if (check != factors.length()) 2449 noOneToOne= true; 2450 2451 if (extension && !noOneToOne) 2452 factors= extNonMonicFactorRecombination (factors, oldA, info, evaluation); 2453 } 2454 if (noOneToOne) 2455 { 2456 A= oldA; 2457 Aeval= evaluateAtZero (A); 2458 biFactors= oldBiFactors; 2459 CanonicalForm LCA= LC (Aeval.getFirst(), 1); 2460 CanonicalForm yToLift= power (y, lift); 2461 CFListIterator i= biFactors; 2462 lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1; 2463 i++; 2464 2465 for (; i.hasItem(); i++) 2466 lift= tmax (lift, degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1); 2467 2468 lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift); 2469 2470 i= biFactors; 2471 yToLift= power (y, lift); 2472 CanonicalForm dummy; 2473 for (; i.hasItem(); i++) 2474 { 2475 LCA= LC (i.getItem(), 1); 2476 extgcd (LCA, yToLift, LCA, dummy); 2477 i.getItem()= mod (i.getItem()*LCA, yToLift); 2478 } 2479 2480 liftBoundsLength= F.level()  1; 2481 liftBounds= liftingBounds (A, lift); 2482 2483 CFList MOD; 2484 bool earlySuccess; 2485 CFList earlyFactors; 2486 TIMING_START (fac_hensel_lift); 2487 CFList liftedFactors= henselLiftAndEarly 2488 (A, MOD, liftBounds, earlySuccess, earlyFactors, 2489 Aeval, biFactors, evaluation, info); 2490 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: "); 2491 2492 if (!extension) 2493 { 2494 TIMING_START (fac_factor_recombination); 2495 factors= factorRecombination (A, liftedFactors, MOD); 2496 TIMING_END_AND_PRINT (fac_factor_recombination, 2497 "time for factor recombination: "); 2498 } 2499 else 2500 { 2501 TIMING_START (fac_factor_recombination); 2502 factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation); 2503 TIMING_END_AND_PRINT (fac_factor_recombination, 2504 "time for factor recombination: "); 2505 } 2506 2507 if (earlySuccess) 2508 factors= Union (factors, earlyFactors); 2509 } 1819 2510 1820 2511 if (!extension) … … 1830 2521 } 1831 2522 } 2523 } 2524 2525 if (v.level() != 1) 2526 { 2527 for (CFListIterator iter= factors; iter.hasItem(); iter++) 2528 iter.getItem()= swapvar (iter.getItem(), v, y); 1832 2529 } 1833 2530 … … 1878 2575 CanonicalForm mipo= randomIrredpoly (2, Variable (1)); 1879 2576 Variable v= rootOf (mipo); 1880 ExtensionInfo info= ExtensionInfo (v , extension);2577 ExtensionInfo info= ExtensionInfo (v); 1881 2578 factors= multiFactorize (A, info); 1882 2579 } … … 1907 2604 ; //ERROR 1908 2605 else 1909 imPrimElem= mapPrimElem (primElem, alpha, v);2606 imPrimElem= mapPrimElem (primElem, vBuf, v); 1910 2607 1911 2608 CFList source, dest;
Note: See TracChangeset
for help on using the changeset viewer.