96 return gcd (resultHi, resultLo);
138 int **
swap=
new int* [n + 1];
139 for (
int i= 0;
i <= n;
i++)
142 swap [
i]=
new int [3];
166 for (
i= 1;
i < n;
i++)
168 for (
int j= 1;
j < n -
i + 1;
j++)
174 buf3=
swap [
j + 1] [2];
187 buf3=
swap [
j + 1] [2];
199 for (
i= n;
i > 0;
i--)
214#if defined(HAVE_NTL) || defined(HAVE_FLINT)
224 int k=
info.getGFDegree();
226 if (factors.
length() == 1)
235 if (!
k &&
beta.level() != 1)
250 int *
v=
new int [
T.length()];
251 for (
int i= 0;
i <
T.length();
i++)
253 bool noSubset=
false;
257 bool trueFactor=
false;
258 while (
T.length() >= 2*
s)
260 while (noSubset ==
false)
321 if (
T.length() < 2*
s ||
T.length() ==
s)
337 if (
T.length() < 2*
s ||
T.length() ==
s)
344 for (
int i= 0;
i <
T.length();
i++)
348 if (
T.length() < 2*
s)
359#if defined(HAVE_NTL) || defined(HAVE_FLINT)
364 if (factors.
length() == 1)
377 int *
v=
new int [
T.length()];
378 for (
int i= 0;
i <
T.length();
i++)
380 bool noSubset=
false;
386 while (
T.length() >= 2*
s)
388 while (noSubset ==
false)
416 if (
T.length() < 2*
s ||
T.length() ==
s)
428 if (
T.length() < 2*
s ||
T.length() ==
s)
434 for (
int i= 0;
i <
T.length();
i++)
438 if (
T.length() < 2*
s)
446#if defined(HAVE_NTL) || defined(HAVE_FLINT)
449 success,
const int deg,
const CFList& MOD,
const int bound)
451 int adaptedLiftBound= 0;
477 if (adaptedLiftBound < deg)
479 if (adaptedLiftBound <
degree (F) + 1)
485 adaptedLiftBound= deg;
491 if (e + 1 <
degree (F) + 1)
492 adaptedLiftBound= deg;
494 adaptedLiftBound= e + 1;
500 adaptedLiftBound= deg;
508 return adaptedLiftBound;
512#if defined(HAVE_NTL) || defined(HAVE_FLINT)
522 int k=
info.getGFDegree();
523 int adaptedLiftBound= 0;
536 if (!
k &&
beta.level() != 1)
574 if (adaptedLiftBound < deg)
576 if (adaptedLiftBound <
degree (F) + 1)
582 adaptedLiftBound= deg;
588 if (e + 1 <
degree (F) + 1)
589 adaptedLiftBound= deg;
591 adaptedLiftBound= e + 1;
597 adaptedLiftBound= deg;
606 return adaptedLiftBound;
610#if defined(HAVE_NTL) || defined(HAVE_FLINT)
613 bool& success,
const int deg,
const CFList& MOD,
646 if (adaptedLiftBound < deg)
648 if (adaptedLiftBound <
degree (F) + 1)
651 adaptedLiftBound=
tmin (e + 1, deg);
653 adaptedLiftBound= deg;
663#if defined(HAVE_NTL) || defined(HAVE_FLINT)
673 int k=
info.getGFDegree();
690 if (!
k &&
beta.level() != 1)
731 if (adaptedLiftBound < deg)
733 if (adaptedLiftBound <
degree (F) + 1)
736 adaptedLiftBound=
tmin (e + 1, deg);
738 adaptedLiftBound= deg;
748#if defined(HAVE_NTL) || defined(HAVE_FLINT)
749#define CHAR_THRESHOLD 8
752 CFList& list,
const bool& GF,
bool& fail)
765 if (!GF &&
alpha.level() == 1)
770 else if (!GF &&
alpha.level() != 1)
806 for (
int i= 0;
i <
k;
i++)
815 else if (
alpha.level() != 1)
827 if (
find (list, random))
838 eval.insert (
eval.getFirst()(
i.getItem(),
l));
842 if (!
find (list, random))
852 if (!
find (list, random))
867 if (!
find (list, random))
879 if (!
find (list, random))
891 if (!
find (list, random))
902 if (!
find (list, random))
915 }
while (
find (list, random));
939 for (
int i= lev;
i <=
A.level();
i++)
974 for (
i=
i - 2;
i > 0;
i--)
983#if defined(HAVE_NTL) || defined(HAVE_FLINT)
990 bool extension=
info.isInExtension();
991 CFList bufFactors= biFactors;
998 int smallFactorDeg= 11;
1000 int adaptedLiftBound= 0;
1001 int liftBound= liftBounds[1];
1003 earlySuccess=
false;
1004 CFList earlyReconstFactors;
1010 if (smallFactorDeg >= liftBound)
1014 else if (smallFactorDeg >=
degree (
buf) + 1)
1018 if (
Aeval.length() == 2)
1022 (
buf,
result, adaptedLiftBound, earlySuccess,
1026 (
buf,
result, adaptedLiftBound, earlySuccess,
1028 (
buf) + 1, MOD, liftBound);
1043 liftBounds[1]= adaptedLiftBound;
1044 liftBound= adaptedLiftBound;
1046 Pi, diophant, Mat, MOD);
1049 liftBounds[1]= adaptedLiftBound;
1051 else if (smallFactorDeg <
degree (
buf) + 1)
1053 liftBounds[1]= smallFactorDeg;
1055 if (
Aeval.length() == 2)
1059 earlySuccess, smallFactorDeg, MOD,
1064 smallFactorDeg, MOD, liftBound);
1070 smallFactorDeg, MOD, liftBound);
1081 Pi, diophant, Mat, MOD);
1082 if (
Aeval.length() == 2)
1108 liftBounds[1]= adaptedLiftBound;
1109 liftBound= adaptedLiftBound;
1111 Pi, diophant, Mat, MOD);
1114 liftBounds[1]= adaptedLiftBound;
1117 liftBounds[1]= adaptedLiftBound;
1122 if (
Aeval.length() > 2)
1129 int liftBoundsLength=
Aeval.getLast().level() - 1;
1130 for (
int i= 2;
i <= liftBoundsLength &&
j.hasItem();
i++,
j++)
1132 earlySuccess=
false;
1135 liftBound= liftBounds[
i];
1139 if (smallFactorDeg >= liftBound)
1141 liftBounds[
i - 1], liftBounds[
i]);
1142 else if (smallFactorDeg >=
degree (
buf) + 1)
1147 if (
Aeval.length() ==
i + 1)
1151 (
buf,
result, adaptedLiftBound, earlySuccess,
1155 (
buf,
result, adaptedLiftBound, earlySuccess,
1163 + 1, MOD, liftBound);
1173 liftBounds[
i]= adaptedLiftBound;
1174 liftBound= adaptedLiftBound;
1176 Pi, diophant, Mat, MOD);
1180 liftBounds[
i]= adaptedLiftBound;
1183 else if (smallFactorDeg <
degree (
buf) + 1)
1186 liftBounds[
i - 1], smallFactorDeg);
1188 if (
Aeval.length() ==
i + 1)
1192 (
buf,
result, adaptedLiftBound, earlySuccess,
1193 smallFactorDeg, MOD, liftBound);
1196 (
buf,
result, adaptedLiftBound, earlySuccess,
1204 smallFactorDeg, MOD, liftBound);
1208 smallFactorDeg, MOD, liftBound);
1215 degree (
buf) + 1, Pi, diophant, Mat, MOD);
1216 if (
Aeval.length() ==
i + 1)
1220 (
buf,
result, adaptedLiftBound, earlySuccess,
1224 (
buf,
result, adaptedLiftBound, earlySuccess,
1233 (
buf) + 1, MOD, liftBound);
1243 liftBounds[
i]= adaptedLiftBound;
1244 liftBound= adaptedLiftBound;
1246 Pi, diophant, Mat, MOD);
1249 liftBounds[
i]= adaptedLiftBound;
1252 liftBounds[
i]= adaptedLiftBound;
1282 g=
gcd (
i.getItem().factor(),
j.getItem().factor());
1285 j.getItem()=
CFFactor (
j.getItem().factor()/
g,
j.getItem().exp());
1286 i.getItem()=
CFFactor (
i.getItem().factor()/
g,
i.getItem().exp());
1305 if (
l.length() == 1)
1310 if (differentSecondVarFactors[
i].isEmpty())
1314 result= differentSecondVarFactors[
i];
1321 for (
CFListIterator iter2= differentSecondVarFactors[
i];iter2.hasItem();
1324 iter1.
getItem() *= iter2.getItem();
1339 if (differentSecondVarFactors[
i].isEmpty())
1345 for (iter2= differentSecondVarFactors[
i]; iter2.
hasItem();
1360 if (!
g.inCoeffDomain())
1373 for (iter2= multiplier; iter2.
hasItem(); iter1++, iter2++)
1395 sqrfFactorization=
sqrFree (F);
1399 sqrfPartF *=
i.getItem().factor();
1412 factors= uniFactors;
1420 sqrfFactors=
sqrFree (
i.getItem());
1424 tmp2.append (
iter.getItem().factor());
1425 tmp *=
iter.getItem().factor();
1427 i.getItem()= tmp/
Lc(tmp);
1428 bufSqrfFactors [
k]= sqrfFactors;
1431 for (
int i= 0;
i < factors.
length() - 1;
i++)
1440 for (
int i= 0;
i < uniFactors.
length();
i++)
1446 if (
iter.getItem().factor().inCoeffDomain())
1449 Lc (
iter.getItem().factor()),
1450 iter.getItem().exp());
1458 if (
iter.getItem().factor().inCoeffDomain())
1461 Lc (
iter.getItem().factor()),
1462 iter.getItem().exp());
1463 if (!
find (factors,
iter.getItem().factor()))
1477#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1481 CFList* & differentSecondVarLCs,
int lSecondVarLCs,
1486 if (
LCF.inCoeffDomain())
1489 for (
int i= 1;
i <= LCFFactors.
length() + 1;
i++)
1500 if (
LCF.isUnivariate())
1503 int LCFLevel=
LCF.level();
1514 for (
int i= 0;
i < lSecondVarLCs;
i++)
1516 for (
j= differentSecondVarLCs[
i];
j.hasItem();
j++)
1518 if (
j.getItem().level() == LCFLevel)
1526 result= differentSecondVarLCs [
i];
1541 CFList factors= LCFFactors;
1544 i.getItem()=
M (
i.getItem());
1548 CFList evalSqrfPartF, bufFactors;
1565 bufFactors, bufSqrfFactors, evalSqrfPartF,
evalPoint);
1567 bool foundDifferent=
false;
1576 for (
int i= 0;
i < lSecondVarLCs;
i++)
1578 if (!differentSecondVarLCs [
i].isEmpty())
1580 bool allConstant=
true;
1581 for (
iter= differentSecondVarLCs[
i];
iter.hasItem();
iter++)
1583 if (!
iter.getItem().inCoeffDomain())
1593 bufFactors= differentSecondVarLCs [
i];
1599 bufBufFactors= bufFactors;
1609 bufSqrfFactors, evalSqrfPartF,
evalPoint);
1612 foundDifferent=
true;
1617 differentSecondVarLCs [
i]=
l;
1621 if (!pass &&
i == lSecondVarLCs - 1)
1625 for (
int j= 1;
j <= factors.
length();
j++)
1629 delete [] bufSqrfFactors;
1639 for (
int j= 1;
j <= factors.
length();
j++)
1643 delete [] bufSqrfFactors;
1647 factors= bufFactors;
1649 bufFactors= factors;
1652 dummy [0]= sqrfPartF;
1655 sqrfPartF= MM (sqrfPartF);
1658 iter.getItem()= MM (
iter.getItem());
1661 for (
int i= 2;
i <= varsSqrfPartF.
level();
i++)
1666 sqrfPartF=
shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1667 if (factors.
length() > 1)
1671 for (
int i= 0;
i < factors.
length();
i++)
1672 leadingCoeffs.
append (LC1);
1675 CFList oldFactors= factors;
1679 bool success=
false;
1682 if (
size (oldSqrfPartFPowLC)/
getNumVars (oldSqrfPartFPowLC) < 500 &&
1684 oldFactors, 2, leadingCoeffs, heuResult))
1695 for (
int i= 0;
i < factors.
length();
i++)
1696 leadingCoeffs[
i]= LC1;
1699 i.getItem() *= LC1 (0,2)/
Lc (
i.getItem());
1705 int liftBound=
degree (newSqrfPartF,2) + 1;
1711 leadingCoeffs,
false);
1713 if (sqrfPartF.
level() > 2)
1715 int* liftBounds=
new int [sqrfPartF.
level() - 1];
1716 bool noOneToOne=
false;
1720 for (
int i= 0;
i < factors.
length();
i++)
1722 leadingCoeffs2 [sqrfPartF.
level() - 3]= LCs;
1723 for (
int i= sqrfPartF.
level() - 1;
i > 2;
i--)
1726 j.getItem()=
j.getItem() (0,
i + 1);
1727 leadingCoeffs2 [
i - 3]= LCs;
1731 int liftBoundsLength= sqrfPartF.
level() - 1;
1732 for (
int i= 0;
i < liftBoundsLength;
i++)
1733 liftBounds [
i]=
degree (sqrfPartF,
i + 2) + 1;
1737 diophant, Pi, liftBounds, sqrfPartF.
level() - 1, noOneToOne);
1738 delete [] leadingCoeffs2;
1739 delete [] liftBounds;
1752 factors=
CFList (oldSqrfPartF/contF);
1757 iter.getItem()= NN (
iter.getItem());
1761 for (
int i= 0;
i < LCFFactors.
length();
i++)
1764 for (
k= bufSqrfFactors[
i];
k.hasItem();
k++)
1766 int pos=
findItem (bufFactors,
k.getItem().factor());
1768 tmp *=
power (
getItem (interMedResult, pos),
k.getItem().exp());
1778 i.getItem()=
N (
i.getItem());
1783 CFList l= differentSecondVarLCs [
j];
1786 differentSecondVarLCs [
j]=
l;
1794 if (!
result.getFirst().inCoeffDomain())
1801 CFList l= differentSecondVarLCs [
j];
1804 differentSecondVarLCs [
j]=
l;
1812 for (
int i=
y.level();
i > 1;
i--)
1824 if (lSecondVarLCs -
level > 0)
1827 int j= lSecondVarLCs+2;
1830 for (
i= evaluation2;
i.hasItem();
i++,
j--)
1835 i.getItem()= evaluation2.
getLast();
1846 delete [] bufSqrfFactors;
1862 for (
CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
1873 for (
int j=
level+1;
j < lSecondVarLCs;
j++)
1877 if (!differentSecondVarLCs[
j].isEmpty())
1879 differentSecondVarLCs2[
j -
level - 1]= differentSecondVarLCs[
j];
1880 i= differentSecondVarLCs2[
j-
level - 1];
1909 for (
i=newLCs;
i.hasItem();
i++)
1911 for (
int j= 1;
j < lSecondVarLCs-
level;
j++)
1913 for (
i= differentSecondVarLCs2[
j-1];
i.hasItem();
i++)
1921 differentSecondVarLCs2, lSecondVarLCs -
level - 1,
1924 if (dummyvar.
level() != 1)
1926 for (
i= recursiveResult;
i.hasItem();
i++)
1929 for (
i= recursiveResult;
i.hasItem();
i++)
1931 for (
int j= lSecondVarLCs-
level-1;
j > 0;
j--)
1939 delete [] bufSqrfFactors;
1940 delete [] differentSecondVarLCs2;
1945 iter=recursiveResult;
1947 i.getItem()=
iter.getItem();
1950 for (;
i.hasItem();
i++,
iter++)
1951 i.getItem() *=
iter.getItem();
1952 delete [] differentSecondVarLCs2;
1959 delete [] bufSqrfFactors;
1972 bool preserveDegree=
true;
1975 for (
int i=
A.level();
i > 2;
i--)
1980 preserveDegree=
true;
1982 for (
j=
A.level();
j > 1;
j--,
iter++)
1988 tmp= tmp (
iter.getItem(),
j);
1990 if ((
degree (tmp,
i) != degAi) ||
1991 (
degree (tmp, 1) != degA1))
1993 preserveDegree=
false;
1998 if (!
content(tmp,1).inCoeffDomain())
1999 preserveDegree=
false;
2000 if (!
content(tmp).inCoeffDomain())
2001 preserveDegree=
false;
2002 if (!(
gcd (
deriv (tmp,
x), tmp)).inCoeffDomain())
2003 preserveDegree=
false;
2027 for (; iter1.
hasItem(); iter1++, iter2++)
2030 if (!g2.inCoeffDomain())
2033 l2.
append (iter2.getItem());
2049 CFList uniFactorsOfFactors1;
2067 uniFactorsOfFactors1.
append (tmp);
2076 while (!uniFactorsOfFactors1.
isEmpty())
2078 tmp= uniFactorsOfFactors1.
getFirst();
2122 int *
v=
new int [
T.length()];
2123 for (
int i= 0;
i <
T.length();
i++)
2125 bool nosubset=
false;
2127 TT=
copy (factors1);
2128 int recombinations= 0;
2129 while (
T.length() >= 2*
s &&
s <= thres)
2131 while (nosubset ==
false)
2133 if (
T.length() ==
s)
2136 if (recombinations ==
factors2.length() - 1)
2143 if (nosubset)
break;
2153 if (nosubset)
break;
2157 if (
T.length() < 2*
s ||
T.length() ==
s)
2159 if (recombinations ==
factors2.length() - 1)
2166 for (
int i= 0;
i <
T.length();
i++)
2172 if (
T.length() < 2*
s)
2181#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2193 for (
int j= 0;
j <
A.level() - 2;
j++)
2200 else if (
info.getAlpha().level() == 1)
2211 if (factors.
length() == 1)
2227 for (
int i=
A.max();
i >=
A.min();
i--)
2238 for (
int j= 0;
j <
A.level() - 2;
j++)
2262 int pos,
index, checklength;
2263 bool leaveLoop=
false;
2265 for (
int j= 0;
j < AevalLength;
j++)
2294 checklength= biFactors.
length();
2296 if (checklength > biFactors.
length())
2345 bool leaveLoop=
false;
2346 for (
int j= 0;
j <
A.level() - 2;
j++)
2390 for (
int i= n - 1;
i > 2;
i--,
iter++)
2392 for (
j=
l;
j.hasItem();
j++)
2393 j.getItem()=
j.getItem() (
iter.getItem(),
i + 1);
2398 i.getItem()=
i.getItem() (
iter.getItem(), 3);
2403 for (
int i= 0;
i < n-2;
i++)
2405 ii= normalizeFactor;
2406 for (
j= LCs [
i];
j.hasItem();
j++, ii++)
2415 iter.getItem() *= hh;
2428 int k=
info.getGFDegree();
2443 int *
v=
new int [
T.length()];
2444 for (
int i= 0;
i <
T.length();
i++)
2446 bool noSubset=
false;
2450 bool trueFactor=
false;
2451 while (
T.length() >= 2*
s)
2453 while (noSubset ==
false)
2455 if (
T.length() ==
s)
2472 if (noSubset)
break;
2480 if (!
k &&
beta.level() == 1)
2504 if (
T.length() < 2*
s ||
T.length() ==
s)
2515 if (noSubset)
break;
2520 if (
T.length() < 2*
s ||
T.length() ==
s)
2528 for (
int i= 0;
i <
T.length();
i++)
2532 if (
T.length() < 2*
s)
2545 CFList*& oldAeval,
int lengthAeval2,
2563 for (
i= 0;
i < lengthAeval2;
i++)
2565 if (oldAeval[
i].isEmpty())
2567 if (oldAeval[
i].getFirst().
level() ==
w.level())
2570 oldAeval[
i]= biFactors;
2573 for (
int ii= 0; ii < tmp.
size(); ii++)
2577 for (
int ii= 0; ii < tmp.
size(); ii++)
2584 for (
int j= 0;
j <
tmp2.size();
j++)
2600 iter.getItem() *= LCmultipler;
2602 for (
int i=
A.level();
i > 2;
i--,
iter++)
2603 tmp= tmp (
iter.getItem(),
i);
2608 i.getItem() *= tmp/
LC (
i.getItem(), 1);
2609 i.getItem() /=
Lc (
i.getItem());
2618 const CFList& oldBiFactors)
2631 for (
int i= 0;
i < lengthAeval;
i++)
2633 if (oldAeval[
i].isEmpty())
2642 for (
iter= leadingCoeffs[lengthAeval-1];
iter.hasItem();
iter++, iter2++)
2644 tmp=
iter.getItem()/LCmultiplier;
2645 for (
int i=1;
i <= tmp.
level();
i++)
2657 tmp=
iter.getItem();
2661 tmp /=
myGetVars (ii.getItem().factor());
2664 if (multi == ii.getItem().exp())
2672 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.
hasItem();iter2++,
2675 if (index2 ==
index)
2679 tmp= ii.getItem().factor();
2683 for (
int jj=
A.level(); jj > 2; jj--, iter3++)
2684 tmp= tmp (iter3.
getItem(), jj);
2688 for (iter3= biFactors; iter3.
hasItem(); iter3++, index3++)
2690 if (index3 == index2)
2694 if (
fdivides (ii.getItem().factor(),
A, quot3))
2709 iter.getItem() /=
getVars (ii.getItem().factor());
2721 for (iter2= leadingCoeffs[lengthAeval-1];iter2.
hasItem();iter2++,
2724 if (index2 ==
index)
2726 tmp=
power (ii.getItem().factor(), ii.getItem().exp());
2732 for (
int jj=
A.level(); jj > 2; jj--, iter3++)
2733 tmp= tmp (iter3.
getItem(), jj);
2737 for (iter3= biFactors; iter3.
hasItem(); iter3++, index3++)
2739 if (index3 == index2)
2765 bool& foundTrueMultiplier)
2768 if (
fdivides (pLCs,
LC (oldA,1)) && (
LC(oldA,1)/pLCs).inCoeffDomain())
2774 foundTrueMultiplier=
true;
2781 bool& foundTrueMultiplier)
2789 cont=
gcd (cont, LCmultiplier);
2793 foundTrueMultiplier=
true;
2795 for (iter2= leadingCoeffs; iter2.
hasItem(); iter2++, index2++)
2797 if (index2 ==
index)
2799 iter2.
getItem() /= LCmultiplier;
2812 int lengthAeval,
bool& foundMultiplier)
2820 if ((LCmultiplier/
iter.getItem()).inCoeffDomain() &&
2827 for (
int i= 0;
i < lengthAeval;
i++)
2829 if (oldAeval[
i].isEmpty())
2835 if (vars.
level() <= 2)
2839 iter3.hasItem(); iter3++, index2++)
2841 if (index2 ==
index)
2843 iter3.getItem() /= LCmultiplier;
2848 foundMultiplier=
true;
2867 if (!
iter.getItem().isOne() &&
2873 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.
hasItem();
2876 if (index2 ==
index)
2879 foundMultiplier=
true;
2883 A /=
iter.getItem();
2884 LCmultiplier /=
iter.getItem();
2893 for (
int i= 0;
i < lengthAeval;
i++)
2895 if (oldAeval[
i].isEmpty())
2905 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.
hasItem();
2908 if (index2 ==
index)
2910 iter2.
getItem() /= LCmultiplier;
2911 foundMultiplier=
true;
2923#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2947 bool extension=
info.isInExtension();
2952 if (extension ==
false)
2966 if (
buf.getFirst().inCoeffDomain())
2983 if (
A.inCoeffDomain())
2987 if (
i.getItem().inCoeffDomain())
2991 lcmCont /=
i.getItem();
3001 return contentAFactors;
3011 if (
A.isUnivariate ())
3014 append (factors, contentAFactors);
3026 for (
int i= 1;
i <=
A.level();
i++)
3029 derivZ=
deriv (bufA, z);
3039 gcdDerivZ=
gcd (bufA, derivZ);
3064 "time to check main var over Fq: ");
3066 "time to preprocess poly and extract content over Fq: ");
3073 CFList biFactors, bufBiFactors;
3075 int lift, bufLift, lengthAeval2=
A.level()-2;
3078 logarithm= ceil (logarithm);
3079 if (factorNums < (
int) logarithm)
3080 factorNums= (int) logarithm;
3084 int differentSecondVar= 0;
3087 for (
int i= 0;
i < factorNums;
i++)
3095 "time to find evaluation point over Fq: ");
3098 if (fail && (
i == 0))
3113 delete [] bufAeval2;
3137 else if (fail && (
i > 0))
3143 "time for evaluation wrt diff second vars over Fq: ");
3145 for (
int j= 0;
j < lengthAeval2;
j++)
3147 if (!bufAeval2[
j].isEmpty())
3154 if (!GF &&
alpha.level() == 1)
3161 "time for bivariate factorization: ");
3164 if (bufBiFactors.
length() == 1)
3176 delete [] bufAeval2;
3185 biFactors= bufBiFactors;
3187 for (
int j= 0;
j < lengthAeval2;
j++)
3188 Aeval2 [
j]= bufAeval2 [
j];
3189 differentSecondVar= counter;
3195 counter > differentSecondVar)
3199 biFactors= bufBiFactors;
3201 for (
int j= 0;
j < lengthAeval2;
j++)
3202 Aeval2 [
j]= bufAeval2 [
j];
3203 differentSecondVar= counter;
3208 evalPoly +=
j.getItem()*
power (
x,
k);
3212 delete [] bufAeval2;
3221 "time for bivariate factorization wrt diff second vars over Fq: ");
3224 "total time for eval and bivar factors over Fq: ");
3269 if (differentSecondVar == lengthAeval2)
3271 bool zeroOccured=
false;
3274 if (
iter.getItem().isZero())
3303 for (
int i= 0;
i < lengthAeval2;
i++)
3304 oldAeval[
i]= Aeval2[
i];
3310 biFactorsLCs.
append (
LC (
i.getItem(), 1));
3322 CFList oldBiFactors= biFactors;
3328 if (!LCmultiplierIsConst)
3337 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
3338 bufBiFactors= biFactors;
3341 if (!LCmultiplierIsConst)
3344 for (
int i= 0;
i < lengthAeval2;
i++)
3346 if (!oldAeval[
i].isEmpty())
3351 "time to precompute LC over Fq: ");
3355 bool LCheuristic=
false;
3361 CFList oldFactors= factors;
3382 "time for successful LucksWang over Fq: ");
3385 else if (factors.
length() > 0)
3394 for (
int j=1;
j <=
i-oneCount;
j++)
3397 for (
int j= 0;
j < lengthAeval2;
j++)
3399 l= leadingCoeffs2[
j];
3401 for (
int k=1;
k <=
i-oneCount;
k++)
3404 leadingCoeffs2[
j]=
l;
3409 bufFactors= factors;
3412 else if (!LCmultiplierIsConst && factors.
length() == 0)
3415 factors= oldFactors;
3417 bool foundTrueMultiplier=
false;
3418 LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
3419 contents, LCs, foundTrueMultiplier);
3420 if (foundTrueMultiplier)
3423 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3424 for (
int i= lengthAeval2-1;
i > -1;
i--)
3431 bool foundMultiplier=
false;
3432 LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
3433 A, leadingCoeffs2, lengthAeval2, foundMultiplier);
3436 if (foundMultiplier)
3438 foundMultiplier=
false;
3439 LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
3440 lengthAeval2, leadingCoeffs2,
A, LCmultiplier,
3446 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
3449 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3455 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3456 for (
int i= lengthAeval2-1;
i > -1;
i--)
3462 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
3466 biFactors= bufBiFactors;
3467 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3468 LCmultiplier= bufLCmultiplier;
3478 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.
isEmpty()
3482 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3485 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3486 for (
int i= lengthAeval2-1;
i > -1;
i--)
3491 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
3495 biFactors= bufBiFactors;
3496 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3497 LCmultiplier= bufLCmultiplier;
3509 for (
int i= 0;
i < lengthAeval2-1;
i++)
3511 for (
iter= leadingCoeffs2[lengthAeval2-1];
iter.hasItem();
iter++)
3514 for (
int i=
A.level() - 4;
i > -1;
i--)
3516 if (
i + 1 == lengthAeval2-1)
3523 "time to shift evaluation point to zero: ");
3527 int* liftBounds=
new int [
A.level() - 1];
3528 int liftBoundsLength=
A.level() - 1;
3529 for (
int i= 0;
i < liftBoundsLength;
i++)
3532 Aeval.removeFirst();
3533 bool noOneToOne=
false;
3536 Pi, liftBounds, liftBoundsLength, noOneToOne);
3538 "time for non monic hensel lifting over Fq: ");
3547 "time to recover factors over Fq: ");
3551 factors=
Union (factors, bufFactors);
3553 if (extension && !noOneToOne)
3558 if (!LCmultiplierIsConst && LCheuristic)
3561 biFactors= bufBiFactors;
3562 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3563 delete [] liftBounds;
3565 goto tryAgainWithoutHeu;
3570 biFactors= oldBiFactors;
3579 for (;
i.hasItem();
i++)
3588 for (;
i.hasItem();
i++)
3590 LCA=
LC (
i.getItem(), 1);
3591 extgcd (LCA, yToLift, LCA, dummy);
3592 i.getItem()=
mod (
i.getItem()*LCA, yToLift);
3595 liftBoundsLength= F.
level() - 1;
3600 CFList earlyFactors, liftedFactors;
3603 (
A, MOD, liftBounds, earlySuccess, earlyFactors,
3606 "time for hensel lifting over Fq: ");
3613 "time for factor recombination: ");
3620 "time for factor recombination: ");
3624 factors=
Union (factors, earlyFactors);
3629 int kk=
Aeval.getLast().level();
3632 if (
i.getItem().level() < kk)
3634 i.getItem()=
i.getItem() (
Variable (kk) -
j.getItem(), kk);
3646 swap (factors, swapLevel, swapLevel2,
x);
3647 append (factors, contentAFactors);
3652 delete[] liftBounds;
3667 int k=
info.getGFDegree();
3668 char cGFName=
info.getGFName();
3677 bool extension=
true;
3698 else if (
p >= 7 &&
p*
p < (1<<16))
3722 else if (!GF && (
alpha !=
w))
3740 bool primFail=
false;
3743 ASSERT (!primFail,
"failure in integer factorizer");
3760 bool primFail=
false;
3762 ASSERT (!primFail,
"failure in integer factorizer");
3772 bufA=
mapUp (bufA,
beta,
v, delta, imPrimElem, source, dest);
3784 bool extension=
true;
3788 if (
pow ((
double)
p, (
double) extensionDeg) < (1<<16))
3814 if (
pow ((
double)
p, (
double) 2*extensionDeg) < (1<<16))
3830 bool primFail=
false;
Rational pow(const Rational &a, int e)
const CanonicalForm CFMap CFMap & N
static const double log2exp
static Variable chooseExtension(const Variable &alpha)
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
#define ASSERT(expression, message)
#define GaloisFieldDomain
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
generate random irreducible univariate polynomials
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
int findItem(const CFList &list, const CanonicalForm &item)
helper function
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
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
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 ,...
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
This file implements functions to map between extensions of finite fields.
generate random integers, random elements of finite fields
generate random elements in F_p(alpha)
CanonicalForm generate() const
class to iterate through CanonicalForm's
ExtensionInfo contains information about extension.
generate random elements in F_p
CanonicalForm generate() const
generate random elements in GF
CanonicalForm generate() const
factory's class for variables
functions to print debug output
const CanonicalForm int const CFList & evaluation
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
const Variable & v
< [in] a sqrfree bivariate poly
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
CFList *& Aeval
<[in] poly
CFList int bool & irred
[in,out] Is A irreducible?
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
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...
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
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
CFArray copy(const CFList &list)
write elements of list into an array
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...
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 ...
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
This file provides utility functions for multivariate factorization.
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
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,...
static CanonicalForm myContent(const CanonicalForm &F)
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,...
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.
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
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...
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...
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 ...
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 checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
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...
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...
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
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 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
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
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)
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...
CFList conv(const CFArray &A)
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
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 gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
static int newMainVariableSearch(CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
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...
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
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 ...
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
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...
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
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....
static CanonicalForm listGCD(const CFList &L)
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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...
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...
This file provides functions for factorizing a multivariate polynomial over , or GF.
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
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 henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
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.
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
This file defines functions for Hensel lifting.
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
This file defines functions for fast multiplication and division with remainder.
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
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...
This file provides functions for sparse heuristic Hensel lifting.
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void FACTORY_PUBLIC prune(Variable &alpha)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
INST_VAR CanonicalForm gf_mipo
static BOOLEAN length(leftv result, leftv arg)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
static int index(p_Length length, p_Ord ord)
int status int void size_t count
int status int void * buf
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)