69 return swapvar (
gcd (L.getFirst(), L.getLast()), F.mvar(),
x);
98 return gcd (resultHi, resultLo);
139 int *
degsf=
new int [n + 1];
140 int **
swap=
new int* [n + 1];
141 for (
int i= 0;
i <=
n;
i++)
144 swap [
i]=
new int [3];
154 while ( i <= F.
level() )
156 while( degsf[i] == 0 ) i++;
159 swap[
n][2]= degsf [
i];
168 for (i= 1; i <
n; i++)
170 for (
int j= 1;
j < n - i + 1;
j++)
172 if (swap[
j][1] > swap[
j + 1][1])
174 buf1= swap [
j + 1] [0];
175 buf2= swap [
j + 1] [1];
176 buf3= swap [
j + 1] [2];
177 swap[
j + 1] [0]= swap[
j] [0];
178 swap[
j + 1] [1]= swap[
j] [1];
179 swap[
j + 1] [2]= swap[
j] [2];
185 else if (swap[
j][1] == swap[
j + 1][1] && swap[
j][2] < swap[
j + 1][2])
187 buf1= swap [
j + 1] [0];
188 buf2= swap [
j + 1] [1];
189 buf3= swap [
j + 1] [2];
190 swap[
j + 1] [0]= swap[
j] [0];
191 swap[
j + 1] [1]= swap[
j] [1];
192 swap[
j + 1] [2]= swap[
j] [2];
201 for (i= n; i > 0; i--)
203 if (i != swap[i] [0])
207 for (i= 0; i <= F.
level(); i++)
227 if (factors.
length() == 1)
236 if (!k && beta.
level() != 1)
254 bool noSubset=
false;
258 bool trueFactor=
false;
261 while (noSubset ==
false)
284 S=
subset (v, s, TT, noSubset);
297 if (
degree (buf2, alpha) < degMipoBeta)
363 if (factors.
length() == 1)
379 bool noSubset=
false;
387 while (noSubset ==
false)
402 S=
subset (v, s, TT, noSubset);
446 success,
const int deg,
const CFList& MOD,
const int bound)
448 int adaptedLiftBound= 0;
474 if (adaptedLiftBound < deg)
476 if (adaptedLiftBound <
degree (F) + 1)
482 adaptedLiftBound= deg;
488 if (e + 1 <
degree (F) + 1)
489 adaptedLiftBound= deg;
491 adaptedLiftBound= e + 1;
497 adaptedLiftBound= deg;
505 return adaptedLiftBound;
518 int adaptedLiftBound= 0;
531 if (!k && beta.
level() != 1)
545 if (
degree (gg, alpha) < degMipoBeta)
569 if (adaptedLiftBound < deg)
571 if (adaptedLiftBound <
degree (F) + 1)
577 adaptedLiftBound= deg;
583 if (e + 1 <
degree (F) + 1)
584 adaptedLiftBound= deg;
586 adaptedLiftBound= e + 1;
592 adaptedLiftBound= deg;
601 return adaptedLiftBound;
606 bool& success,
const int deg,
const CFList& MOD,
639 if (adaptedLiftBound < deg)
641 if (adaptedLiftBound <
degree (F) + 1)
644 adaptedLiftBound=
tmin (e + 1, deg);
646 adaptedLiftBound= deg;
681 if (!k && beta.
level() != 1)
694 if (
degree (gg, alpha) < degMipoBeta)
722 if (adaptedLiftBound < deg)
724 if (adaptedLiftBound <
degree (F) + 1)
727 adaptedLiftBound=
tmin (e + 1, deg);
729 adaptedLiftBound= deg;
738 #define CHAR_THRESHOLD 8
741 CFList& list,
const bool& GF,
bool& fail)
754 if (!GF && alpha.
level() == 1)
759 else if (!GF && alpha.
level() != 1)
782 bound=
pow ((
double) p, (
double) k);
795 for (
int i= 0;
i <
k;
i++)
804 else if (alpha.
level() != 1)
816 if (
find (list, random))
831 if (!
find (list, random))
841 if (!
find (list, random))
856 if (!
find (list, random))
866 if (
degree (gcd_deriv) > 0)
868 if (!
find (list, random))
878 if (
degree (contentx) > 0)
880 if (!
find (list, random))
889 if (
degree (contentx) > 0)
891 if (!
find (list, random))
904 }
while (
find (list, random));
927 for (
int i= lev;
i <= A.
level();
i++)
932 g=
gcd (buf, derivI);
940 evaluation=
evalPoints (buf, Aeval, alpha, list, GF, fail);
962 for (i= i - 2; i > 0; i--)
978 CFList bufFactors= biFactors;
985 int smallFactorDeg= 11;
987 int adaptedLiftBound= 0;
988 int liftBound= liftBounds[1];
991 CFList earlyReconstFactors;
997 if (smallFactorDeg >= liftBound)
999 result=
henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1001 else if (smallFactorDeg >=
degree (buf) + 1)
1003 liftBounds[1]=
degree (buf) + 1;
1004 result=
henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1009 (buf, result, adaptedLiftBound, earlySuccess,
1010 degree (buf) + 1, MOD, liftBound);
1013 (buf, result, adaptedLiftBound, earlySuccess,
1015 (buf) + 1, MOD, liftBound);
1021 degree (buf) + 1, MOD, liftBound);
1024 evaluation,
degree (buf) + 1,
1030 liftBounds[1]= adaptedLiftBound;
1031 liftBound= adaptedLiftBound;
1033 Pi, diophant, Mat, MOD);
1036 liftBounds[1]= adaptedLiftBound;
1038 else if (smallFactorDeg <
degree (buf) + 1)
1040 liftBounds[1]= smallFactorDeg;
1041 result=
henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1046 earlySuccess, smallFactorDeg, MOD,
1050 earlySuccess, info, evaluation,
1051 smallFactorDeg, MOD, liftBound);
1057 smallFactorDeg, MOD, liftBound);
1060 evaluation, smallFactorDeg, MOD,
1068 Pi, diophant, Mat, MOD);
1073 earlySuccess,
degree (buf) + 1,
1077 earlySuccess, info, evaluation,
1085 degree (buf) + 1, MOD,liftBound);
1095 liftBounds[1]= adaptedLiftBound;
1096 liftBound= adaptedLiftBound;
1098 Pi, diophant, Mat, MOD);
1101 liftBounds[1]= adaptedLiftBound;
1104 liftBounds[1]= adaptedLiftBound;
1117 for (
int i= 2;
i <= liftBoundsLength && j.
hasItem();
i++, j++)
1119 earlySuccess=
false;
1122 liftBound= liftBounds[
i];
1126 if (smallFactorDeg >= liftBound)
1127 result=
henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1128 liftBounds[i - 1], liftBounds[i]);
1129 else if (smallFactorDeg >=
degree (buf) + 1)
1131 result=
henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1132 liftBounds[i - 1],
degree (buf) + 1);
1134 if (Aeval.
length() == i + 1)
1138 (buf, result, adaptedLiftBound, earlySuccess,
1139 degree (buf) + 1, MOD, liftBound);
1142 (buf, result, adaptedLiftBound, earlySuccess,
1143 info, evaluation,
degree (buf) + 1, MOD, liftBound);
1149 (buf, result, earlySuccess,
degree (buf)
1150 + 1, MOD, liftBound);
1153 (buf, result, earlySuccess, info, evaluation,
1154 degree (buf) + 1, MOD, liftBound);
1160 liftBounds[
i]= adaptedLiftBound;
1161 liftBound= adaptedLiftBound;
1163 Pi, diophant, Mat, MOD);
1167 liftBounds[
i]= adaptedLiftBound;
1170 else if (smallFactorDeg <
degree (buf) + 1)
1172 result=
henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1173 liftBounds[i - 1], smallFactorDeg);
1175 if (Aeval.
length() == i + 1)
1179 (buf, result, adaptedLiftBound, earlySuccess,
1180 smallFactorDeg, MOD, liftBound);
1183 (buf, result, adaptedLiftBound, earlySuccess,
1184 info, evaluation, smallFactorDeg, MOD, liftBound);
1190 (buf, result, earlySuccess,
1191 smallFactorDeg, MOD, liftBound);
1194 (buf, result, earlySuccess, info, evaluation,
1195 smallFactorDeg, MOD, liftBound);
1202 degree (buf) + 1, Pi, diophant, Mat, MOD);
1203 if (Aeval.
length() == i + 1)
1207 (buf, result, adaptedLiftBound, earlySuccess,
1208 degree (buf) + 1, MOD, liftBound);
1211 (buf, result, adaptedLiftBound, earlySuccess,
1212 info, evaluation,
degree (buf) + 1, MOD,
1219 (buf, result, earlySuccess,
degree
1220 (buf) + 1, MOD, liftBound);
1223 (buf, result, earlySuccess, info, evaluation,
1224 degree (buf) + 1, MOD, liftBound);
1230 liftBounds[
i]= adaptedLiftBound;
1231 liftBound= adaptedLiftBound;
1233 Pi, diophant, Mat, MOD);
1236 liftBounds[
i]= adaptedLiftBound;
1239 liftBounds[
i]= adaptedLiftBound;
1266 for (j= factors2; (m < l && j.
hasItem()); j++, m++)
1268 g=
gcd (
i.getItem().factor(), j.
getItem().factor());
1272 i.getItem()=
CFFactor (
i.getItem().factor()/
g,
i.getItem().exp());
1294 for (
int i= 0;
i < length;
i++)
1296 if (differentSecondVarFactors[
i].isEmpty())
1300 result= differentSecondVarFactors[
i];
1307 for (
CFListIterator iter2= differentSecondVarFactors[
i];iter2.hasItem();
1310 iter1.
getItem() *= iter2.getItem();
1311 content /= iter2.getItem();
1323 for (
int i= 0;
i < length;
i++)
1325 if (differentSecondVarFactors[
i].isEmpty())
1331 for (iter2= differentSecondVarFactors[
i]; iter2.
hasItem();
1334 if (iter2.
getItem().inCoeffDomain())
1359 for (iter2= multiplier; iter2.
hasItem(); iter1++, iter2++)
1381 sqrfFactorization=
sqrFree (F);
1385 sqrfPartF *=
i.getItem().factor();
1398 factors= uniFactors;
1406 sqrfFactors=
sqrFree (
i.getItem());
1408 for (iter= sqrfFactors; iter.
hasItem(); iter++)
1411 tmp *= iter.
getItem().factor();
1413 i.getItem()= tmp/
Lc(tmp);
1414 bufSqrfFactors [
k]= sqrfFactors;
1417 for (
int i= 0;
i < factors.
length() - 1;
i++)
1419 for (k=
i + 1; k < factors.
length(); k++)
1426 for (
int i= 0;
i < uniFactors.
length();
i++)
1430 for (iter= bufSqrfFactors [
i]; iter.
hasItem(); iter++)
1432 if (iter.
getItem().factor().inCoeffDomain())
1442 for (iter= bufSqrfFactors [
i]; iter.
hasItem(); iter++)
1444 if (iter.
getItem().factor().inCoeffDomain())
1455 test=
prod (factors);
1456 tmp= evalSqrfPartF.
getFirst() (evalPoint[0],2);
1457 if (test/
Lc (test) != tmp/
Lc (tmp))
1466 CFList* & differentSecondVarLCs,
int lSecondVarLCs,
1474 for (
int i= 1;
i <= LCFFactors.
length() + 1;
i++)
1488 int LCFLevel= LCF.
level();
1499 for (
int i= 0;
i < lSecondVarLCs;
i++)
1501 for (j= differentSecondVarLCs[
i]; j.
hasItem(); j++)
1503 if (j.
getItem().level() == LCFLevel)
1511 result= differentSecondVarLCs [
i];
1526 CFList factors= LCFFactors;
1529 i.getItem()=
M (
i.getItem());
1533 CFList evalSqrfPartF, bufFactors;
1539 for (
int i= evaluation.
length() +1;
i > 1;
i--, iter++)
1541 buf[
i-2]=iter.getItem();
1546 for (
int i= 0;
i < evaluation.
length() - 1;
i++)
1547 evalPoint[
i]= buf[
i+1];
1549 int pass=
testFactors (F, factors, alpha, sqrfPartF,
1550 bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1552 bool foundDifferent=
false;
1561 for (
int i= 0;
i < lSecondVarLCs;
i++)
1563 if (!differentSecondVarLCs [
i].isEmpty())
1565 bool allConstant=
true;
1566 for (iter= differentSecondVarLCs[
i]; iter.hasItem(); iter++)
1568 if (!iter.getItem().inCoeffDomain())
1571 y=
Variable (iter.getItem().level());
1578 bufFactors= differentSecondVarLCs [
i];
1579 for (iter= bufFactors; iter.hasItem(); iter++)
1580 iter.getItem()=
swapvar (iter.getItem(),
x,
y);
1584 bufBufFactors= bufFactors;
1586 for (
int k= 1;
k < evaluation.
length();
k++)
1589 evalPoint[
k-1]= buf[
k];
1591 evalPoint[
k-1]= buf[0];
1593 pass=
testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1594 bufSqrfFactors, evalSqrfPartF, evalPoint);
1597 foundDifferent=
true;
1600 for (iter= l; iter.hasItem(); iter++)
1601 iter.getItem()=
swapvar (iter.getItem(),
x,
y);
1602 differentSecondVarLCs [
i]=
l;
1606 if (!pass &&
i == lSecondVarLCs - 1)
1610 for (
int j= 1; j <= factors.
length(); j++)
1614 delete [] bufSqrfFactors;
1624 for (
int j= 1; j <= factors.
length(); j++)
1628 delete [] bufSqrfFactors;
1632 factors= bufFactors;
1634 bufFactors= factors;
1637 dummy [0]= sqrfPartF;
1640 sqrfPartF= MM (sqrfPartF);
1643 iter.getItem()= MM (iter.getItem());
1646 for (
int i= 2;
i <= varsSqrfPartF.
level();
i++)
1651 sqrfPartF=
shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1652 if (factors.
length() > 1)
1656 for (
int i= 0;
i < factors.
length();
i++)
1657 leadingCoeffs.
append (LC1);
1660 CFList oldFactors= factors;
1664 bool success=
false;
1667 if (
size (oldSqrfPartFPowLC)/
getNumVars (oldSqrfPartFPowLC) < 500 &&
1669 oldFactors, 2, leadingCoeffs, heuResult))
1680 for (
int i= 0;
i < factors.
length();
i++)
1681 leadingCoeffs[
i]= LC1;
1684 i.getItem() *= LC1 (0,2)/
Lc (
i.getItem());
1690 int liftBound=
degree (newSqrfPartF,2) + 1;
1696 leadingCoeffs,
false);
1698 if (sqrfPartF.level() > 2)
1700 int* liftBounds=
new int [sqrfPartF.level() - 1];
1701 bool noOneToOne=
false;
1702 CFList *leadingCoeffs2=
new CFList [sqrfPartF.level()-2];
1705 for (
int i= 0;
i < factors.
length();
i++)
1707 leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1708 for (
int i= sqrfPartF.level() - 1;
i > 2;
i--)
1711 j.getItem()= j.getItem() (0,
i + 1);
1712 leadingCoeffs2 [
i - 3]= LCs;
1716 int liftBoundsLength= sqrfPartF.
level() - 1;
1717 for (
int i= 0;
i < liftBoundsLength;
i++)
1718 liftBounds [
i]=
degree (sqrfPartF,
i + 2) + 1;
1722 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1723 delete [] leadingCoeffs2;
1724 delete [] liftBounds;
1727 iter.getItem()=
reverseShift (iter.getItem(), evaluation2);
1737 factors=
CFList (oldSqrfPartF/contF);
1741 for (
CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1742 iter.getItem()= NN (iter.getItem());
1746 for (
int i= 0;
i < LCFFactors.
length();
i++)
1749 for (k= bufSqrfFactors[
i]; k.
hasItem(); k++)
1755 result.append (tmp);
1763 i.getItem()=
N (
i.getItem());
1768 CFList l= differentSecondVarLCs [
j];
1771 differentSecondVarLCs [
j]=
l;
1775 result.insert (N (F));
1779 if (!result.getFirst().inCoeffDomain())
1786 CFList l= differentSecondVarLCs [
j];
1789 differentSecondVarLCs [
j]=
l;
1792 F= result.getFirst();
1796 level= y.
level() - 2;
1809 if (lSecondVarLCs - level > 0)
1812 int j= lSecondVarLCs+2;
1815 for (i= evaluation2; i.
hasItem(); i++, j--)
1822 evaluation2.
append (swap);
1829 if (
degree (F, level+3) > 0)
1831 delete [] bufSqrfFactors;
1841 for (;iter.
hasItem(); iter++, i++)
1844 if (
degree (swap, level+3) > 0)
1847 for (
CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
1850 if (count != level+3)
1857 CFList * differentSecondVarLCs2=
new CFList [lSecondVarLCs - level - 1];
1858 for (
int j= level+1; j < lSecondVarLCs; j++)
1862 if (!differentSecondVarLCs[j].isEmpty())
1864 differentSecondVarLCs2[j - level - 1]= differentSecondVarLCs[
j];
1865 i= differentSecondVarLCs2[j-level - 1];
1868 for (;iter.
hasItem(); iter++, i++)
1871 if (
degree (swap, j+3) > 0)
1888 for (
int j= 0; j < level+1; j++)
1894 for (i=newLCs; i.
hasItem(); i++)
1896 for (
int j= 1; j < lSecondVarLCs-
level;j++)
1898 for (i= differentSecondVarLCs2[j-1]; i.
hasItem(); i++)
1906 differentSecondVarLCs2, lSecondVarLCs - level - 1,
1909 if (dummyvar.
level() != 1)
1911 for (i= recursiveResult; i.
hasItem(); i++)
1914 for (i= recursiveResult; i.
hasItem(); i++)
1916 for (
int j= lSecondVarLCs-level-1; j > 0; j--)
1922 if (recursiveResult.
getFirst() == result.getFirst())
1924 delete [] bufSqrfFactors;
1925 delete [] differentSecondVarLCs2;
1930 iter=recursiveResult;
1935 for (; i.
hasItem(); i++, iter++)
1937 delete [] differentSecondVarLCs2;
1944 delete [] bufSqrfFactors;
1956 bool preserveDegree=
true;
1958 int j, degAi, degA1=
degree (A,1);
1964 preserveDegree=
true;
1966 for (j= A.
level(); j > 1; j--, iter++)
1974 if ((
degree (tmp,
i) != degAi) ||
1975 (
degree (tmp, 1) != degA1))
1977 preserveDegree=
false;
1982 if (!
content(tmp,1).inCoeffDomain())
1983 preserveDegree=
false;
1984 if (!
content(tmp).inCoeffDomain())
1985 preserveDegree=
false;
1986 if (!(
gcd (
deriv (tmp,x), tmp)).inCoeffDomain())
1987 preserveDegree=
false;
1989 Aeval [
i - 3]=
tmp2;
2013 for (; iter1.
hasItem(); iter1++, iter2++)
2016 if (!g2.inCoeffDomain())
2019 l2.
append (iter2.getItem());
2035 CFList uniFactorsOfFactors1;
2042 for (iter= factors1; iter.
hasItem(); iter++)
2046 if ((pos=
findItem (factors2, tmp)))
2053 uniFactorsOfFactors1.
append (tmp);
2062 while (!uniFactorsOfFactors1.
isEmpty())
2064 tmp= uniFactorsOfFactors1.
getFirst();
2070 checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2082 checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2108 int *
v=
new int [T.
length()];
2111 bool nosubset=
false;
2113 TT=
copy (factors1);
2114 int recombinations= 0;
2115 while (T.
length() >= 2*s && s <= thres)
2117 while (nosubset ==
false)
2122 if (recombinations == factors2.
length() - 1)
2125 result=
Union (result, T);
2128 S=
subset (v, s, TT, nosubset);
2129 if (nosubset)
break;
2132 if (
find (factors2, buf))
2139 if (nosubset)
break;
2145 if (recombinations == factors2.
length() - 1)
2148 result=
Union (result, T);
2160 result=
Union (result, T);
2174 minFactorsLength= 0;
2178 for (
int j= 0;
j < A.
level() - 2;
j++)
2180 if (!Aeval[
j].isEmpty())
2191 if (minFactorsLength == 0)
2192 minFactorsLength= factors.
length();
2194 minFactorsLength=
tmin (minFactorsLength, factors.
length());
2196 if (factors.
length() == 1)
2221 for (
int j= 0;
j < A.
level() - 2;
j++)
2223 if (!Aeval[
j].isEmpty())
2226 for (iter= Aeval[
j]; iter.
hasItem(); iter++)
2245 int pos,
index, checklength;
2246 bool leaveLoop=
false;
2248 for (
int j= 0;
j < AevalLength;
j++)
2250 if (!Aeval[
j].isEmpty())
2252 i= evaluation.
length() + 1;
2253 for (iter= evaluation; iter.
hasItem(); iter++, i--)
2255 for (iter2= Aeval[
j]; iter2.
hasItem(); iter2++)
2257 if (i == iter2.
getItem().level())
2272 if (Aeval[
j].length() > uniFactors.
length())
2274 Aeval[j].length() - uniFactors.
length() + 1,
2277 checklength= biFactors.
length();
2278 Aeval[
j]=
checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2279 if (checklength > biFactors.
length())
2289 for (iter= buf; iter.
hasItem(); iter++, index++)
2293 l[pos-1]=
getItem (Aeval[j], index);
2328 bool leaveLoop=
false;
2329 for (
int j= 0;
j < A.
level() - 2;
j++)
2335 for (iter= evaluation; iter.
hasItem(); iter++, i--)
2337 for (iter2= Aeval[
j]; iter2.
hasItem(); iter2++)
2339 if (i == iter2.
getItem().level())
2373 for (
int i= n - 1;
i > 2;
i--, iter++)
2381 i.getItem()=
i.getItem() (iter.
getItem(), 3);
2386 for (
int i= 0;
i < n-2;
i++)
2388 ii= normalizeFactor;
2389 for (j= LCs [
i]; j.
hasItem(); j++, ii++)
2397 for (iter= Aeval; iter.
hasItem(); iter++)
2426 int *
v=
new int [T.
length()];
2429 bool noSubset=
false;
2433 bool trueFactor=
false;
2436 while (noSubset ==
false)
2454 S=
subset (v, s, TT, noSubset);
2455 if (noSubset)
break;
2463 if (!k && beta.
level() == 1)
2465 if (
degree (buf2, alpha) < degMipoBeta)
2469 recombination=
true;
2479 recombination=
true;
2498 if (noSubset)
break;
2528 CFList*& oldAeval,
int lengthAeval2,
2542 evaluation.
append (evalPoint);
2546 for (i= 0; i < lengthAeval2; i++)
2548 if (oldAeval[i].isEmpty())
2550 if (oldAeval[i].getFirst().
level() == w.
level())
2553 oldAeval[
i]= biFactors;
2556 for (
int ii= 0; ii < tmp.
size(); ii++)
2557 tmp[ii]=
swapvar (tmp[ii], w, y);
2560 for (
int ii= 0; ii < tmp.
size(); ii++)
2562 buf= tmp[ii] (evaluation.
getLast(),
y);
2564 tmp2[
findItem (uniFactors, buf)-1]=tmp[ii];
2567 for (
int j= 0;
j < tmp2.
size();
j++)
2583 iter.
getItem() *= LCmultipler;
2585 for (
int i= A.level();
i > 2;
i--, iter++)
2591 i.getItem() *= tmp/
LC (
i.getItem(), 1);
2592 i.getItem() /=
Lc (
i.getItem());
2601 const CFList& oldBiFactors)
2608 if (sqrfMultiplier.
getFirst().factor().inCoeffDomain())
2612 for (iter= oldBiFactors; iter.
hasItem(); iter++)
2614 for (
int i= 0;
i < lengthAeval;
i++)
2616 if (oldAeval[
i].isEmpty())
2620 for (iter= oldAeval[
i]; iter.
hasItem(); iter++, iter2++)
2625 for (iter= leadingCoeffs[lengthAeval-1]; iter.
hasItem(); iter++, iter2++)
2627 tmp= iter.
getItem()/LCmultiplier;
2628 for (
int i=1;
i <= tmp.
level();
i++)
2638 for (iter= vars1; iter.
hasItem(); iter++)
2644 tmp /=
myGetVars (ii.getItem().factor());
2647 if (multi == ii.getItem().exp())
2650 for (iter= vars1; iter.
hasItem(); iter++, index++)
2655 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.
hasItem();iter2++,
2658 if (index2 == index)
2662 tmp= ii.getItem().factor();
2666 for (
int jj= A.
level(); jj > 2; jj--, iter3++)
2667 tmp= tmp (iter3.
getItem(), jj);
2671 for (iter3= biFactors; iter3.
hasItem(); iter3++, index3++)
2673 if (index3 == index2)
2677 if (
fdivides (ii.getItem().factor(),
A, quot3))
2699 for (iter= vars1; iter.
hasItem(); iter++, index++)
2704 for (iter2= leadingCoeffs[lengthAeval-1];iter2.
hasItem();iter2++,
2707 if (index2 == index)
2709 tmp=
power (ii.getItem().factor(), ii.getItem().exp());
2715 for (
int jj= A.
level(); jj > 2; jj--, iter3++)
2716 tmp= tmp (iter3.
getItem(), jj);
2720 for (iter3= biFactors; iter3.
hasItem(); iter3++, index3++)
2722 if (index3 == index2)
2748 bool& foundTrueMultiplier)
2751 if (
fdivides (pLCs,
LC (oldA,1)) && (
LC(oldA,1)/pLCs).inCoeffDomain())
2757 foundTrueMultiplier=
true;
2764 bool& foundTrueMultiplier)
2772 cont=
gcd (cont, LCmultiplier);
2774 if (cont.inCoeffDomain())
2776 foundTrueMultiplier=
true;
2778 for (iter2= leadingCoeffs; iter2.
hasItem(); iter2++, index2++)
2780 if (index2 == index)
2782 iter2.
getItem() /= LCmultiplier;
2795 int lengthAeval,
bool& foundMultiplier)
2799 for (iter= contents; iter.
hasItem(); iter++, iter2++, index++)
2803 if ((LCmultiplier/iter.
getItem()).inCoeffDomain() &&
2810 for (
int i= 0;
i < lengthAeval;
i++)
2812 if (oldAeval[
i].isEmpty())
2818 if (vars.
level() <= 2)
2822 iter3.hasItem(); iter3++, index2++)
2824 if (index2 == index)
2826 iter3.getItem() /= LCmultiplier;
2831 foundMultiplier=
true;
2848 for (iter= contents; iter.
hasItem(); iter++, iter2++, index++)
2850 if (!iter.
getItem().isOne() &&
2856 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2859 if (index2 == index)
2861 iter2.getItem() /= iter.
getItem();
2862 foundMultiplier=
true;
2867 LCmultiplier /= iter.
getItem();
2876 for (
int i= 0;
i < lengthAeval;
i++)
2878 if (oldAeval[
i].isEmpty())
2888 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2891 if (index2 == index)
2893 iter2.getItem() /= LCmultiplier;
2894 foundMultiplier=
true;
2933 if (extension ==
false)
2938 A=
mapDown (F, info, source, dest);
2968 if (
i.getItem().inCoeffDomain())
2972 lcmCont /=
i.getItem();
2982 return contentAFactors;
2995 append (factors, contentAFactors);
3007 for (
int i= 1;
i <= A.
level();
i++)
3010 derivZ=
deriv (bufA, z);
3020 gcdDerivZ=
gcd (bufA, derivZ);
3045 "time to check main var over Fq: ");
3047 "time to preprocess poly and extract content over Fq: ");
3054 CFList biFactors, bufBiFactors;
3056 int lift, bufLift, lengthAeval2= A.
level()-2;
3059 logarithm= ceil (logarithm);
3060 if (factorNums < (
int) logarithm)
3061 factorNums= (int) logarithm;
3065 int differentSecondVar= 0;
3068 for (
int i= 0;
i < factorNums;
i++)
3074 bufEvaluation=
evalPoints (bufA, bufAeval, alpha, list, GF, fail);
3076 "time to find evaluation point over Fq: ");
3079 if (fail && (
i == 0))
3094 delete [] bufAeval2;
3118 else if (fail && (
i > 0))
3124 "time for evaluation wrt diff second vars over Fq: ");
3126 for (
int j= 0;
j < lengthAeval2;
j++)
3128 if (!bufAeval2[
j].isEmpty())
3135 if (!GF && alpha.
level() == 1)
3142 "time for bivariate factorization: ");
3143 bufBiFactors.removeFirst();
3145 if (bufBiFactors.length() == 1)
3150 A=
mapDown (A, info, source, dest);
3157 delete [] bufAeval2;
3165 evaluation= bufEvaluation;
3166 biFactors= bufBiFactors;
3168 for (
int j= 0;
j < lengthAeval2;
j++)
3169 Aeval2 [
j]= bufAeval2 [
j];
3170 differentSecondVar= counter;
3174 if (bufBiFactors.length() < biFactors.
length() ||
3175 ((bufLift <
lift) && (bufBiFactors.length() == biFactors.
length())) ||
3176 counter > differentSecondVar)
3179 evaluation= bufEvaluation;
3180 biFactors= bufBiFactors;
3182 for (
int j= 0;
j < lengthAeval2;
j++)
3183 Aeval2 [
j]= bufAeval2 [
j];
3184 differentSecondVar= counter;
3189 evalPoly +=
j.getItem()*
power (x, k);
3193 delete [] bufAeval2;
3202 "time for bivariate factorization wrt diff second vars over Fq: ");
3205 "total time for eval and bivar factors over Fq: ");
3211 A=
mapDown (A, info, source, dest);
3222 if (minFactorsLength == 0)
3223 minFactorsLength= biFactors.
length();
3226 minFactorsLength=
tmin (minFactorsLength, biFactors.
length());
3230 sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
3232 minFactorsLength=
tmin (minFactorsLength, biFactors.
length());
3234 if (minFactorsLength == 1)
3239 A=
mapDown (A, info, source, dest);
3250 if (differentSecondVar == lengthAeval2)
3252 bool zeroOccured=
false;
3284 for (
int i= 0;
i < lengthAeval2;
i++)
3285 oldAeval[
i]= Aeval2[
i];
3291 biFactorsLCs.
append (
LC (
i.getItem(), 1));
3296 evaluation, Aeval2, lengthAeval2, v);
3303 CFList oldBiFactors= biFactors;
3309 if (!LCmultiplierIsConst)
3318 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
3319 bufBiFactors= biFactors;
3322 if (!LCmultiplierIsConst)
3325 for (
int i= 0;
i < lengthAeval2;
i++)
3327 if (!oldAeval[
i].isEmpty())
3332 "time to precompute LC over Fq: ");
3336 bool LCheuristic=
false;
3340 int check= biFactors.length();
3342 CFList oldFactors= factors;
3345 if (check == factors.
length())
3352 for (iter= factors; iter.hasItem(); iter++)
3353 iter.getItem()=
swapvar (iter.getItem(),
v,
y);
3363 "time for successful LucksWang over Fq: ");
3366 else if (factors.
length() > 0)
3375 for (
int j=1;
j <=
i-oneCount;
j++)
3378 for (
int j= 0;
j < lengthAeval2;
j++)
3380 l= leadingCoeffs2[
j];
3382 for (
int k=1;
k <=
i-oneCount;
k++)
3385 leadingCoeffs2[
j]=
l;
3390 bufFactors= factors;
3393 else if (!LCmultiplierIsConst && factors.
length() == 0)
3396 factors= oldFactors;
3398 bool foundTrueMultiplier=
false;
3399 LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
3400 contents, LCs, foundTrueMultiplier);
3401 if (foundTrueMultiplier)
3404 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3405 for (
int i= lengthAeval2-1;
i > -1;
i--)
3412 bool foundMultiplier=
false;
3413 LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
3414 A, leadingCoeffs2, lengthAeval2, foundMultiplier);
3417 if (foundMultiplier)
3419 foundMultiplier=
false;
3420 LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
3421 lengthAeval2, leadingCoeffs2, A, LCmultiplier,
3427 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
3430 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3431 lengthAeval2, evaluation, oldBiFactors);
3436 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3437 for (
int i= lengthAeval2-1;
i > -1;
i--)
3443 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
3447 biFactors= bufBiFactors;
3448 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3449 LCmultiplier= bufLCmultiplier;
3459 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.
isEmpty()
3463 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3464 lengthAeval2, evaluation, oldBiFactors);
3466 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3467 for (
int i= lengthAeval2-1;
i > -1;
i--)
3472 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
3476 biFactors= bufBiFactors;
3477 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3478 LCmultiplier= bufLCmultiplier;
3487 for (iter= biFactors; iter.hasItem(); iter++)
3488 iter.getItem()= iter.getItem () (y + evaluation.
getLast(),
y);
3490 for (
int i= 0;
i < lengthAeval2-1;
i++)
3492 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3495 for (
int i= A.
level() - 4;
i > -1;
i--)
3497 if (
i + 1 == lengthAeval2-1)
3498 leadingCoeffs2[
i].
append (iter.getItem() (0,
i + 4));
3504 "time to shift evaluation point to zero: ");
3508 int* liftBounds=
new int [A.
level() - 1];
3509 int liftBoundsLength= A.
level() - 1;
3510 for (
int i= 0;
i < liftBoundsLength;
i++)
3511 liftBounds [
i]=
degree (A,
i + 2) + 1;
3514 bool noOneToOne=
false;
3517 Pi, liftBounds, liftBoundsLength, noOneToOne);
3519 "time for non monic hensel lifting over Fq: ");
3528 "time to recover factors over Fq: ");
3529 if (check != factors.
length())
3532 factors=
Union (factors, bufFactors);
3534 if (extension && !noOneToOne)
3539 if (!LCmultiplierIsConst && LCheuristic)
3542 biFactors= bufBiFactors;
3543 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3544 delete [] liftBounds;
3546 goto tryAgainWithoutHeu;
3551 biFactors= oldBiFactors;
3552 for (iter= biFactors; iter.hasItem(); iter++)
3553 iter.getItem()= iter.getItem () (y + evaluation.
getLast(),
y);
3567 yToLift=
power (y, lift);
3572 extgcd (LCA, yToLift, LCA, dummy);
3576 liftBoundsLength= F.
level() - 1;
3581 CFList earlyFactors, liftedFactors;
3584 (A, MOD, liftBounds, earlySuccess, earlyFactors,
3585 Aeval, biFactors, evaluation, info);
3587 "time for hensel lifting over Fq: ");
3594 "time for factor recombination: ");
3601 "time for factor recombination: ");
3605 factors=
Union (factors, earlyFactors);
3624 iter.getItem()=
swapvar (iter.getItem(),
v,
y);
3627 swap (factors, swapLevel, swapLevel2, x);
3628 append (factors, contentAFactors);
3633 delete[] liftBounds;
3653 if (!GF && alpha == w)
3656 bool extension=
true;
3677 else if (p >= 7 && p*p < (1<<16))
3701 else if (!GF && (alpha != w))
3719 bool primFail=
false;
3722 ASSERT (!primFail,
"failure in integer factorizer");
3739 bool primFail=
false;
3741 ASSERT (!primFail,
"failure in integer factorizer");
3751 bufA=
mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3763 bool extension=
true;
3767 if (
pow ((
double) p, (
double) extensionDeg) < (1<<16))
3793 if (
pow ((
double) p, (
double) 2*extensionDeg) < (1<<16))
3809 bool primFail=
false;
int status int void size_t count
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
CanonicalForm generate() const
CanonicalForm generate() const
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
static int newMainVariableSearch(CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
const CanonicalForm int s
bool isInExtension() const
getter
generate random elements in GF
const CanonicalForm int const CFList const Variable & y
CFArray copy(const CFList &list)
write elements of list into an array
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
Conversion to and from NTL.
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
This file defines functions for Hensel lifting.
This file provides utility functions for multivariate factorization.
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
static CanonicalForm bound(const CFMatrix &M)
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
Variable getBeta() const
getter
functions to print debug output
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
#define TIMING_END_AND_PRINT(t, msg)
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
static Variable chooseExtension(const Variable &alpha)
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to ...
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
factory's class for variables
CFList *& Aeval
<[in] poly
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
CanonicalForm generate() const
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
const CanonicalForm CFMap CFMap int &both_non_zero int n
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field...
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
const CanonicalForm int const CFList & evaluation
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
This file provides functions for factorizing a multivariate polynomial over , or GF...
static const double log2exp
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Variable getAlpha() const
getter
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
bool delta(X x, Y y, D d)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
This file implements functions to map between extensions of finite fields.
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
This file provides functions for sparse heuristic Hensel lifting.
ExtensionInfo contains information about extension.
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible ...
int getGFDegree() const
getter
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity ...
const CanonicalForm CFMap CFMap & N
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int status int void * buf
This file defines functions for fast multiplication and division with remainder.
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
static CanonicalForm myContent(const CanonicalForm &F)
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
CanonicalForm getGamma() const
getter
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
generate random elements in F_p
void prune(Variable &alpha)
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
generate random integers, random elements of finite fields
char getGFName() const
getter
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
static int index(p_Length length, p_Ord ord)
class to iterate through CanonicalForm's
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
const Variable & v
< [in] a sqrfree bivariate poly
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
generate random irreducible univariate polynomials
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
static CanonicalForm listGCD(const CFList &L)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
generate random elements in F_p(alpha)
CanonicalForm getDelta() const
getter
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
CFList conv(const CFArray &A)
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
#define GaloisFieldDomain
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted...
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
CFList int bool & irred
[in,out] Is A irreducible?
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents...
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL ...
#define ASSERT(expression, message)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Rational pow(const Rational &a, int e)
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
int findItem(const CFList &list, const CanonicalForm &item)
helper function
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
TIMING_DEFINE_PRINT(fac_fq_bi_factorizer) TIMING_DEFINE_PRINT(fac_fq_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_fq_evaluation) TIMING_DEFINE_PRINT(fac_fq_recover_factors) TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content) TIMING_DEFINE_PRINT(fac_fq_bifactor_total) TIMING_DEFINE_PRINT(fac_fq_luckswang) TIMING_DEFINE_PRINT(fac_fq_lcheuristic) TIMING_DEFINE_PRINT(fac_fq_content) TIMING_DEFINE_PRINT(fac_fq_check_mainvar) TIMING_DEFINE_PRINT(fac_fq_compress) static inline CanonicalForm listGCD(const CFList &L)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.