98 return gcd (resultHi, resultLo);
140 int **
swap=
new int* [n + 1];
141 for (
int i= 0;
i <= n;
i++)
144 swap [
i]=
new int [3];
168 for (
i= 1;
i < n;
i++)
170 for (
int j= 1;
j < n -
i + 1;
j++)
176 buf3=
swap [
j + 1] [2];
189 buf3=
swap [
j + 1] [2];
201 for (
i= n;
i > 0;
i--)
227 if (factors.
length() == 1)
251 int *
v=
new int [
T.length()];
252 for (
int i= 0;
i <
T.length();
i++)
254 bool noSubset=
false;
258 bool trueFactor=
false;
259 while (
T.length() >= 2*
s)
261 while (noSubset ==
false)
322 if (
T.length() < 2*
s ||
T.length() ==
s)
338 if (
T.length() < 2*
s ||
T.length() ==
s)
345 for (
int i= 0;
i <
T.length();
i++)
349 if (
T.length() < 2*
s)
363 if (factors.
length() == 1)
376 int *
v=
new int [
T.length()];
377 for (
int i= 0;
i <
T.length();
i++)
379 bool noSubset=
false;
385 while (
T.length() >= 2*
s)
387 while (noSubset ==
false)
415 if (
T.length() < 2*
s ||
T.length() ==
s)
427 if (
T.length() < 2*
s ||
T.length() ==
s)
433 for (
int i= 0;
i <
T.length();
i++)
437 if (
T.length() < 2*
s)
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;
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;
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)
795 for (
int i= 0;
i <
k;
i++)
816 if (
find (list, random))
831 if (!
find (list, random))
841 if (!
find (list, random))
856 if (!
find (list, random))
868 if (!
find (list, random))
880 if (!
find (list, random))
891 if (!
find (list, random))
904 }
while (
find (list, random));
927 for (
int i= lev;
i <=
A.level();
i++)
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)
1001 else if (smallFactorDeg >=
degree (
buf) + 1)
1009 (
buf,
result, adaptedLiftBound, earlySuccess,
1013 (
buf,
result, adaptedLiftBound, earlySuccess,
1015 (
buf) + 1, MOD, liftBound);
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;
1046 earlySuccess, smallFactorDeg, MOD,
1051 smallFactorDeg, MOD, liftBound);
1057 smallFactorDeg, MOD, liftBound);
1068 Pi, diophant, Mat, MOD);
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)
1128 liftBounds[
i - 1], liftBounds[
i]);
1129 else if (smallFactorDeg >=
degree (
buf) + 1)
1138 (
buf,
result, adaptedLiftBound, earlySuccess,
1142 (
buf,
result, adaptedLiftBound, earlySuccess,
1150 + 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)
1173 liftBounds[
i - 1], smallFactorDeg);
1179 (
buf,
result, adaptedLiftBound, earlySuccess,
1180 smallFactorDeg, MOD, liftBound);
1183 (
buf,
result, adaptedLiftBound, earlySuccess,
1191 smallFactorDeg, MOD, liftBound);
1195 smallFactorDeg, MOD, liftBound);
1202 degree (
buf) + 1, Pi, diophant, Mat, MOD);
1207 (
buf,
result, adaptedLiftBound, earlySuccess,
1211 (
buf,
result, adaptedLiftBound, earlySuccess,
1220 (
buf) + 1, MOD, liftBound);
1230 liftBounds[
i]= adaptedLiftBound;
1231 liftBound= adaptedLiftBound;
1233 Pi, diophant, Mat, MOD);
1236 liftBounds[
i]= adaptedLiftBound;
1239 liftBounds[
i]= adaptedLiftBound;
1268 g=
gcd (
i.getItem().factor(),
j.getItem().factor());
1271 j.getItem()=
CFFactor (
j.getItem().factor()/
g,
j.getItem().exp());
1272 i.getItem()=
CFFactor (
i.getItem().factor()/
g,
i.getItem().exp());
1291 if (
l.length() == 1)
1296 if (differentSecondVarFactors[
i].isEmpty())
1300 result= differentSecondVarFactors[
i];
1307 for (
CFListIterator iter2= differentSecondVarFactors[
i];iter2.hasItem();
1310 iter1.
getItem() *= iter2.getItem();
1325 if (differentSecondVarFactors[
i].isEmpty())
1331 for (iter2= differentSecondVarFactors[
i]; iter2.
hasItem();
1334 if (iter2.
getItem().inCoeffDomain())
1346 if (!
g.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());
1413 i.getItem()= tmp/
Lc(tmp);
1414 bufSqrfFactors [
k]= sqrfFactors;
1417 for (
int i= 0;
i < factors.
length() - 1;
i++)
1426 for (
int i= 0;
i < uniFactors.
length();
i++)
1466 CFList* & differentSecondVarLCs,
int lSecondVarLCs,
1474 for (
int i= 1;
i <= LCFFactors.
length() + 1;
i++)
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;
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;
1578 bufFactors= differentSecondVarLCs [
i];
1584 bufBufFactors= bufFactors;
1594 bufSqrfFactors, evalSqrfPartF,
evalPoint);
1597 foundDifferent=
true;
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);
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;
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;
1737 factors=
CFList (oldSqrfPartF/contF);
1746 for (
int i= 0;
i < LCFFactors.
length();
i++)
1749 for (
k= bufSqrfFactors[
i];
k.hasItem();
k++)
1751 int pos=
findItem (bufFactors,
k.getItem().factor());
1753 tmp *=
power (
getItem (interMedResult, pos),
k.getItem().exp());
1763 i.getItem()=
N (
i.getItem());
1768 CFList l= differentSecondVarLCs [
j];
1771 differentSecondVarLCs [
j]=
l;
1779 if (!
result.getFirst().inCoeffDomain())
1786 CFList l= differentSecondVarLCs [
j];
1789 differentSecondVarLCs [
j]=
l;
1809 if (lSecondVarLCs -
level > 0)
1812 int j= lSecondVarLCs+2;
1815 for (
i= evaluation2;
i.hasItem();
i++,
j--)
1820 i.getItem()= evaluation2.
getLast();
1831 delete [] bufSqrfFactors;
1847 for (
CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
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];
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--)
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;
1959 for (
int i=
A.level();
i > 2;
i--)
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;
2013 for (; iter1.
hasItem(); iter1++, iter2++)
2016 if (!g2.inCoeffDomain())
2019 l2.
append (iter2.getItem());
2035 CFList uniFactorsOfFactors1;
2053 uniFactorsOfFactors1.
append (tmp);
2062 while (!uniFactorsOfFactors1.
isEmpty())
2064 tmp= uniFactorsOfFactors1.
getFirst();
2108 int *
v=
new int [
T.length()];
2109 for (
int i= 0;
i <
T.length();
i++)
2111 bool nosubset=
false;
2113 TT=
copy (factors1);
2114 int recombinations= 0;
2115 while (
T.length() >= 2*
s &&
s <= thres)
2117 while (nosubset ==
false)
2119 if (
T.length() ==
s)
2129 if (nosubset)
break;
2139 if (nosubset)
break;
2143 if (
T.length() < 2*
s ||
T.length() ==
s)
2152 for (
int i= 0;
i <
T.length();
i++)
2158 if (
T.length() < 2*
s)
2178 for (
int j= 0;
j <
A.level() - 2;
j++)
2196 if (factors.
length() == 1)
2210 for (
int i=
A.max();
i >=
A.min();
i--)
2221 for (
int j= 0;
j <
A.level() - 2;
j++)
2245 int pos,
index, checklength;
2246 bool leaveLoop=
false;
2248 for (
int j= 0;
j < AevalLength;
j++)
2277 checklength= biFactors.
length();
2279 if (checklength > biFactors.
length())
2328 bool leaveLoop=
false;
2329 for (
int j= 0;
j <
A.level() - 2;
j++)
2373 for (
int i= n - 1;
i > 2;
i--,
iter++)
2375 for (
j=
l;
j.hasItem();
j++)
2386 for (
int i= 0;
i < n-2;
i++)
2388 ii= normalizeFactor;
2389 for (
j= LCs [
i];
j.hasItem();
j++, ii++)
2426 int *
v=
new int [
T.length()];
2427 for (
int i= 0;
i <
T.length();
i++)
2429 bool noSubset=
false;
2433 bool trueFactor=
false;
2434 while (
T.length() >= 2*
s)
2436 while (noSubset ==
false)
2438 if (
T.length() ==
s)
2455 if (noSubset)
break;
2487 if (
T.length() < 2*
s ||
T.length() ==
s)
2498 if (noSubset)
break;
2503 if (
T.length() < 2*
s ||
T.length() ==
s)
2511 for (
int i= 0;
i <
T.length();
i++)
2515 if (
T.length() < 2*
s)
2528 CFList*& oldAeval,
int lengthAeval2,
2546 for (
i= 0;
i < lengthAeval2;
i++)
2548 if (oldAeval[
i].isEmpty())
2553 oldAeval[
i]= biFactors;
2556 for (
int ii= 0; ii < tmp.
size(); ii++)
2560 for (
int ii= 0; ii < tmp.
size(); ii++)
2567 for (
int j= 0;
j <
tmp2.size();
j++)
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())
2614 for (
int i= 0;
i < lengthAeval;
i++)
2616 if (oldAeval[
i].isEmpty())
2628 for (
int i=1;
i <= tmp.
level();
i++)
2644 tmp /=
myGetVars (ii.getItem().factor());
2647 if (multi == ii.getItem().exp())
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))
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);
2776 foundTrueMultiplier=
true;
2778 for (iter2= leadingCoeffs; iter2.
hasItem(); iter2++, index2++)
2780 if (index2 ==
index)
2782 iter2.
getItem() /= LCmultiplier;
2795 int lengthAeval,
bool& foundMultiplier)
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;
2856 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.
hasItem();
2859 if (index2 ==
index)
2862 foundMultiplier=
true;
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)
2947 if (
buf.getFirst().inCoeffDomain())
2964 if (
A.inCoeffDomain())
2968 if (
i.getItem().inCoeffDomain())
2972 lcmCont /=
i.getItem();
2982 return contentAFactors;
2992 if (
A.isUnivariate ())
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++)
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())
3142 "time for bivariate factorization: ");
3145 if (bufBiFactors.
length() == 1)
3157 delete [] bufAeval2;
3166 biFactors= bufBiFactors;
3168 for (
int j= 0;
j < lengthAeval2;
j++)
3169 Aeval2 [
j]= bufAeval2 [
j];
3170 differentSecondVar= counter;
3176 counter > differentSecondVar)
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: ");
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));
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;
3342 CFList oldFactors= factors;
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,
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,
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;
3490 for (
int i= 0;
i < lengthAeval2-1;
i++)
3495 for (
int i=
A.level() - 4;
i > -1;
i--)
3497 if (
i + 1 == lengthAeval2-1)
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++)
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: ");
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;
3560 for (;
i.hasItem();
i++)
3569 for (;
i.hasItem();
i++)
3571 LCA=
LC (
i.getItem(), 1);
3572 extgcd (LCA, yToLift, LCA, dummy);
3573 i.getItem()=
mod (
i.getItem()*LCA, yToLift);
3576 liftBoundsLength= F.
level() - 1;
3581 CFList earlyFactors, liftedFactors;
3584 (
A, MOD, liftBounds, earlySuccess, earlyFactors,
3587 "time for hensel lifting over Fq: ");
3594 "time for factor recombination: ");
3601 "time for factor recombination: ");
3605 factors=
Union (factors, earlyFactors);
3613 if (
i.getItem().level() < kk)
3615 i.getItem()=
i.getItem() (
Variable (kk) -
j.getItem(), kk);
3627 swap (factors, swapLevel, swapLevel2,
x);
3628 append (factors, contentAFactors);
3633 delete[] liftBounds;
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");
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;
Rational pow(const Rational &a, int e)
Conversion to and from NTL.
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 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
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.
int getGFDegree() const
getter
bool isInExtension() const
getter
CanonicalForm getGamma() const
getter
CanonicalForm getDelta() const
getter
char getGFName() const
getter
Variable getAlpha() const
getter
Variable getBeta() const
getter
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
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
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
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...
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)
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.
const ExtensionInfo & info
< [in] sqrfree poly
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 rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
void prune(Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
INST_VAR CanonicalForm gf_mipo
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
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)
bool delta(X x, Y y, D d)
const signed long ceil(const ampf< Precision > &x)
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)