Changeset b1d287 in git for factory/facFqBivar.cc
 Timestamp:
 Aug 1, 2012, 2:25:24 AM (11 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'ad2543eab51733612ba7d118afc77edca719600e')
 Children:
 0df59c8a8e59eded04e4aca4e57cfed188a00cf1
 Parents:
 09afeb85ea17e564813761786f76281c8162dad0362fc6799a207ad61d3be8abe0206e52b5782e50
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/facFqBivar.cc
r09afeb rb1d287 13 13 * 14 14 * @author Martin Lee 15 *16 * @internal @version \$Id$17 15 * 18 16 **/ … … 1333 1331 Variable x= Variable (1); 1334 1332 CanonicalForm yToL= power (y, liftBound); 1333 if (factors.length() == 2) 1334 { 1335 CanonicalForm tmp1, tmp2, tmp3; 1336 tmp1= factors.getFirst(); 1337 tmp2= factors.getLast(); 1338 tmp1 *= LC (F, x); 1339 tmp1= mod (tmp1, yToL); 1340 tmp1 /= content (tmp1, x); 1341 tmp2 *= LC (F, x); 1342 tmp2= mod (tmp2, yToL); 1343 tmp2 /= content (tmp2, x); 1344 tmp3 = tmp1*tmp2; 1345 if (tmp3/Lc (tmp3) == F/Lc (F)) 1346 { 1347 factorsFound++; 1348 F= 1; 1349 reconstructedFactors.append (tmp1); 1350 reconstructedFactors.append (tmp2); 1351 return; 1352 } 1353 } 1335 1354 CanonicalForm quot, buf; 1336 1355 CFListIterator iter; … … 1388 1407 Variable y= Variable (2); 1389 1408 Variable x= Variable (1); 1409 CanonicalForm yToL= power (y, liftBound); 1410 if (factors.length() == 2) 1411 { 1412 CanonicalForm tmp1, tmp2, tmp3; 1413 tmp1= factors.getFirst(); 1414 tmp2= factors.getLast(); 1415 tmp1 *= LC (F, x); 1416 tmp1= mod (tmp1, yToL); 1417 tmp1 /= content (tmp1, x); 1418 tmp2 *= LC (F, x); 1419 tmp2= mod (tmp2, yToL); 1420 tmp2 /= content (tmp2, x); 1421 tmp3 = tmp1*tmp2; 1422 if (tmp3/Lc (tmp3) == F/Lc (F)) 1423 { 1424 factorsFound++; 1425 F= 1; 1426 reconstructedFactors.append (tmp1); 1427 reconstructedFactors.append (tmp2); 1428 return; 1429 } 1430 } 1390 1431 CanonicalForm quot, buf; 1391 CanonicalForm yToL= power (y, liftBound);1392 1432 CFListIterator iter; 1393 1433 for (long i= 1; i <= N.NumCols(); i++) … … 1682 1722 CanonicalForm delta= info.getDelta(); 1683 1723 CanonicalForm yToL= power (y, liftBound); 1724 CFList source, dest; 1725 if (factors.length() == 2) 1726 { 1727 CanonicalForm tmp1, tmp2, tmp3; 1728 tmp1= factors.getFirst(); 1729 tmp2= factors.getLast(); 1730 tmp1 *= LC (F, x); 1731 tmp1= mod (tmp1, yToL); 1732 tmp1 /= content (tmp1, x); 1733 tmp2 *= LC (F, x); 1734 tmp2= mod (tmp2, yToL); 1735 tmp2 /= content (tmp2, x); 1736 tmp3 = tmp1*tmp2; 1737 if (tmp3/Lc (tmp3) == F/Lc (F)) 1738 { 1739 tmp1= tmp1 (y  evaluation, y); 1740 tmp2= tmp2 (y  evaluation, y); 1741 if (!k && beta == x && degree (tmp2, alpha) < 1 && 1742 degree (tmp1, alpha) < 1) 1743 { 1744 factorsFound++; 1745 F= 1; 1746 tmp1= mapDown (tmp1, info, source, dest); 1747 tmp2= mapDown (tmp2, info, source, dest); 1748 reconstructedFactors.append (tmp1); 1749 reconstructedFactors.append (tmp2); 1750 return; 1751 } 1752 else if (!isInExtension (tmp2, gamma, k, delta, source, dest) && 1753 !isInExtension (tmp1, gamma, k, delta, source, dest)) 1754 { 1755 factorsFound++; 1756 F= 1; 1757 tmp1= mapDown (tmp1, info, source, dest); 1758 tmp2= mapDown (tmp2, info, source, dest); 1759 reconstructedFactors.append (tmp1); 1760 reconstructedFactors.append (tmp2); 1761 return; 1762 } 1763 } 1764 } 1684 1765 CanonicalForm quot, buf, buf2; 1685 CFList source, dest;1686 1766 CFListIterator iter; 1687 1767 for (long i= 1; i <= N.NumCols(); i++) … … 4179 4259 CanonicalForm& bufF, CFList& factors, int& l, 4180 4260 int& factorsFound, bool beenInThres, CFMatrix& M, 4181 CFArray& Pi, CFList& diophant 4261 CFArray& Pi, CFList& diophant, bool symmetric, 4262 const CanonicalForm& evaluation 4182 4263 ) 4183 4264 { … … 4249 4330 while ((degree (F,y)/4)*i + 4 <= smallFactorDeg) 4250 4331 i++; 4251 while (i < 4)4252 { 4253 dummy= tmin (degree (F,y)+1, (degree (F,y)/4)* (i+1)+4);4332 while (i < 5) 4333 { 4334 dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4); 4254 4335 if (l < dummy) 4255 4336 { … … 4257 4338 henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M); 4258 4339 l= dummy; 4340 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 && 4341 LC (F,1).inCoeffDomain() && 4342 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1))) 4343 { 4344 Variable x= Variable (1); 4345 CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2; 4346 int m= degree (F)/4+1; 4347 g= factors.getFirst(); 4348 h= factors.getLast(); 4349 g= mod (g, power (y,m)); 4350 h= mod (h, power (y,m)); 4351 g= g (yevaluation, y); 4352 h= h (yevaluation, y); 4353 gg= mod (swapvar (g,x,y),power (x,m)); 4354 gg= gg (y + evaluation, y); 4355 multiplier1= factors.getLast()[m1][0]/gg[m1][0]; 4356 gg= div (gg, power (y,m)); 4357 gg= gg*power (y,m); 4358 hh= mod (swapvar (h,x,y),power (x,m)); 4359 hh= hh (y + evaluation, y); 4360 multiplier2= factors.getFirst()[m1][0]/hh[m1][0]; 4361 hh= div (hh, power (y,m)); 4362 hh= hh*power (y,m); 4363 gg= multiplier1*gg+mod (factors.getLast(), power (y,m)); 4364 hh= multiplier2*hh+mod (factors.getFirst(), power (y,m)); 4365 check1= gg (yevaluation,y); 4366 check2= hh (yevaluation,y); 4367 check1= swapvar (check1, x, y); 4368 if (check1/Lc (check1) == check2/Lc (check2)) 4369 { 4370 result.append (gg); 4371 result.append (hh); 4372 delete [] liftPre; 4373 delete [] factorsFoundIndex; 4374 return result; 4375 } 4376 } 4259 4377 } 4260 4378 else 4261 4379 { 4262 4380 i++; 4263 if (i < 4)4381 if (i < 5) 4264 4382 continue; 4265 4383 } … … 4286 4404 CanonicalForm& bufF, CFList& factors, int& l, 4287 4405 int& factorsFound, bool beenInThres, CFMatrix& M, 4288 CFArray& Pi, CFList& diophant 4406 CFArray& Pi, CFList& diophant, bool symmetric, 4407 const CanonicalForm& evaluation 4289 4408 ) 4290 4409 { … … 4355 4474 while ((degree (F,y)/4)*i + 4 <= smallFactorDeg) 4356 4475 i++; 4357 while (i < 4)4358 { 4359 dummy= tmin (degree (F,y)+1, (degree (F,y)/4)* (i+1)+4);4476 while (i < 5) 4477 { 4478 dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4); 4360 4479 if (l < dummy) 4361 4480 { … … 4363 4482 henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M); 4364 4483 l= dummy; 4484 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 && 4485 LC (F,1).inCoeffDomain() && 4486 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1))) 4487 { 4488 Variable x= Variable (1); 4489 CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2; 4490 int m= degree (F)/4+1; 4491 g= factors.getFirst(); 4492 h= factors.getLast(); 4493 g= mod (g, power (y,m)); 4494 h= mod (h, power (y,m)); 4495 g= g (yevaluation, y); 4496 h= h (yevaluation, y); 4497 gg= mod (swapvar (g,x,y),power (x,m)); 4498 gg= gg (y + evaluation, y); 4499 multiplier1= factors.getLast()[m1][0]/gg[m1][0]; 4500 gg= div (gg, power (y,m)); 4501 gg= gg*power (y,m); 4502 hh= mod (swapvar (h,x,y),power (x,m)); 4503 hh= hh (y + evaluation, y); 4504 multiplier2= factors.getFirst()[m1][0]/hh[m1][0]; 4505 hh= div (hh, power (y,m)); 4506 hh= hh*power (y,m); 4507 gg= multiplier1*gg+mod (factors.getLast(), power (y,m)); 4508 hh= multiplier2*hh+mod (factors.getFirst(), power (y,m)); 4509 check1= gg (yevaluation,y); 4510 check2= hh (yevaluation,y); 4511 check1= swapvar (check1, x, y); 4512 if (check1/Lc (check1) == check2/Lc (check2)) 4513 { 4514 result.append (gg); 4515 result.append (hh); 4516 delete [] liftPre; 4517 delete [] factorsFoundIndex; 4518 return result; 4519 } 4520 } 4365 4521 } 4366 4522 else 4367 4523 { 4368 4524 i++; 4369 if (i < 4)4525 if (i < 5) 4370 4526 continue; 4371 4527 } … … 4466 4622 while ((degree (F,y)/4)*i + 4 <= smallFactorDeg) 4467 4623 i++; 4468 while (i < 4)4469 { 4470 dummy= tmin (degree (F,y)+1, (degree (F,y)/4)* (i+1)+4);4624 while (i < 5) 4625 { 4626 dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4); 4471 4627 if (l < dummy) 4472 4628 { … … 4478 4634 { 4479 4635 i++; 4480 if (i < 4)4636 if (i < 5) 4481 4637 continue; 4482 4638 } … … 4579 4735 } 4580 4736 Variable y= F.mvar(); 4581 CanonicalForm shiftedF= G (y  evaluation, y); 4582 int sizeOldF= size (shiftedF); 4737 int sizeOldF= size (G); 4583 4738 if (size (F) < sizeOldF) 4584 4739 { 4585 H= F (y + evaluation, y); //shift back to zero4740 H= F; 4586 4741 success= true; 4587 4742 return earlyFactors; … … 4596 4751 CFList 4597 4752 henselLiftAndLatticeRecombi (const CanonicalForm& G, const CFList& uniFactors, 4598 const Variable& alpha, const DegreePattern& degPat 4753 const Variable& alpha, const DegreePattern& degPat, 4754 bool symmetric, const CanonicalForm& evaluation 4599 4755 ) 4600 4756 { … … 4627 4783 CFList smallFactors; 4628 4784 CanonicalForm H; 4629 bool success ;4785 bool success= false; 4630 4786 smallFactors= sieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi, M, 4631 4787 success, minBound + 1 … … 4926 5082 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l, 4927 5083 factorsFound, beenInThres, M, Pi, 4928 diophant 5084 diophant, symmetric, evaluation 4929 5085 ); 4930 5086 … … 4939 5095 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l, 4940 5096 factorsFound, beenInThres, M, Pi, 4941 diophant 5097 diophant, symmetric, evaluation 4942 5098 ); 4943 5099 … … 5064 5220 } 5065 5221 return Union (result, henselLiftAndLatticeRecombi (bufF, bufUniFactors, 5066 alpha, degs 5222 alpha, degs, symmetric, 5223 evaluation 5067 5224 ) 5068 5225 ); … … 5194 5351 delete [] bounds; 5195 5352 return Union (result, henselLiftAndLatticeRecombi (F, bufUniFactors, alpha, 5196 degs 5353 degs,symmetric, evaluation 5197 5354 ) 5198 5355 ); … … 5281 5438 { 5282 5439 delete [] bounds; 5283 return CFList (F); 5440 CFList source, dest; 5441 CanonicalForm tmp= G (y  evaluation, y); 5442 tmp= mapDown (tmp, info, source, dest); 5443 return CFList (tmp); 5284 5444 } 5285 5445 int minBound= bounds[0]; … … 5299 5459 CFList smallFactors; 5300 5460 CanonicalForm H; 5301 bool success ;5461 bool success= false; 5302 5462 smallFactors= extSieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi, 5303 5463 M, success, minBound + 1, evaluation, info … … 5851 6011 5852 6012 bool fail= false; 5853 CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf ;6013 CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp; 5854 6014 CFList uniFactors, list, bufUniFactors; 5855 6015 DegreePattern degs; … … 5869 6029 int subCheck1= substituteCheck (A, x); 5870 6030 int subCheck2= substituteCheck (A, y); 6031 bool symmetric= false; 5871 6032 for (int i= 0; i < factorNums; i++) 5872 6033 { 5873 6034 bufAeval= A; 5874 6035 bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail); 5875 if (!derivXZero && !fail2) 5876 { 5877 buf= swapvar (A, x, y); 6036 if (!derivXZero && !fail2 && !symmetric) 6037 { 6038 if (i == 0) 6039 { 6040 buf= swapvar (A, x, y); 6041 symmetric= (A/Lc (A) == buf/Lc (buf)); 6042 } 5878 6043 bufAeval2= buf; 5879 6044 bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2); … … 5882 6047 if (fail && (i == 0)) 5883 6048 { 5884 if (!derivXZero && !fail2 )6049 if (!derivXZero && !fail2 && !symmetric) 5885 6050 { 5886 6051 bufEvaluation= bufEvaluation2; … … 5888 6053 subCheck2= subCheck1; 5889 6054 subCheck1= dummy; 6055 tmp= A; 5890 6056 A= buf; 6057 buf= tmp; 5891 6058 bufAeval= bufAeval2; 5892 6059 swap2= true; … … 5920 6087 (prod (bufUniFactors)*Lc (bufAeval) == bufAeval)); 5921 6088 5922 if (!derivXZero && !fail2 )6089 if (!derivXZero && !fail2 && !symmetric) 5923 6090 { 5924 6091 TIMING_START (fac_fq_uni_factorizer); … … 5931 6098 5932 6099 if (bufUniFactors.length() == 1  5933 (!fail2 && !derivXZero && (bufUniFactors2.length() == 1)))6100 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1))) 5934 6101 { 5935 6102 if (extension) … … 5969 6136 } 5970 6137 5971 if (!derivXZero && !fail2 && subCheck2 > 0)6138 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0) 5972 6139 { 5973 6140 int subCheck= substituteCheck (bufUniFactors2); … … 5989 6156 // degree analysis 5990 6157 bufDegs = DegreePattern (bufUniFactors); 5991 if (!derivXZero && !fail2 )6158 if (!derivXZero && !fail2 && !symmetric) 5992 6159 bufDegs2= DegreePattern (bufUniFactors2); 5993 6160 … … 5998 6165 uniFactors= bufUniFactors; 5999 6166 degs= bufDegs; 6000 if (!derivXZero && !fail2 )6167 if (!derivXZero && !fail2 && !symmetric) 6001 6168 { 6002 6169 Aeval2= bufAeval2; … … 6009 6176 { 6010 6177 degs.intersect (bufDegs); 6011 if (!derivXZero && !fail2 )6178 if (!derivXZero && !fail2 && !symmetric) 6012 6179 { 6013 6180 degs2.intersect (bufDegs2); … … 6027 6194 } 6028 6195 list.append (bufEvaluation); 6029 if (!derivXZero && !fail2 )6196 if (!derivXZero && !fail2 && !symmetric) 6030 6197 list2.append (bufEvaluation2); 6031 6198 } 6032 6199 6033 if (!derivXZero && !fail2 )6200 if (!derivXZero && !fail2 && !symmetric) 6034 6201 { 6035 6202 if (uniFactors.length() > uniFactors2.length()  … … 6118 6285 else if (alpha.level() == 1 && !GF) 6119 6286 { 6120 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs); 6287 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs, 6288 symmetric, evaluation); 6121 6289 factors= Union (lll, factors); 6122 6290 } 6123 6291 else if (!extension && (alpha != x  GF)) 6124 6292 { 6125 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs); 6293 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs, 6294 symmetric, evaluation); 6126 6295 factors= Union (lll, factors); 6127 6296 }
Note: See TracChangeset
for help on using the changeset viewer.