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)
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;
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();
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)
801 if (list.length() >=
bound)
806 for (
int i= 0;
i <
k;
i++)
827 if (
find (list, random))
842 if (!
find (list, random))
843 list.append (random);
852 if (!
find (list, random))
853 list.append (random);
867 if (!
find (list, random))
868 list.append (random);
879 if (!
find (list, random))
880 list.append (random);
891 if (!
find (list, random))
892 list.append (random);
902 if (!
find (list, random))
903 list.append (random);
910 if (list.length() >=
bound)
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)
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;
1059 earlySuccess, smallFactorDeg, MOD,
1064 smallFactorDeg, MOD, liftBound);
1070 smallFactorDeg, MOD, liftBound);
1081 Pi, diophant, Mat, MOD);
1108 liftBounds[1]= adaptedLiftBound;
1109 liftBound= adaptedLiftBound;
1111 Pi, diophant, Mat, MOD);
1114 liftBounds[1]= adaptedLiftBound;
1117 liftBounds[1]= adaptedLiftBound;
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)
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);
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);
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();
1348 if (iter2.
getItem().inCoeffDomain())
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());
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++)
1477#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1481 CFList* & differentSecondVarLCs,
int lSecondVarLCs,
1489 for (
int i= 1;
i <= LCFFactors.
length() + 1;
i++)
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;
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);
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);
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;
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;
1950 for (;
i.hasItem();
i++,
iter++)
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++)
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)
2143 if (nosubset)
break;
2153 if (nosubset)
break;
2157 if (
T.length() < 2*
s ||
T.length() ==
s)
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++)
2374 biFactors.
length() - list.length() + 1,
2390 for (
int i= n - 1;
i > 2;
i--,
iter++)
2392 for (
j=
l;
j.hasItem();
j++)
2403 for (
int i= 0;
i < n-2;
i++)
2405 ii= normalizeFactor;
2406 for (
j= LCs [
i];
j.hasItem();
j++, ii++)
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;
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())
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++)
2602 for (
int i=
A.level();
i > 2;
i--,
iter++)
2608 i.getItem() *= tmp/
LC (
i.getItem(), 1);
2609 i.getItem() /=
Lc (
i.getItem());
2618 const CFList& oldBiFactors)
2625 if (sqrfMultiplier.
getFirst().factor().inCoeffDomain())
2631 for (
int i= 0;
i < lengthAeval;
i++)
2633 if (oldAeval[
i].isEmpty())
2645 for (
int i=1;
i <= tmp.
level();
i++)
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))
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;
2873 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.
hasItem();
2876 if (index2 ==
index)
2879 foundMultiplier=
true;
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())
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);
3209 list.append (evalPoly);
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;
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++)
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++)
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);
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
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
ExtensionInfo contains information about extension.
generate random elements in F_p
CanonicalForm generate() const
generate random elements in GF
CanonicalForm generate() const
void remove(int moveright)
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 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)