47#include "flint/nmod_poly_factor.h"
48#include "flint/fq_nmod_poly_factor.h"
67 else if (L.length() == 1)
68 return mod (L.getFirst()(0, 1) ,
M);
69 else if (L.length() == 2)
70 return mod (
mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1),
b),
M);
76 CanonicalForm buf1, buf2;
77 for (int j= 1; j <= l; j++, i++)
78 tmp1.append (i.getItem());
79 tmp2= Difference (L, tmp1);
80 buf1= prodMod0 (tmp1, M, b);
81 buf2= prodMod0 (tmp2, M, b);
82 return mod (mulNTL (buf1,buf2, b), M);
86#if defined(HAVE_NTL) || defined(HAVE_FLINT)
99 if (
alpha.level() != 1)
142 if (
find (list, random))
continue;
146 if (!
find (list, random))
152 if (!
find (list, random))
156 }
while (
find (list, random));
161#if defined(HAVE_NTL) || defined(HAVE_FLINT)
166 if (
A.inCoeffDomain())
169 "univariate polynomial expected or constant expected");
185#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
186 nmod_poly_t FLINTmipo, leadingCoeff;
188 fq_nmod_poly_t FLINTA;
189 fq_nmod_poly_factor_t FLINTFactorsA;
197 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
199 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
202 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
207 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
219 zz_pE::init (NTLMipo);
222 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
223 zz_pE multi= to_zz_pE (1);
232 GF2E::init (NTLMipo);
235 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
236 GF2E multi= to_GF2E (1);
244 buf=
i.getItem().factor();
250 else if (
alpha.level() != 1)
258#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
259 nmod_poly_t FLINTmipo, leadingCoeff;
261 fq_nmod_poly_t FLINTA;
262 fq_nmod_poly_factor_t FLINTFactorsA;
270 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
272 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
275 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
280 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
292 zz_pE::init (NTLMipo);
295 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
296 zz_pE multi= to_zz_pE (1);
305 GF2E::init (NTLMipo);
308 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
309 GF2E multi= to_GF2E (1);
324 nmod_poly_factor_t
result;
325 nmod_poly_factor_init (
result);
326 mp_limb_t leadingCoeff= nmod_poly_factor (
result, FLINTA);
330 nmod_poly_factor_clear (
result);
347 vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
348 zz_p multi= to_zz_p (1);
355 vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
356 GF2 multi= to_GF2 (1);
364 uniFactors.
append (
i.getItem().factor());
369#if defined(HAVE_NTL) || defined(HAVE_FLINT)
378 if (factors.
length() == 0)
390 int k=
info.getGFDegree();
404 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, M) == F " <<
407 if (!
k &&
beta.level() != 1)
419 int *
v=
new int [
T.length()];
420 for (
int i= 0;
i <
T.length();
i++)
428 bool nosubset=
false;
430 bool trueFactor=
false;
433 while (
T.length() >= 2*
s &&
s <= thres)
435 while (nosubset ==
false)
463 if (!degs.
find (subsetDeg))
481 if (!
k &&
beta.level() == 1)
508 buf0=
buf (0,
x)*LCBuf;
514 if (
T.length() < 2*
s ||
T.length() ==
s ||
544 if (
T.length() < 2*
s ||
T.length() ==
s)
562 for (
int i= 0;
i <
T.length();
i++)
566 if (
T.length() < 2*
s)
595 if (factors.
length() == 0)
611 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
614 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
628 int *
v=
new int [
T.length()];
629 for (
int i= 0;
i <
T.length();
i++)
631 bool nosubset=
false;
646 while (
T.length() >= 2*
s &&
s <= thres)
648 while (nosubset ==
false)
676 if (!degs.
find (subsetDeg))
710 if (!
Lc (
g).inBaseDomain())
727 denom /=
gcd (denom, denQuot);
743 if (
T.length() < 2*
s ||
T.length() ==
s ||
770 if (
T.length() < 2*
s ||
T.length() ==
s)
786 for (
int i= 0;
i <
T.length();
i++)
791 if (
T.length() < 2*
s)
808#if defined(HAVE_NTL) || defined(HAVE_FLINT)
813 if (
alpha.level() == 1 &&
beta.level() == 1 &&
k == 1)
818 else if (
alpha.level() != 1 &&
beta.level() == 1 &&
k == 1)
823 else if (
alpha.level() != 1 &&
beta.level() == 1 &&
k != 1)
828 else if (
alpha.level() != 1 &&
beta.level() != 1 &&
k != 1)
833 #if defined(HAVE_FLINT)
834 nmod_poly_t Irredpoly;
836 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom,
i*
m+1);
838 #elif defined(HAVE_NTL)
845 BuildIrred (NTLIrredpoly,
i*
m);
856 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
886 if (!bufDegs1.
find (
degree (
i.getItem(), 1)) || factorsFoundIndex[
l] == 1)
912 if (!
Lc (
g).inBaseDomain())
923 factorsFoundIndex[
l]= 1;
949 if (!
buf.inCoeffDomain())
963 adaptedLiftBound= d + 1;
964 if (adaptedLiftBound < deg)
975 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
981 factorsFoundIndex, degs, success, deg,
eval,
b,
den);
986 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
995 int k=
info.getGFDegree();
1003 adaptedLiftBound= 0;
1004 bool trueFactor=
false;
1008 if (!
k &&
beta.level() != 1)
1013 if (!bufDegs1.
find (
degree (
i.getItem(), 1)) || factorsFoundIndex[
l] == 1)
1029 factorsFoundIndex[
l]= 1;
1041 factorsFoundIndex[
l]= 1;
1060 if (!
buf.inCoeffDomain())
1073 adaptedLiftBound= d + 1;
1074 if (adaptedLiftBound < deg)
1093 for (
int i= 0;
i < sizeOfRightSide;
i++)
1099 if (
i.exp() < degreeLC)
1106 ASSERT (
j > 1,
"j > 1 expected" );
1108 int*
result =
new int [
j - 1];
1109 sizeOfOutput=
j - 1;
1125 int sizeOfNewtonPoly;
1127 int sizeOfRightSide;
1128 int * rightSide=
getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1131 delete [] rightSide;
1132 for (
int i= 0;
i < sizeOfNewtonPoly;
i++)
1133 delete [] newtonPolyg[
i];
1134 delete [] newtonPolyg;
1145 if (factorsFoundIndex[
i] == 1)
1153#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1164 bool extension=
info.isInExtension();
1173 CFList bufUniFactors= uniFactors;
1176 if (!
Lc (
A).inBaseDomain())
1191 bool mipoHasDen=
false;
1194 if (
alpha.level() == 1)
1196 lcA0=
lc (
A (0, 2));
1197 A *=
b.inverse (lcA0);
1200 i.getItem()=
b (
i.getItem()*
b.inverse (
lc (
i.getItem())));
1213 i.getItem()=
b (
i.getItem()*
b.inverse (
lc (
i.getItem())));
1218 earlySuccess=
false;
1219 int newLiftBound= 0;
1221 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
1223 int * factorsFoundIndex=
new int [uniFactors.
length()];
1224 for (
int i= 0;
i < uniFactors.
length();
i++)
1225 factorsFoundIndex [
i]= 0;
1229 if (smallFactorDeg >= liftBound ||
degree (
A,
y) <= 4)
1231 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1233 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1241 bufBufUniFactors= bufUniFactors;
1252 factorsFoundIndex, degs, earlySuccess,
1256 factorsFoundIndex, degs, earlySuccess,
1261 factorsFoundIndex, degs, earlySuccess,
info,
1262 eval, smallFactorDeg);
1263 if (degs.
getLength() > 1 && !earlySuccess &&
1264 smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1266 if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1270 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant,
M,
b);
1273 bufBufUniFactors= bufUniFactors;
1281 factorsFoundIndex, degs, earlySuccess,
1282 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1285 factorsFoundIndex, degs, earlySuccess,
1286 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1290 factorsFoundIndex, degs, earlySuccess,
info,
1291 eval, liftPre[sizeOfLiftPre-1] + 1);
1294 else if (earlySuccess)
1295 liftBound= newLiftBound;
1297 int i= sizeOfLiftPre - 1;
1298 while (degs.
getLength() > 1 && !earlySuccess &&
i - 1 >= 0)
1300 if (newLiftBound >= liftPre[
i] + 1)
1304 liftPre[
i-1] + 1, Pi, diophant,
M,
b);
1307 bufBufUniFactors= bufUniFactors;
1315 factorsFoundIndex, degs, earlySuccess,
1319 factorsFoundIndex, degs, earlySuccess,
1324 factorsFoundIndex, degs, earlySuccess,
info,
1325 eval, liftPre[
i-1] + 1);
1329 liftBound= newLiftBound;
1335 liftBound= newLiftBound;
1340 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1348 bufBufUniFactors= bufUniFactors;
1358 factorsFoundIndex, degs, earlySuccess,
1362 factorsFoundIndex, degs, earlySuccess,
1367 factorsFoundIndex, degs, earlySuccess,
info,
1368 eval, smallFactorDeg);
1370 while ((
degree (
A,
y)/4)*
i + 4 <= smallFactorDeg)
1373 if (degs.
getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1377 dummy, Pi, diophant,
M,
b);
1380 bufBufUniFactors= bufUniFactors;
1388 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1392 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1397 factorsFoundIndex, degs, earlySuccess,
info,
1400 while (degs.
getLength() > 1 && !earlySuccess &&
i < 4)
1402 if (newLiftBound >= dummy)
1407 dummy, Pi, diophant,
M,
b);
1410 bufBufUniFactors= bufUniFactors;
1418 factorsFoundIndex, degs, earlySuccess, dummy,
1422 factorsFoundIndex, degs, earlySuccess, dummy,
1427 factorsFoundIndex, degs, earlySuccess,
info,
1432 liftBound= newLiftBound;
1438 liftBound= newLiftBound;
1449 delete [] factorsFoundIndex;
1452 return bufUniFactors;
1474 for (
i = 1;
i <=
M.NumRows();
i++)
1477 for (
j = 1;
j <=
M.NumCols();
j++)
1493 for (
i = 1;
i <= nmod_mat_nrows(
M);
i++)
1496 for (
j = 1;
j <= nmod_mat_ncols (
M);
j++)
1498 if (!(nmod_mat_entry (
M,
i-1,
j-1)==0))
1512 for (
i = 1;
i <=
M.NumRows();
i++)
1515 for (
j = 1;
j <=
M.NumCols();
j++)
1531 bool nonZeroOne=
false;
1532 int *
result=
new int [
M.NumCols()];
1533 for (
i = 1;
i <=
M.NumCols();
i++)
1535 for (
j = 1;
j <=
M.NumRows();
j++)
1557 bool nonZeroOne=
false;
1558 int *
result=
new int [nmod_mat_ncols (
M)];
1559 for (
i = 0;
i < nmod_mat_ncols (
M);
i++)
1561 for (
j = 0;
j < nmod_mat_nrows (
M);
j++)
1563 if (!((nmod_mat_entry (
M,
j,
i) == 1) || (nmod_mat_entry (
M,
j,
i) == 0)))
1583 bool nonZeroOne=
false;
1584 int *
result=
new int [
M.NumCols()];
1585 for (
i = 1;
i <=
M.NumCols();
i++)
1587 for (
j = 1;
j <=
M.NumRows();
j++)
1608 factors,
const int liftBound,
int& factorsFound,
int*&
1617 if (factors.
length() == 2)
1629 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1640 for (
long i= 1;
i <=
N.NumCols();
i++)
1642 if (factorsFoundIndex [
i - 1] == 1)
1658 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1669 factorsFoundIndex[
i - 1]= 1;
1677 if (factorsFound + 1 ==
N.NumCols())
1679 reconstructedFactors.
append (bufF);
1684 if (reconstructedFactors.
length() != 0)
1692 factors,
const int liftBound,
int& factorsFound,
int*&
1701 if (factors.
length() == 2)
1713 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1724 for (
long i= 1;
i <=
N.NumCols();
i++)
1726 if (factorsFoundIndex [
i - 1] == 1)
1742 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1753 factorsFoundIndex[
i - 1]= 1;
1761 if (factorsFound + 1 ==
N.NumCols())
1763 reconstructedFactors.
append (bufF);
1768 if (reconstructedFactors.
length() != 0)
1776 factors,
const int liftBound,
int& factorsFound,
int*&
1785 if (factors.
length() == 2)
1797 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1808 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
1810 if (factorsFoundIndex [
i] == 1)
1826 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
1828 if (!(nmod_mat_entry (
N,
j,
i) == 0))
1837 factorsFoundIndex[
i]= 1;
1845 if (factorsFound + 1 == nmod_mat_ncols (
N))
1848 reconstructedFactors.
append (bufF);
1852 if (reconstructedFactors.
length() != 0)
1869 CFList bufFactors= factors;
1871 for (
long i= 1;
i <=
N.NumCols();
i++)
1873 if (zeroOneVecs [
i - 1] == 0)
1877 factorsConsidered=
CFList();
1878 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1893 bufFactors=
Difference (bufFactors, factorsConsidered);
1898 factors= bufFactors;
1903 factors= bufFactors;
1911 int precision,
const mat_zz_pE&
N
1920 CFList bufFactors= factors;
1921 CFList factorsConsidered;
1923 for (
long i= 1;
i <=
N.NumCols();
i++)
1925 if (zeroOneVecs [
i - 1] == 0)
1929 factorsConsidered=
CFList();
1930 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1946 bufFactors=
Difference (bufFactors, factorsConsidered);
1951 factors= bufFactors;
1956 factors= bufFactors;
1972 int k=
info.getGFDegree();
1978 CFList bufFactors= factors;
1979 CFList factorsConsidered;
1982 for (
long i= 1;
i <=
N.NumCols();
i++)
1984 if (zeroOneVecs [
i - 1] == 0)
1988 factorsConsidered=
CFList();
1989 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2010 bufFactors=
Difference (bufFactors, factorsConsidered);
2025 bufFactors=
Difference (bufFactors, factorsConsidered);
2032 factors= bufFactors;
2037 factors= bufFactors;
2053 int k=
info.getGFDegree();
2059 CFList bufFactors= factors;
2060 CFList factorsConsidered;
2063 for (
long i= 0;
i < nmod_mat_ncols(
N);
i++)
2065 if (zeroOneVecs [
i] == 0)
2069 factorsConsidered=
CFList();
2070 for (
long j= 0;
j < nmod_mat_nrows(
N);
j++,
iter++)
2072 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2091 bufFactors=
Difference (bufFactors, factorsConsidered);
2106 bufFactors=
Difference (bufFactors, factorsConsidered);
2113 factors= bufFactors;
2118 factors= bufFactors;
2134 CFList bufFactors= factors;
2135 CFList factorsConsidered;
2137 for (
long i= 1;
i <=
N.NumCols();
i++)
2139 if (zeroOneVecs [
i - 1] == 0)
2143 factorsConsidered=
CFList();
2144 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2159 bufFactors=
Difference (bufFactors, factorsConsidered);
2164 factors= bufFactors;
2169 factors= bufFactors;
2185 CFList bufFactors= factors;
2186 CFList factorsConsidered;
2188 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2190 if (zeroOneVecs [
i] == 0)
2194 factorsConsidered=
CFList();
2195 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2197 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2210 bufFactors=
Difference (bufFactors, factorsConsidered);
2215 factors= bufFactors;
2220 factors= bufFactors;
2228 CFList& factors,
const int liftBound,
int& factorsFound,
2229 int*& factorsFoundIndex, mat_zz_p&
N,
bool beenInThres,
2237 int k=
info.getGFDegree();
2242 if (factors.
length() == 2)
2252 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2284 for (
long i= 1;
i <=
N.NumCols();
i++)
2286 if (factorsFoundIndex [
i - 1] == 1)
2302 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2318 factorsFoundIndex[
i - 1]= 1;
2333 factorsFoundIndex[
i - 1]= 1;
2344 if (factorsFound + 1 ==
N.NumCols())
2348 reconstructedFactors.
append (tmp);
2358 CFList& factors,
const int liftBound,
int& factorsFound,
2359 int*& factorsFoundIndex, nmod_mat_t
N,
bool beenInThres,
2367 int k=
info.getGFDegree();
2372 if (factors.
length() == 2)
2382 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2414 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2416 if (factorsFoundIndex [
i] == 1)
2432 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2434 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2448 factorsFoundIndex[
i]= 1;
2463 factorsFoundIndex[
i]= 1;
2474 if (factorsFound + 1 == nmod_mat_nrows (
N))
2478 reconstructedFactors.
append (tmp);
2489 start,
int liftBound,
int minBound,
CFList& factors,
2496 bool wasInBounds=
false;
2497 bool hitBound=
false;
2498 int l= (minBound+1)*2;
2501 bool reduced=
false;
2502 mat_zz_p NTLK, *NTLC;
2508 while (
l <= liftBound)
2524 "time to lift in compute lattice: ");
2532 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2541 "time to compute logarithmic derivative: ");
2543 for (
int i= 0;
i < sizeBounds;
i++)
2545 if (bounds [
i] + 1 <=
l/2)
2548 int k=
tmin (bounds [
i] + 1,
l/2);
2550 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2552 if (
A[ii].
size() - 1 >=
i)
2560 transpose (NTLK, NTLK);
2561 kernel (NTLK, NTLK);
2562 transpose (NTLK, NTLK);
2566 if (NTLN.NumCols() == 1)
2614 start,
int liftBound,
int minBound,
CFList& factors,
2621 bool wasInBounds=
false;
2622 bool hitBound=
false;
2623 int l= (minBound+1)*2;
2626 bool reduced=
false;
2628 nmod_mat_t FLINTK, FLINTC, null;
2634 while (
l <= liftBound)
2650 "time to lift in compute lattice: ");
2658 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2667 "time to compute logarithmic derivative: ");
2669 for (
int i= 0;
i < sizeBounds;
i++)
2671 if (bounds [
i] + 1 <=
l/2)
2674 int k=
tmin (bounds [
i] + 1,
l/2);
2676 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2678 if (
A[ii].
size() - 1 >=
i)
2686 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2688 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2689 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2691 rank= nmod_mat_nullspace (null, FLINTK);
2692 nmod_mat_clear (FLINTK);
2693 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2694 nmod_mat_clear (FLINTC);
2695 nmod_mat_init_set (FLINTC, FLINTN);
2696 nmod_mat_clear (FLINTN);
2697 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2699 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
2701 nmod_mat_clear (FLINTC);
2702 nmod_mat_window_clear (FLINTK);
2703 nmod_mat_clear (null);
2704 if (nmod_mat_ncols (FLINTN) == 1)
2709 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
2753 int liftBound,
int minBound,
int start,
CFList&
2754 factors, mat_zz_p& NTLN,
CFList& diophant,
2763 bool wasInBounds=
false;
2764 bool hitBound=
false;
2775 int l= ((minBound+1)/degMipo+1)*2;
2780 bool reduced=
false;
2787 mat_zz_p* NTLMat, *NTLC, NTLK;
2789 while (
l <= liftBound)
2805 "time to lift in compute lattice: ");
2814 for (
int i= 0;
i <
l*degMipo;
i++)
2817 imBasis= imBasis (
power (
y, degMipo),
y);
2818 imBasis= imBasis (
y, gamma);
2825 *NTLMat= inv (*NTLMat);
2835 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2844 "time to compute logarithmic derivative: ");
2846 for (
int i= 0;
i < sizeBounds;
i++)
2848 if (bounds [
i] + 1 <= (
l/2)*degMipo)
2851 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
2854 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2856 if (
A[ii].
size() - 1 >=
i)
2864 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2873 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2889 transpose (NTLK, NTLK);
2890 kernel (NTLK, NTLK);
2891 transpose (NTLK, NTLK);
2898 if (NTLN.NumCols() == 1)
2913 if (NTLN.NumCols() == 1)
2952 int liftBound,
int minBound,
int start,
CFList&
2953 factors, nmod_mat_t FLINTN,
CFList& diophant,
2962 bool wasInBounds=
false;
2963 bool hitBound=
false;
2974 int l= ((minBound+1)/degMipo+1)*2;
2979 bool reduced=
false;
2987 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
2989 while (
l <= liftBound)
3011 for (
int i= 0;
i <
l*degMipo;
i++)
3014 imBasis= imBasis (
power (
y, degMipo),
y);
3015 imBasis= imBasis (
y, gamma);
3022 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3024 nmod_mat_inv (FLINTMatInv, FLINTMat);
3033 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3042 for (
int i= 0;
i < sizeBounds;
i++)
3044 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3047 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3050 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3052 if (
A[ii].
size() - 1 >=
i)
3060 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3069 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3084 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3086 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3087 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3089 rank= nmod_mat_nullspace (null, FLINTK);
3090 nmod_mat_clear (FLINTK);
3091 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3092 nmod_mat_clear (FLINTC);
3093 nmod_mat_init_set (FLINTC, FLINTN);
3094 nmod_mat_clear (FLINTN);
3095 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3097 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3099 nmod_mat_clear (FLINTC);
3100 nmod_mat_window_clear (FLINTK);
3101 nmod_mat_clear (null);
3106 if (nmod_mat_ncols (FLINTN) == 1)
3119 nmod_mat_clear (FLINTMat);
3120 nmod_mat_clear (FLINTMatInv);
3122 if (nmod_mat_ncols (FLINTN) == 1)
3161 int start,
int liftBound,
int minBound,
CFList& factors,
3168 bool wasInBounds=
false;
3169 bool hitBound=
false;
3170 int l= (minBound+1)*2;
3173 bool reduced=
false;
3175 mat_zz_pE* NTLC, NTLK;
3180 while (
l <= liftBound)
3196 "time to lift in compute lattice: ");
3204 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3206 if (
l == (minBound+1)*2)
3218 "time to compute logarithmic derivative: ");
3220 for (
int i= 0;
i < sizeBounds;
i++)
3222 if (bounds [
i] + 1 <=
l/2)
3225 int k=
tmin (bounds [
i] + 1,
l/2);
3227 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3230 if (
A[ii].
size() - 1 >=
i)
3239 transpose (NTLK, NTLK);
3240 kernel (NTLK, NTLK);
3241 transpose (NTLK, NTLK);
3245 if (NTLN.NumCols() == 1)
3258 if (NTLN.NumCols() == 1)
3296 int start,
int liftBound,
int minBound,
CFList&
3297 factors, nmod_mat_t FLINTN,
CFList& diophant,
3304 int start,
int liftBound,
int minBound,
CFList&
3313 bool wasInBounds=
false;
3314 int l= (minBound+1)*2;
3317 bool hitBound=
false;
3319 bool reduced=
false;
3325 nmod_mat_t FLINTC, FLINTK, null;
3327 mat_zz_p* NTLC, NTLK;
3331 while (
l <= liftBound)
3347 "time to lift in compute lattice: ");
3355 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3357 if (
l == (minBound+1)*2)
3369 "time to compute logarithmic derivative: ");
3371 for (
int i= 0;
i < sizeBounds;
i++)
3373 if (bounds [
i] + 1 <=
l/2)
3376 int k=
tmin (bounds [
i] + 1,
l/2);
3378 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3380 if (
A[ii].
size() - 1 >=
i)
3389 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3391 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3392 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3394 rank= nmod_mat_nullspace (null, FLINTK);
3395 nmod_mat_clear (FLINTK);
3396 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3397 nmod_mat_clear (FLINTC);
3398 nmod_mat_init_set (FLINTC, FLINTN);
3399 nmod_mat_clear (FLINTN);
3400 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3402 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3404 nmod_mat_clear (FLINTC);
3405 nmod_mat_window_clear (FLINTK);
3406 nmod_mat_clear (null);
3410 transpose (NTLK, NTLK);
3411 kernel (NTLK, NTLK);
3412 transpose (NTLK, NTLK);
3418 if (nmod_mat_nrows (FLINTN) == 1)
3420 if (NTLN.NumCols() == 1)
3427 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
3439 if (nmod_mat_ncols (FLINTN) == 1)
3441 if (NTLN.NumCols() == 1)
3479 int oldNumCols,
int oldL,
int precision,
3499 for (
long i=factors.
length()-1;
i >= 0;
i--)
3500 nmod_mat_entry (FLINTN,
i,
i)= 1;
3503 ident (NTLN, factors.
length());
3505 int minBound= bounds[0];
3506 for (
int i= 1;
i < d;
i++)
3509 minBound=
tmin (minBound, bounds[
i]);
3511 int l=
tmax (2*(minBound + 1), oldL);
3514 bool useOldQs=
false;
3515 bool hitBound=
false;
3521 nmod_mat_t FLINTC, FLINTK, null;
3523 mat_zz_p* NTLC, NTLK;
3526 while (
l <= precision)
3532 for (
int i= 0;
i < factors.
length();
i++,
j++)
3539 for (
int i= 0;
i < factors.
length();
i++,
j++)
3543 for (
int i= 0;
i < d;
i++)
3545 if (bounds [
i] + 1 <=
l/2)
3547 int k=
tmin (bounds [
i] + 1,
l/2);
3549 for (
int ii= 0; ii < factors.
length(); ii++)
3551 if (
A[ii].
size() - 1 >=
i)
3559 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3561 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3562 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3564 rank= nmod_mat_nullspace (null, FLINTK);
3565 nmod_mat_clear (FLINTK);
3566 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3567 nmod_mat_clear (FLINTC);
3568 nmod_mat_init_set (FLINTC, FLINTN);
3569 nmod_mat_clear (FLINTN);
3570 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3572 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3574 nmod_mat_clear (FLINTC);
3575 nmod_mat_window_clear (FLINTK);
3576 nmod_mat_clear (null);
3580 transpose (NTLK, NTLK);
3581 kernel (NTLK, NTLK);
3582 transpose (NTLK, NTLK);
3587 if (nmod_mat_ncols (FLINTN) == 1)
3589 nmod_mat_clear (FLINTN);
3591 if (NTLN.NumCols() == 1)
3604 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3608 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
3609 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
3611 if (NTLN.NumCols() < oldNumCols - factorsFound)
3615 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3616 for (
long i= 0;
i < NTLN.NumCols();
i++)
3618 factorsFoundIndex[
i]= 0;
3619 int factorsFound2= 0;
3624 factorsFoundIndex, FLINTN,
eval,
false
3626 if (
result.length() == nmod_mat_ncols (FLINTN))
3628 nmod_mat_clear (FLINTN);
3631 factorsFoundIndex, NTLN,
eval,
false
3633 if (
result.length() == NTLN.NumCols())
3636 delete [] factorsFoundIndex;
3642 delete [] factorsFoundIndex;
3644 else if (
l == precision)
3650 nmod_mat_clear (FLINTN);
3677 nmod_mat_clear (FLINTN);
3688 int oldNumCols,
int oldL,
const Variable&,
3706 ident (NTLN, factors.
length());
3707 int minBound= bounds[0];
3708 for (
int i= 1;
i < d;
i++)
3711 minBound=
tmin (minBound, bounds[
i]);
3713 int l=
tmax (2*(minBound + 1), oldL);
3716 bool useOldQs=
false;
3717 bool hitBound=
false;
3720 mat_zz_pE* NTLC, NTLK;
3723 while (
l <= precision)
3729 for (
int i= 0;
i < factors.
length();
i++,
j++)
3736 for (
int i= 0;
i < factors.
length();
i++,
j++)
3740 for (
int i= 0;
i < d;
i++)
3742 if (bounds [
i] + 1 <=
l/2)
3744 int k=
tmin (bounds [
i] + 1,
l/2);
3746 for (
int ii= 0; ii < factors.
length(); ii++)
3748 if (
A[ii].
size() - 1 >=
i)
3756 transpose (NTLK, NTLK);
3757 kernel (NTLK, NTLK);
3758 transpose (NTLK, NTLK);
3761 if (NTLN.NumCols() == 1)
3772 if (NTLN.NumCols() < oldNumCols - factorsFound)
3776 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3777 for (
long i= 0;
i < NTLN.NumCols();
i++)
3778 factorsFoundIndex[
i]= 0;
3779 int factorsFound2= 0;
3783 factorsFoundIndex, NTLN,
eval,
false);
3784 if (
result.length() == NTLN.NumCols())
3786 delete [] factorsFoundIndex;
3792 delete [] factorsFoundIndex;
3794 else if (
l == precision)
3857 for (
long i=factors.
length()-1;
i >= 0;
i--)
3858 nmod_mat_entry (FLINTN,
i,
i)= 1;
3866 ident (NTLN, factors.
length());
3868 int minBound= bounds[0];
3869 for (
int i= 1;
i < d;
i++)
3872 minBound=
tmin (minBound, bounds[
i]);
3874 int l=
tmax (oldL, 2*((minBound+1)/degMipo+1));
3877 bool useOldQs=
false;
3878 bool hitBound=
false;
3889 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
3891 mat_zz_p* NTLMat,*NTLC, NTLK;
3894 while (
l <= precision)
3901 for (
int i= 0;
i <
l*degMipo;
i++)
3904 imBasis= imBasis (
power (
y, degMipo),
y);
3905 imBasis= imBasis (
y, gamma);
3913 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3915 nmod_mat_inv (FLINTMatInv, FLINTMat);
3918 *NTLMat= inv (*NTLMat);
3927 for (
int i= 0;
i < factors.
length();
i++,
j++)
3934 for (
int i= 0;
i < factors.
length();
i++,
j++)
3938 for (
int i= 0;
i < d;
i++)
3940 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3942 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3944 for (
int ii= 0; ii < factors.
length(); ii++)
3946 if (
A[ii].
size() - 1 >=
i)
3954 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3967 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3987 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3989 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3990 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3992 rank= nmod_mat_nullspace (null, FLINTK);
3993 nmod_mat_clear (FLINTK);
3994 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3995 nmod_mat_clear (FLINTC);
3996 nmod_mat_init_set (FLINTC, FLINTN);
3997 nmod_mat_clear (FLINTN);
3998 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4000 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4002 nmod_mat_clear (FLINTC);
4003 nmod_mat_window_clear (FLINTK);
4004 nmod_mat_clear (null);
4008 transpose (NTLK, NTLK);
4009 kernel (NTLK, NTLK);
4010 transpose (NTLK, NTLK);
4019 if (nmod_mat_ncols (FLINTN) == 1)
4021 nmod_mat_clear (FLINTMat);
4022 nmod_mat_clear (FLINTMatInv);
4023 nmod_mat_clear (FLINTN);
4025 if (NTLN.NumCols() == 1)
4042 nmod_mat_clear (FLINTMat);
4043 nmod_mat_clear (FLINTMatInv);
4049 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4053 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4054 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4056 if (NTLN.NumCols() < oldNumCols - factorsFound)
4060 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4061 for (
long i= 0;
i < NTLN.NumCols();
i++)
4063 factorsFoundIndex[
i]= 0;
4064 int factorsFound2= 0;
4071 if (
result.length() == nmod_mat_ncols (FLINTN))
4073 nmod_mat_clear (FLINTN);
4078 if (
result.length() == NTLN.NumCols())
4081 delete [] factorsFoundIndex;
4087 delete [] factorsFoundIndex;
4089 else if (
l == precision)
4097 nmod_mat_clear (FLINTN);
4127 nmod_mat_clear (FLINTN);
4156 zz_pE::init (NTLMipo);
4158 ident (NTLN, factors.
length());
4159 int minBound= bounds[0];
4160 for (
int i= 1;
i < d;
i++)
4163 minBound=
tmin (minBound, bounds[
i]);
4165 int l=
tmin (2*(minBound + 1), precision);
4168 bool useOldQs=
false;
4169 bool hitBound=
false;
4173 mat_zz_pE* NTLC, NTLK;
4176 while (
l <= precision)
4182 for (
int i= 0;
i < factors.
length();
i++,
j++)
4187 for (
int i= 0;
i < factors.
length();
i++,
j++)
4191 for (
int i= 0;
i < d;
i++)
4193 if (bounds [
i] + 1 <=
l/2)
4195 int k=
tmin (bounds [
i] + 1,
l/2);
4197 for (
int ii= 0; ii < factors.
length(); ii++)
4199 if (
A[ii].
size() - 1 >=
i)
4207 transpose (NTLK, NTLK);
4208 kernel (NTLK, NTLK);
4209 transpose (NTLK, NTLK);
4213 if (NTLN.NumCols() == 1)
4226 CFList bufFactors= factors;
4230 if (
result.length() != NTLN.NumCols() &&
l != precision)
4231 factors= bufFactors;
4232 if (
result.length() == NTLN.NumCols())
4292 for (
long i=factors.
length()-1;
i >= 0;
i--)
4293 nmod_mat_entry (FLINTN,
i,
i)= 1;
4296 ident (NTLN, factors.
length());
4298 int minBound= bounds[0];
4299 for (
int i= 1;
i < d;
i++)
4302 minBound=
tmin (minBound, bounds[
i]);
4304 int l=
tmax (2*(minBound + 1), oldL);
4307 bool useOldQs=
false;
4308 bool hitBound=
false;
4313 nmod_mat_t FLINTC, FLINTK, null;
4315 mat_zz_p* NTLC, NTLK;
4319 while (
l <= precision)
4325 for (
int i= 0;
i < factors.
length();
i++,
j++)
4332 for (
int i= 0;
i < factors.
length();
i++,
j++)
4336 for (
int i= 0;
i < d;
i++)
4338 if (bounds [
i] + 1 <=
l/2)
4340 int k=
tmin (bounds [
i] + 1,
l/2);
4342 for (
int ii= 0; ii < factors.
length(); ii++)
4344 if (
A[ii].
size() - 1 >=
i)
4352 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4354 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4355 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4357 rank= nmod_mat_nullspace (null, FLINTK);
4358 nmod_mat_clear (FLINTK);
4359 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4360 nmod_mat_clear (FLINTC);
4361 nmod_mat_init_set (FLINTC, FLINTN);
4362 nmod_mat_clear (FLINTN);
4363 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4365 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4367 nmod_mat_clear (FLINTC);
4368 nmod_mat_window_clear (FLINTK);
4369 nmod_mat_clear (null);
4373 transpose (NTLK, NTLK);
4374 kernel (NTLK, NTLK);
4375 transpose (NTLK, NTLK);
4380 if (nmod_mat_ncols (FLINTN) == 1)
4382 nmod_mat_clear (FLINTN);
4384 if (NTLN.NumCols() == 1)
4397 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4401 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4402 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4404 if (NTLN.NumCols() < oldNumCols - factorsFound)
4408 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4409 for (
long i= 0;
i < NTLN.NumCols();
i++)
4411 factorsFoundIndex[
i]= 0;
4412 int factorsFound2= 0;
4417 factorsFoundIndex, FLINTN,
eval,
false
4419 if (
result.length() == nmod_mat_ncols (FLINTN))
4421 nmod_mat_clear (FLINTN);
4424 factorsFoundIndex, NTLN,
eval,
false
4426 if (
result.length() == NTLN.NumCols())
4429 delete [] factorsFoundIndex;
4435 delete [] factorsFoundIndex;
4437 else if (
l == precision)
4443 nmod_mat_clear (FLINTN);
4470 nmod_mat_clear (FLINTN);
4482 l,
int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
4488 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
4496 bool hitBound=
false;
4498 if (nmod_mat_nrows (FLINTN) != factors.
length())
4500 nmod_mat_clear (FLINTN);
4502 for (
long i=factors.
length()-1;
i >= 0;
i--)
4503 nmod_mat_entry (FLINTN,
i,
i)= 1;
4507 if (NTLN.NumRows() != factors.
length())
4509 ident (NTLN, factors.
length());
4513 bool useOldQs=
false;
4519 nmod_mat_t FLINTC, FLINTK, null;
4521 mat_zz_p* NTLC, NTLK;
4532 for (
int i= 0;
i < factors.
length();
i++,
j++)
4539 for (
int i= 0;
i < factors.
length();
i++,
j++)
4544 for (
int i= 0;
i < d;
i++)
4546 if (bounds [
i] + 1 <= oldL/2)
4548 int k=
tmin (bounds [
i] + 1, oldL/2);
4550 for (
int ii= 0; ii < factors.
length(); ii++)
4552 if (
A[ii].
size() - 1 >=
i)
4560 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4562 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4563 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4565 rank= nmod_mat_nullspace (null, FLINTK);
4566 nmod_mat_clear (FLINTK);
4567 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4568 nmod_mat_clear (FLINTC);
4569 nmod_mat_init_set (FLINTC, FLINTN);
4570 nmod_mat_clear (FLINTN);
4571 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4573 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4575 nmod_mat_clear (FLINTC);
4576 nmod_mat_window_clear (FLINTK);
4577 nmod_mat_clear (null);
4581 transpose (NTLK, NTLK);
4582 kernel (NTLK, NTLK);
4583 transpose (NTLK, NTLK);
4588 if (nmod_mat_ncols (FLINTN) == 1)
4590 if (NTLN.NumCols() == 1)
4599 if (nmod_mat_ncols (FLINTN) == 1)
4601 if (NTLN.NumCols() == 1)
4614 bufUniFactors= factors;
4620 delete [] zeroOneVecs;
4624 factors= bufUniFactors;
4651 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_pE& NTLN,
4658 bool hitBound=
false;
4659 bool useOldQs=
false;
4660 if (NTLN.NumRows() != factors.
length())
4661 ident (NTLN, factors.
length());
4665 mat_zz_pE* NTLC, NTLK;
4675 for (
int i= 0;
i < factors.
length();
i++,
j++)
4682 for (
int i= 0;
i < factors.
length();
i++,
j++)
4687 for (
int i= 0;
i < d;
i++)
4689 if (bounds [
i] + 1 <= oldL/2)
4691 int k=
tmin (bounds [
i] + 1, oldL/2);
4693 for (
int ii= 0; ii < factors.
length(); ii++)
4695 if (
A[ii].
size() - 1 >=
i)
4703 transpose (NTLK, NTLK);
4704 kernel (NTLK, NTLK);
4705 transpose (NTLK, NTLK);
4709 if (NTLN.NumCols() == 1)
4716 if (NTLN.NumCols() == 1)
4725 bufUniFactors= factors;
4727 delete [] zeroOneVecs;
4731 factors= bufUniFactors;
4760 int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
const
4767 int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
const
4776 bool hitBound=
false;
4777 bool useOldQs=
false;
4786 nmod_mat_clear (FLINTN);
4788 for (
long i=factors.
length()-1;
i >= 0;
i--)
4789 nmod_mat_entry (FLINTN,
i,
i)= 1;
4791 if (NTLN.NumRows() != factors.
length())
4792 ident (NTLN, factors.
length());
4802 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
4804 mat_zz_p* NTLC, NTLK, *NTLMat;
4813 powX=
power (
y-gamma, oldL);
4814 Mat=
CFMatrix (oldL*degMipo, oldL*degMipo);
4815 for (
int i= 0;
i < oldL*degMipo;
i++)
4818 imBasis= imBasis (
power (
y, degMipo),
y);
4819 imBasis= imBasis (
y, gamma);
4827 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
4829 nmod_mat_inv (FLINTMatInv, FLINTMat);
4832 *NTLMat= inv (*NTLMat);
4841 for (
int i= 0;
i < factors.
length();
i++,
j++)
4847 for (
int i= 0;
i < factors.
length();
i++,
j++)
4852 for (
int i= 0;
i < d;
i++)
4854 if (bounds [
i] + 1 <= oldL/2)
4856 int k=
tmin (bounds [
i] + 1, oldL/2);
4858 for (
int ii= 0; ii < factors.
length(); ii++)
4860 if (
A[ii].
size() - 1 >=
i)
4868 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4881 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4901 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4903 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4904 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4906 rank= nmod_mat_nullspace (null, FLINTK);
4907 nmod_mat_clear (FLINTK);
4908 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4909 nmod_mat_clear (FLINTC);
4910 nmod_mat_init_set (FLINTC, FLINTN);
4911 nmod_mat_clear (FLINTN);
4912 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4914 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4916 nmod_mat_clear (FLINTC);
4917 nmod_mat_window_clear (FLINTK);
4918 nmod_mat_clear (null);
4922 transpose (NTLK, NTLK);
4923 kernel (NTLK, NTLK);
4924 transpose (NTLK, NTLK);
4933 if (nmod_mat_ncols (FLINTN) == 1)
4935 nmod_mat_clear (FLINTMat);
4936 nmod_mat_clear (FLINTMatInv);
4938 if (NTLN.NumCols() == 1)
4953 nmod_mat_clear (FLINTMat);
4954 nmod_mat_clear (FLINTMatInv);
4960 if (nmod_mat_ncols (FLINTN) == 1)
4962 if (NTLN.NumCols() == 1)
4975 bufUniFactors= factors;
4987 delete [] zeroOneVecs;
4991 factors= bufUniFactors;
5018 int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
5024 int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
5033 bool hitBound=
false;
5034 bool useOldQs=
false;
5036 if (nmod_mat_nrows (FLINTN) != factors.
length())
5038 nmod_mat_clear (FLINTN);
5040 for (
long i=factors.
length()-1;
i >= 0;
i--)
5041 nmod_mat_entry (FLINTN,
i,
i)= 1;
5044 if (NTLN.NumRows() != factors.
length())
5045 ident (NTLN, factors.
length());
5052 nmod_mat_t FLINTC, FLINTK, null;
5054 mat_zz_p* NTLC, NTLK;
5065 for (
int i= 0;
i < factors.
length();
i++,
j++)
5072 for (
int i= 0;
i < factors.
length();
i++,
j++)
5077 for (
int i= 0;
i < d;
i++)
5079 if (bounds [
i] + 1 <= oldL/2)
5081 int k=
tmin (bounds [
i] + 1, oldL/2);
5083 for (
int ii= 0; ii < factors.
length(); ii++)
5085 if (
A[ii].
size() - 1 >=
i)
5093 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5095 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5096 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5098 rank= nmod_mat_nullspace (null, FLINTK);
5099 nmod_mat_clear (FLINTK);
5100 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5101 nmod_mat_clear (FLINTC);
5102 nmod_mat_init_set (FLINTC, FLINTN);
5103 nmod_mat_clear (FLINTN);
5104 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5106 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5108 nmod_mat_clear (FLINTC);
5109 nmod_mat_window_clear (FLINTK);
5110 nmod_mat_clear (null);
5114 transpose (NTLK, NTLK);
5115 kernel (NTLK, NTLK);
5116 transpose (NTLK, NTLK);
5121 if (nmod_mat_ncols (FLINTN) == 1)
5123 if (NTLN.NumCols() == 1)
5140 bufUniFactors= factors;
5146 delete [] zeroOneVecs;
5150 factors= bufUniFactors;
5178 factors,
int l,
int liftBound,
int d,
int*
5179 bounds, nmod_mat_t FLINTN,
CFList& diophant,
5186 factors,
int l,
int liftBound,
int d,
int*
5187 bounds, mat_zz_p& NTLN,
CFList& diophant,
5196 CFList bufFactors= factors;
5199 bool useOldQs=
false;
5200 bool hitBound=
false;
5205 if (nmod_mat_nrows (FLINTN) != factors.
length())
5207 nmod_mat_clear (FLINTN);
5209 for (
long i=factors.
length()-1;
i >= 0;
i--)
5210 nmod_mat_entry (FLINTN,
i,
i)= 1;
5213 if (NTLN.NumRows() != factors.
length())
5214 ident (NTLN, factors.
length());
5221 nmod_mat_t FLINTC, FLINTK, null;
5223 mat_zz_p* NTLC, NTLK;
5227 while (
l <= liftBound)
5235 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5241 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5244 for (
int i= 0;
i < d;
i++)
5246 if (bounds [
i] + 1 <=
l/2)
5248 int k=
tmin (bounds [
i] + 1,
l/2);
5250 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5252 if (
A[ii].
size() - 1 >=
i)
5260 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5262 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5263 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5265 rank= nmod_mat_nullspace (null, FLINTK);
5266 nmod_mat_clear (FLINTK);
5267 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5268 nmod_mat_clear (FLINTC);
5269 nmod_mat_init_set (FLINTC, FLINTN);
5270 nmod_mat_clear (FLINTN);
5271 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5273 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5275 nmod_mat_clear (FLINTC);
5276 nmod_mat_window_clear (FLINTK);
5277 nmod_mat_clear (null);
5281 transpose (NTLK, NTLK);
5282 kernel (NTLK, NTLK);
5283 transpose (NTLK, NTLK);
5288 if (nmod_mat_ncols (FLINTN) == 1)
5290 if (NTLN.NumCols() == 1)
5300 if (nmod_mat_ncols (FLINTN) == 1)
5302 if (NTLN.NumCols() == 1)
5315 bufBufFactors= bufFactors;
5321 delete [] zeroOneVecs;
5325 factors= bufFactors;
5332 bufFactors= bufBufFactors;
5341 int factorsFound= 0;
5344 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5345 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5347 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5348 for (
long i= 0;
i < NTLN.NumCols();
i++)
5350 factorsFoundIndex[
i]= 0;
5354 factorsFoundIndex, FLINTN,
eval,
false
5358 degree (
LCF), factorsFound, factorsFoundIndex,
5362 if (nmod_mat_ncols (FLINTN) ==
result.length())
5366 factorsFoundIndex, NTLN,
eval,
false
5370 degree (
LCF), factorsFound, factorsFoundIndex,
5374 if (NTLN.NumCols() ==
result.length())
5378 delete [] factorsFoundIndex;
5381 delete [] factorsFoundIndex;
5404 factors= bufFactors;
5413 factors,
int l,
int liftBound,
int d,
int*
5414 bounds, mat_zz_pE& NTLN,
CFList& diophant,
5422 CFList bufFactors= factors;
5425 bool useOldQs=
false;
5426 bool hitBound=
false;
5430 if (NTLN.NumRows() != factors.
length())
5431 ident (NTLN, factors.
length());
5434 mat_zz_pE* NTLC, NTLK;
5437 while (
l <= liftBound)
5445 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5451 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5454 for (
int i= 0;
i < d;
i++)
5456 if (bounds [
i] + 1 <=
l/2)
5458 int k=
tmin (bounds [
i] + 1,
l/2);
5460 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5462 if (
A[ii].
size() - 1 >=
i)
5470 transpose (NTLK, NTLK);
5471 kernel (NTLK, NTLK);
5472 transpose (NTLK, NTLK);
5475 if (NTLN.NumCols() == 1)
5482 if (NTLN.NumCols() == 1)
5490 bufBufFactors= bufFactors;
5492 delete [] zeroOneVecs;
5496 factors= bufFactors;
5503 bufFactors= bufBufFactors;
5508 int factorsFound= 0;
5510 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5511 for (
long i= 0;
i < NTLN.NumCols();
i++)
5512 factorsFoundIndex[
i]= 0;
5515 factorsFoundIndex, NTLN,
eval,
false
5519 degree (
LCF), factorsFound, factorsFoundIndex,
5522 if (NTLN.NumCols() ==
result.length())
5525 delete [] factorsFoundIndex;
5528 delete [] factorsFoundIndex;
5551 factors= bufFactors;
5561 int liftBound,
int d,
int* bounds,
5562 nmod_mat_t FLINTN,
CFList& diophant,
5571 int liftBound,
int d,
int* bounds,
5572 mat_zz_p& NTLN,
CFList& diophant,
5583 CFList bufFactors= factors;
5586 bool useOldQs=
false;
5587 bool hitBound=
false;
5598 nmod_mat_clear (FLINTN);
5600 for (
long i=factors.
length()-1;
i >= 0;
i--)
5601 nmod_mat_entry (FLINTN,
i,
i)= 1;
5603 if (NTLN.NumRows() != factors.
length())
5604 ident (NTLN, factors.
length());
5612 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
5614 mat_zz_p* NTLMat,*NTLC, NTLK;
5618 while (
l <= liftBound)
5628 for (
int i= 0;
i <
l*degMipo;
i++)
5632 imBasis= imBasis (
power (
y, degMipo),
y);
5633 imBasis= imBasis (
y, gamma);
5641 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
5643 nmod_mat_inv (FLINTMatInv, FLINTMat);
5646 *NTLMat= inv (*NTLMat);
5656 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5662 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5665 for (
int i= 0;
i < d;
i++)
5667 if (bounds [
i] + 1 <=
l/2)
5669 int k=
tmin (bounds [
i] + 1,
l/2);
5671 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5673 if (
A[ii].
size() - 1 >=
i)
5681 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5694 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5714 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5716 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5717 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5719 rank= nmod_mat_nullspace (null, FLINTK);
5720 nmod_mat_clear (FLINTK);
5721 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5722 nmod_mat_clear (FLINTC);
5723 nmod_mat_init_set (FLINTC, FLINTN);
5724 nmod_mat_clear (FLINTN);
5725 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5727 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5729 nmod_mat_clear (FLINTC);
5730 nmod_mat_window_clear (FLINTK);
5731 nmod_mat_clear (null);
5735 transpose (NTLK, NTLK);
5736 kernel (NTLK, NTLK);
5737 transpose (NTLK, NTLK);
5746 if (nmod_mat_ncols (FLINTN) == 1)
5748 if (NTLN.NumCols() == 1)
5758 nmod_mat_clear (FLINTMat);
5759 nmod_mat_clear (FLINTMatInv);
5760 if (nmod_mat_ncols (FLINTN) == 1)
5763 if (NTLN.NumCols() == 1)
5771 bufBufFactors= bufFactors;
5783 delete [] zeroOneVecs;
5787 factors= bufFactors;
5794 bufFactors= bufBufFactors;
5803 int factorsFound= 0;
5806 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5807 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5809 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5810 for (
long i= 0;
i < NTLN.NumCols();
i++)
5812 factorsFoundIndex[
i]= 0;
5820 degree (
LCF), factorsFound, factorsFoundIndex,
5823 if (nmod_mat_ncols (FLINTN) ==
result.length())
5831 degree (
LCF), factorsFound, factorsFoundIndex,
5834 if (NTLN.NumCols() ==
result.length())
5838 delete [] factorsFoundIndex;
5841 delete [] factorsFoundIndex;
5868 factors= bufFactors;
5877 l,
int liftBound,
int d,
int* bounds,
5878 nmod_mat_t FLINTN,
CFList& diophant,
5886 l,
int liftBound,
int d,
int* bounds,
5887 mat_zz_p& NTLN,
CFList& diophant,
5897 CFList bufFactors= factors;
5900 bool useOldQs=
false;
5902 bool hitBound=
false;
5907 if (nmod_mat_nrows (FLINTN) != factors.
length())
5909 nmod_mat_clear (FLINTN);
5911 for (
long i=factors.
length()-1;
i >= 0;
i--)
5912 nmod_mat_entry (FLINTN,
i,
i)= 1;
5915 if (NTLN.NumRows() != factors.
length())
5916 ident (NTLN, factors.
length());
5922 nmod_mat_t FLINTC, FLINTK, null;
5924 mat_zz_p* NTLC, NTLK;
5928 while (
l <= liftBound)
5936 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5942 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5945 for (
int i= 0;
i < d;
i++)
5947 if (bounds [
i] + 1 <=
l/2)
5949 int k=
tmin (bounds [
i] + 1,
l/2);
5951 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5954 if (
A[ii].
size() - 1 >=
i)
5962 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5964 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5965 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5967 rank= nmod_mat_nullspace (null, FLINTK);
5968 nmod_mat_clear (FLINTK);
5969 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5970 nmod_mat_clear (FLINTC);
5971 nmod_mat_init_set (FLINTC, FLINTN);
5972 nmod_mat_clear (FLINTN);
5973 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5975 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5977 nmod_mat_clear (FLINTC);
5978 nmod_mat_window_clear (FLINTK);
5979 nmod_mat_clear (null);
5983 transpose (NTLK, NTLK);
5984 kernel (NTLK, NTLK);
5985 transpose (NTLK, NTLK);
5990 if (nmod_mat_ncols (FLINTN) == 1)
5992 if (NTLN.NumCols() == 1)
6001 if (nmod_mat_ncols (FLINTN) == 1)
6003 if (NTLN.NumCols() == 1)
6016 bufBufFactors= bufFactors;
6022 delete [] zeroOneVecs;
6026 factors= bufFactors;
6033 bufFactors= bufBufFactors;
6042 int factorsFound= 0;
6045 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6046 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6048 int* factorsFoundIndex=
new int [NTLN.NumCols()];
6049 for (
long i= 0;
i < NTLN.NumCols();
i++)
6051 factorsFoundIndex[
i]= 0;
6055 factorsFoundIndex, FLINTN,
eval,
false
6059 degree (
LCF), factorsFound, factorsFoundIndex,
6062 if (nmod_mat_ncols (FLINTN) ==
result.length())
6066 factorsFoundIndex, NTLN,
eval,
false
6070 degree (
LCF), factorsFound, factorsFoundIndex,
6073 if (NTLN.NumCols() ==
result.length())
6077 delete [] factorsFoundIndex;
6080 delete [] factorsFoundIndex;
6103 factors= bufFactors;
6120 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6124 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6131 factors= bufFactors;
6153 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6157 for (
long j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
6159 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
6164 factors= bufFactors;
6186 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6190 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6197 factors= bufFactors;
6210 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6218 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6231 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6234 nmod_mat_init_set (FLINTN,
N);
6235 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6236 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6239 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6240 for (
long i= 0;
i < NTLN.NumCols();
i++)
6242 factorsFoundIndex [
i]= 0;
6244 if (
degree (F) + 1 > smallFactorDeg)
6246 if (
l < smallFactorDeg)
6257 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6260 if (
result.length() == nmod_mat_ncols (FLINTN))
6262 nmod_mat_clear (FLINTN);
6266 factorsFoundIndex, NTLN,
evaluation, beenInThres
6269 if (
result.length() == NTLN.NumCols())
6273 delete [] factorsFoundIndex;
6278 int i= sizeOfLiftPre - 1;
6280 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6284 if (
l < liftPre[
i-1] + 1)
6290 l= liftPre[
i-1] + 1;
6301 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6304 if (
result.length() == nmod_mat_ncols (FLINTN))
6306 nmod_mat_clear (FLINTN);
6310 factorsFoundIndex, NTLN,
evaluation, beenInThres
6313 if (
result.length() == NTLN.NumCols())
6317 delete [] factorsFoundIndex;
6326 while (((
degree (F,
y)/4)*
i+1) + 4 <= smallFactorDeg)
6338 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6339 LC (F,1).inCoeffDomain() &&
6353 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6358 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6367 if (check1/
Lc (check1) == check2/
Lc (check2))
6370 nmod_mat_clear (FLINTN);
6372 result.append (oldcheck1);
6375 delete [] factorsFoundIndex;
6389 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6392 if (
result.length() == nmod_mat_ncols (FLINTN))
6394 nmod_mat_clear (FLINTN);
6398 factorsFoundIndex, NTLN,
evaluation, beenInThres
6401 if (
result.length() == NTLN.NumCols())
6405 delete [] factorsFoundIndex;
6413 nmod_mat_clear (FLINTN);
6416 delete [] factorsFoundIndex;
6424 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6435 int smallFactorDeg= 11;
6437 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6438 for (
long i= 0;
i < NTLN.NumCols();
i++)
6439 factorsFoundIndex [
i]= 0;
6441 if (
degree (F) + 1 > smallFactorDeg)
6443 if (
l < smallFactorDeg)
6453 factorsFoundIndex, NTLN,
evaluation, beenInThres
6456 if (
result.length() == NTLN.NumCols())
6459 delete [] factorsFoundIndex;
6464 int i= sizeOfLiftPre - 1;
6466 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6470 if (
l < liftPre[
i-1] + 1)
6476 l= liftPre[
i-1] + 1;
6486 factorsFoundIndex, NTLN,
evaluation, beenInThres
6489 if (
result.length() == NTLN.NumCols())
6492 delete [] factorsFoundIndex;
6501 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6513 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6514 LC (F,1).inCoeffDomain() &&
6528 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6533 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6542 if (check1/
Lc (check1) == check2/
Lc (check2))
6544 result.append (oldcheck1);
6547 delete [] factorsFoundIndex;
6560 factorsFoundIndex, NTLN,
evaluation, beenInThres
6563 if (
result.length() == NTLN.NumCols())
6566 delete [] factorsFoundIndex;
6574 delete [] factorsFoundIndex;
6584 int& factorsFound,
bool beenInThres,
CFMatrix&
6593 int& factorsFound,
bool beenInThres,
CFMatrix&
6606 int smallFactorDeg= 11;
6609 nmod_mat_init_set (FLINTN,
N);
6610 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6611 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6614 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6615 for (
long i= 0;
i < NTLN.NumCols();
i++)
6617 factorsFoundIndex [
i]= 0;
6619 if (
degree (F) + 1 > smallFactorDeg)
6621 if (
l < smallFactorDeg)
6632 factorsFoundIndex, FLINTN, beenInThres,
info,
6637 factorsFoundIndex, NTLN, beenInThres,
info,
6643 if (
result.length() == nmod_mat_ncols (FLINTN))
6645 nmod_mat_clear (FLINTN);
6647 if (
result.length() == NTLN.NumCols())
6651 delete [] factorsFoundIndex;
6656 int i= sizeOfLiftPre - 1;
6658 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6662 if (
l < liftPre[
i-1] + 1)
6668 l= liftPre[
i-1] + 1;
6679 factorsFoundIndex, FLINTN, beenInThres,
info,
6684 factorsFoundIndex, NTLN, beenInThres,
info,
6690 if (
result.length() == nmod_mat_ncols (FLINTN))
6692 nmod_mat_clear (FLINTN);
6694 if (
result.length() == NTLN.NumCols())
6698 delete [] factorsFoundIndex;
6707 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6729 factorsFoundIndex, FLINTN, beenInThres,
info,
6734 factorsFoundIndex, NTLN, beenInThres,
info,
6740 if (
result.length() == nmod_mat_ncols (FLINTN))
6742 nmod_mat_clear (FLINTN);
6744 if (
result.length() == NTLN.NumCols())
6748 delete [] factorsFoundIndex;
6756 nmod_mat_clear (FLINTN);
6759 delete [] factorsFoundIndex;
6771 CFList bufUniFactors= uniFactors;
6773 int smallFactorDeg= d;
6775 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6776 int adaptedLiftBound;
6778 int * factorsFoundIndex=
new int [uniFactors.
length()];
6779 for (
int i= 0;
i < uniFactors.
length();
i++)
6780 factorsFoundIndex [
i]= 0;
6783 factorsFoundIndex, degs, success, smallFactorDeg,
eval);
6784 delete [] factorsFoundIndex;
6788 return earlyFactors;
6793 return earlyFactors;
6795 int sizeOldF=
size (
G);
6796 if (
size (F) < sizeOldF)
6800 return earlyFactors;
6804 uniFactors= bufUniFactors;
6819 CFList bufUniFactors= uniFactors;
6821 int smallFactorDeg= d;
6823 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6824 int adaptedLiftBound;
6826 int * factorsFoundIndex=
new int [uniFactors.
length()];
6827 for (
int i= 0;
i < uniFactors.
length();
i++)
6828 factorsFoundIndex [
i]= 0;
6833 delete [] factorsFoundIndex;
6837 return earlyFactors;
6842 return earlyFactors;
6845 int sizeOldF=
size (
G);
6846 if (
size (F) < sizeOldF)
6850 return earlyFactors;
6854 uniFactors= bufUniFactors;
6880 int minBound= bounds[0];
6881 for (
int i= 1;
i < d;
i++)
6884 minBound=
tmin (minBound, bounds[
i]);
6887 CFList bufUniFactors= uniFactors;
6895 bool success=
false;
6897 success, minBound + 1,
eval
6900 if (smallFactors.
length() > 0)
6902 if (smallFactors.
length() == 1)
6913 return smallFactors;
6940 return smallFactors;
6952 return smallFactors;
6956 minBound= bounds[0];
6957 for (
int i= 1;
i < d;
i++)
6960 minBound=
tmin (minBound, bounds[
i]);
6973 return smallFactors;
6992 if (
alpha.level() != 1)
6995 zz_pE::init (NTLMipo);
6999 if (
alpha.level() == 1)
7003 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7004 nmod_mat_entry (FLINTN,
i,
i)= 1;
7006 ident (NTLN, bufUniFactors.
length() - 1);
7015 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7016 nmod_mat_entry (FLINTN,
i,
i)= 1;
7019 ident (NTLN, bufUniFactors.
length() - 1);
7022 ident (NTLNe, bufUniFactors.
length() - 1);
7032 if (
alpha.level() == 1)
7035 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7037 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7046 minBound, bufUniFactors, FLINTN,
7048 minBound, bufUniFactors, NTLN,
7055 bufUniFactors, NTLNe, diophant,
M, Pi, bufQ,
7062 if (
alpha.level() == 1)
7066 minBound, bufUniFactors, FLINTN, diophant,
M,
7068 minBound, bufUniFactors, NTLN, diophant,
M,
7077 liftBound, minBound, bufUniFactors,
7079 FLINTN, diophant,
M, Pi, bufQ,
7081 NTLN, diophant,
M, Pi, bufQ,
7087 minBound, bufUniFactors, NTLNe, diophant,
7094 "time to compute a reduced lattice: ");
7096 if (oldL > liftBound)
7099 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7100 nmod_mat_clear (FLINTN);
7103 return Union (smallFactors,
7115 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7116 nmod_mat_clear (FLINTN);
7127 int * factorsFoundIndex;
7128 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7131 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7132 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7134 factorsFoundIndex=
new int [NTLN.NumCols()];
7135 for (
long i= 0;
i < NTLN.NumCols();
i++)
7137 factorsFoundIndex[
i]= 0;
7141 factorsFoundIndex=
new int [NTLNe.NumCols()];
7142 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7143 factorsFoundIndex[
i]= 0;
7145 int factorsFound= 0;
7147 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7150 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7152 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7157 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7159 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7162 if (
result.length() == nmod_mat_ncols (FLINTN))
7164 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7165 nmod_mat_clear (FLINTN);
7167 if (
result.length() == NTLN.NumCols())
7170 delete [] factorsFoundIndex;
7177 if (
result.length() == NTLNe.NumCols())
7179 delete [] factorsFoundIndex;
7184 delete [] factorsFoundIndex;
7188 int * factorsFoundIndex;
7189 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7192 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7193 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7195 factorsFoundIndex=
new int [NTLN.NumCols()];
7196 for (
long i= 0;
i < NTLN.NumCols();
i++)
7198 factorsFoundIndex[
i]= 0;
7202 factorsFoundIndex=
new int [NTLNe.NumCols()];
7203 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7204 factorsFoundIndex[
i]= 0;
7207 int factorsFound= 0;
7208 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7211 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7213 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7218 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7220 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7223 if (
result.length() == nmod_mat_ncols(FLINTN))
7225 nmod_mat_clear (FLINTN);
7227 if (
result.length() == NTLN.NumCols())
7230 delete [] factorsFoundIndex;
7237 if (
result.length() == NTLNe.NumCols())
7239 delete [] factorsFoundIndex;
7244 delete [] factorsFoundIndex;
7248 bool beenInThres=
false;
7252 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7255 if (nmod_mat_ncols (FLINTN) < bufUniFactors.
length())
7259 if (NTLN.NumCols() < bufUniFactors.
length())
7261 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7270 if (NTLNe.NumCols() < bufUniFactors.
length())
7281 int factorsFound= 0;
7282 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7289 factorsFound, beenInThres,
M, Pi,
7290 diophant, symmetric,
eval
7294 if (
result.length() == nmod_mat_ncols (FLINTN))
7296 nmod_mat_clear (FLINTN);
7298 if (
result.length() == NTLN.NumCols())
7308 factorsFound, beenInThres,
M, Pi,
7309 diophant, symmetric,
eval
7312 if (
result.length() == NTLNe.NumCols())
7324 for (CFListIterator i= result; i.hasItem(); i++)
7327 tmp1= mod (i.getItem(), y-eval);
7329 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7331 tmp2= mod (j.getItem(), y);
7345 long numCols, numRows;
7346 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7349 numCols= nmod_mat_ncols (FLINTN);
7350 numRows= nmod_mat_nrows (FLINTN);
7351 zeroOne= extractZeroOneVecs (FLINTN);
7353 numCols= NTLN.NumCols();
7354 numRows= NTLN.NumRows();
7355 zeroOne= extractZeroOneVecs (NTLN);
7360 numCols= NTLNe.NumCols();
7361 numRows= NTLNe.NumRows();
7362 zeroOne= extractZeroOneVecs (NTLNe);
7364 CFList bufBufUniFactors= bufUniFactors;
7367 CFList factorsConsidered;
7369 for (
int i= 0;
i < numCols;
i++)
7371 if (zeroOne [
i] == 0)
7373 iter= bufUniFactors;
7375 factorsConsidered=
CFList();
7376 for (
int j= 0;
j < numRows;
j++,
iter++)
7378 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7381 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
7386 factorsConsidered.append (
iter.getItem());
7394 factorsConsidered.append (
iter.getItem());
7400 for (iter2=
result; iter2.hasItem(); iter2++)
7402 tmp=
mod (iter2.getItem(),
y-
eval);
7406 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
7411 bufUniFactors= bufBufUniFactors;
7419 if (
alpha.level() == 1)
7422 oldNumCols= nmod_mat_ncols (FLINTN);
7424 oldNumCols= NTLN.NumCols();
7426 resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound,
7427 oldNumCols, oldL, l, eval
7435 oldNumCols= nmod_mat_ncols (FLINTN);
7437 oldNumCols= NTLN.NumCols();
7440 resultBufF= increasePrecisionFq2Fp (bufF, bufUniFactors, factorsFound,
7441 oldNumCols, oldL, alpha, l, eval
7446 oldNumCols= NTLNe.NumCols();
7448 resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound,
7449 oldNumCols, oldL, alpha, l, eval
7457 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7458 nmod_mat_clear (FLINTN);
7466 i.getItem()=
mod (
i.getItem(),
y);
7477 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7478 nmod_mat_clear (FLINTN);
7484 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7485 nmod_mat_clear (FLINTN);
7488 alpha, degs, symmetric,
7496 if (
alpha.level() == 1)
7525 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7528 if (
result.length()== nmod_mat_ncols (FLINTN))
7530 nmod_mat_clear (FLINTN);
7532 if (
result.length()== NTLN.NumCols())
7542 if (
result.length()== NTLNe.NumCols())
7552 if (
alpha.level() == 1)
7555 liftBound,d,bounds,FLINTN,
7557 liftBound, d, bounds, NTLN,
7559 diophant,
M, Pi, bufQ,
eval
7565 liftBound, d, bounds,
7567 FLINTN, diophant,
M,
7575 liftBound, d, bounds,
7581 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7584 if (
result.length() == nmod_mat_ncols (FLINTN))
7586 nmod_mat_clear (FLINTN);
7588 if (
result.length() == NTLN.NumCols())
7598 if (
result.length() == NTLNe.NumCols())
7608 DEBOUTLN (cerr,
"lattice recombination failed");
7617 if (
alpha.level() == 1 || (
alpha.level() != 1 && reduceFq2Fp))
7618 nmod_mat_clear (FLINTN);
7627 minBound= bounds[0];
7628 for (
int i= 1;
i < d;
i++)
7631 minBound=
tmin (minBound, bounds[
i]);
7634 if (minBound > 16 ||
result.length() == 0)
7648 i.getItem()=
mod (
i.getItem(),
y);
7651 degs,symmetric,
eval
7698 imPrimElemAlpha=
map (primElemAlpha,
alpha, bufEvaluation, gamma);
7706 imPrimElemAlpha, 1,
info.getGFName(),
true
7727 CFList bufUniFactors= uniFactors;
7747 int minBound= bounds[0];
7748 for (
int i= 1;
i < d;
i++)
7751 minBound=
tmin (minBound, bounds[
i]);
7763 bool success=
false;
7768 if (smallFactors.
length() > 0)
7770 if (smallFactors.
length() == 1)
7784 return smallFactors;
7811 return smallFactors;
7825 smallFactors.
append (tmp);
7826 return smallFactors;
7830 minBound= bounds[0];
7831 for (
int i= 1;
i < d;
i++)
7834 minBound=
tmin (minBound, bounds[
i]);
7850 smallFactors.
append (tmp);
7851 return smallFactors;
7860 nmod_mat_init (FLINTN, bufUniFactors.
length()-1, bufUniFactors.
length()-1,
7862 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7863 nmod_mat_entry (FLINTN,
i,
i)= 1;
7873 ident (NTLN, bufUniFactors.
length() - 1);
7885 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7890 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7899 minBound+1, bufUniFactors, FLINTN, diophant,
7905 minBound + 1, bufUniFactors, NTLN, diophant,
7912 "time to compute a reduced lattice: ");
7915 if (oldL > liftBound)
7918 nmod_mat_clear (FLINTN);
7933 nmod_mat_clear (FLINTN);
7947 int * factorsFoundIndex;
7950 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7951 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7953 factorsFoundIndex=
new int [NTLN.NumCols()];
7954 for (
long i= 0;
i < NTLN.NumCols();
i++)
7956 factorsFoundIndex[
i]= 0;
7958 int factorsFound= 0;
7963 factorsFound, factorsFoundIndex, FLINTN,
false,
info,
7967 if (
result.length() == nmod_mat_ncols (FLINTN))
7969 nmod_mat_clear (FLINTN);
7972 factorsFound, factorsFoundIndex, NTLN,
false,
info,
7976 if (
result.length() == NTLN.NumCols())
7979 delete [] factorsFoundIndex;
7984 delete [] factorsFoundIndex;
7988 int * factorsFoundIndex;
7990 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7991 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7993 factorsFoundIndex=
new int [NTLN.NumCols()];
7994 for (
long i= 0;
i < NTLN.NumCols();
i++)
7996 factorsFoundIndex[
i]= 0;
7998 int factorsFound= 0;
8002 factorsFound, factorsFoundIndex, FLINTN,
false,
8006 if (
result.length() == nmod_mat_ncols (FLINTN))
8008 nmod_mat_clear (FLINTN);
8011 factorsFound, factorsFoundIndex, NTLN,
false,
8015 if (
result.length() == NTLN.NumCols())
8018 delete [] factorsFoundIndex;
8022 delete [] factorsFoundIndex;
8026 bool beenInThres=
false;
8029 if (
l <= thres && bufUniFactors.
length() > nmod_mat_ncols (FLINTN))
8035 if (
l <= thres && bufUniFactors.
length() > NTLN.NumCols())
8046 int factorsFound= 0;
8050 factorsFound, beenInThres,
M, Pi,
8054 if (
result.length() == nmod_mat_ncols (FLINTN))
8056 nmod_mat_clear (FLINTN);
8059 factorsFound, beenInThres,
M, Pi,
8063 if (
result.length() == NTLN.NumCols())
8100 CFList bufBufUniFactors= bufUniFactors;
8103 CFList factorsConsidered;
8105 for (
int i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
8107 for (
int i= 0;
i < NTLN.NumCols();
i++)
8110 if (zeroOne [
i] == 0)
8112 iter= bufUniFactors;
8114 factorsConsidered=
CFList();
8116 for (
int j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
8118 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
8120 for (
int j= 0;
j < NTLN.NumRows();
j++,
iter++)
8136 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
8141 bufUniFactors= bufBufUniFactors;
8150 oldNumCols= nmod_mat_ncols (FLINTN);
8155 nmod_mat_clear (FLINTN);
8157 oldNumCols= NTLN.NumCols();
8171 i.getItem()=
mod (
i.getItem(),
y);
8193 if (
l/degMipo < liftBound)
8200 if (
result.length()== nmod_mat_ncols (FLINTN))
8202 nmod_mat_clear (FLINTN);
8208 if (
result.length()== NTLN.NumCols())
8220 liftBound, d,bounds,FLINTN,
8221 diophant,
M, Pi, bufQ,
8225 if (
result.length()== nmod_mat_ncols (FLINTN))
8227 nmod_mat_clear (FLINTN);
8230 liftBound, d, bounds, NTLN,
8231 diophant,
M, Pi, bufQ,
8235 if (
result.length()== NTLN.NumCols())
8246 nmod_mat_clear (FLINTN);
8249 DEBOUTLN (cerr,
"lattice recombination failed");
8263 smallFactors.
append (tmp);
8267 minBound= bounds[0];
8268 for (
int i= 1;
i < d;
i++)
8271 minBound=
tmin (minBound, bounds[
i]);
8274 if (minBound > 16 ||
result.length() == 0)
8289 i.getItem()=
mod (
i.getItem(),
y);
8318 int k=
info.getGFDegree();
8319 bool extension=
info.isInExtension();
8320 if (
A.isUnivariate())
8322 if (extension ==
false)
8336 if (
y.level() > 2)
return CFList (F);
8343 A=
A/(contentAx*contentAy);
8344 CFList contentAxFactors, contentAyFactors;
8354 if (
A.inCoeffDomain())
8356 append (factors, contentAxFactors);
8357 append (factors, contentAyFactors);
8361 else if (
A.isUnivariate())
8364 append (factors, contentAxFactors);
8365 append (factors, contentAyFactors);
8386 bool derivXZero=
false;
8393 gcdDerivX=
gcd (
A, derivX);
8394 if (
degree (gcdDerivX) > 0)
8399 append (factorsG, contentAxFactors);
8400 append (factorsG, contentAyFactors);
8407 bool derivYZero=
false;
8414 gcdDerivY=
gcd (
A, derivY);
8415 if (
degree (gcdDerivY) > 0)
8420 append (factorsG, contentAxFactors);
8421 append (factorsG, contentAyFactors);
8436 derivXZero= derivYZero;
8458 int minBound= bounds[0];
8459 for (
int i= 1;
i < boundsLength;
i++)
8462 minBound=
tmin (minBound, bounds[
i]);
8467 int minBound2= bounds2[0];
8468 for (
int i= 1;
i < boundsLength2;
i++)
8470 if (bounds2[
i] != 0)
8471 minBound2=
tmin (minBound2, bounds2[
i]);
8477 CFList uniFactors, list, bufUniFactors;
8482 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8483 CFList bufUniFactors2, list2, uniFactors2;
8494 bool symmetric=
false;
8497 for (
int i= 0;
i < factorNums;
i++)
8503 if (!derivXZero && !fail2 && !symmetric)
8514 "time to find eval point wrt y: ");
8517 if (fail && (
i == 0))
8519 if (!derivXZero && !fail2 && !symmetric)
8521 bufEvaluation= bufEvaluation2;
8522 int dummy= subCheck2;
8523 subCheck2= subCheck1;
8528 bufAeval= bufAeval2;
8537 if (fail && (
i == 0))
8550 if (fail && (
i != 0))
8557 "time for univariate factorization over Fq: ");
8558 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8559 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8561 if (!derivXZero && !fail2 && !symmetric)
8566 "time for univariate factorization in y over Fq: ");
8567 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8568 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8571 if (bufUniFactors.
length() == 1 ||
8572 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8592 if (
i == 0 && !extension)
8598 if (subCheck > 1 && (subCheck1%subCheck == 0))
8601 subst (bufA, bufA, subCheck,
x);
8614 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8618 if (subCheck > 1 && (subCheck2%subCheck == 0))
8621 subst (bufA, bufA, subCheck,
y);
8637 if (!derivXZero && !fail2 && !symmetric)
8644 uniFactors= bufUniFactors;
8646 if (!derivXZero && !fail2 && !symmetric)
8649 evaluation2= bufEvaluation2;
8650 uniFactors2= bufUniFactors2;
8657 if (!derivXZero && !fail2 && !symmetric)
8662 uniFactors2= bufUniFactors2;
8664 evaluation2= bufEvaluation2;
8669 uniFactors= bufUniFactors;
8674 list.
append (bufEvaluation);
8675 if (!derivXZero && !fail2 && !symmetric)
8676 list2.
append (bufEvaluation2);
8679 "total time for univariate factorizations: ");
8681 if (!derivXZero && !fail2 && !symmetric)
8683 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8688 uniFactors= uniFactors2;
8720 minBound= minBound2;
8726 "time to shift eval to zero: ");
8729 if (extension &&
alpha.level() != 1 &&
k==1)
8732 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8734 if ((GF && !extension) || (GF && extension &&
k != 1))
8736 bool earlySuccess=
false;
8740 (
A, earlySuccess, earlyFactors, degs, liftBound,
8743 "time for bivariate hensel lifting over Fq: ");
8744 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8756 "time for naive bivariate factor recombi over Fq: ");
8759 factors=
Union (earlyFactors, factors);
8760 else if (!earlySuccess && degs.
getLength() == 1)
8761 factors= earlyFactors;
8763 else if (
degree (
A) > 4 &&
beta.level() == 1 && (2*minBound)/degMipo < 32)
8771 factors=
Union (lll, factors);
8773 else if (
alpha.level() == 1 && !GF)
8777 factors=
Union (lll, factors);
8779 else if (!extension && (
alpha !=
x || GF))
8783 factors=
Union (lll, factors);
8786 "time to bivar lift and LLL recombi over Fq: ");
8787 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8791 bool earlySuccess=
false;
8795 (
A, earlySuccess, earlyFactors, degs, liftBound,
8798 "time for bivar hensel lifting over Fq: ");
8799 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8807 "time for small subset naive recombi over Fq: ");
8809 int oldUniFactorsLength= uniFactors.
length();
8814 if (
alpha.level() == 1)
8830 "time to increase precision: ");
8831 factors=
Union (factors, tmp);
8833 && uniFactors.
length() != oldUniFactorsLength)
8849 if (
beta.level() != 1 ||
k > 1)
8881 int oldUniFactorsLength= uniFactors.
length();
8890 info2, source, dest, liftBound
8892 factors=
Union (factors, tmp);
8894 && uniFactors.
length() != oldUniFactorsLength)
8911 factors=
Union (earlyFactors, factors);
8912 else if (!earlySuccess && degs.
getLength() == 1)
8913 factors= earlyFactors;
8937 int k=
info.getGFDegree();
8938 char cGFName=
info.getGFName();
8946 bool extension=
true;
8972 else if (!GF && (
alpha !=
x))
8990 bool primFail=
false;
8993 ASSERT (!primFail,
"failure in integer factorizer");
9010 bool primFail=
false;
9012 ASSERT (!primFail,
"failure in integer factorizer");
9022 bufA=
mapUp (bufA,
beta,
v, delta, imPrimElem, source, dest);
9034 bool extension=
true;
9038 if (
ipower (
p, extensionDeg) < (1<<16))
9064 if (
ipower (
p, 2*extensionDeg) < (1<<16))
9080 bool primFail=
false;
9083 ASSERT (!primFail,
"failure in integer factorizer");
void convertFacCFMatrix2nmod_mat_t(nmod_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z/p to a nmod_mat_t
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational pow(const Rational &a, int e)
Rational abs(const Rational &a)
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Conversion to and from NTL.
static bool irreducible(const CFList &AS)
const CanonicalForm CFMap CFMap & N
for(int i=0;i<=n;i++) degsf[i]
int * getRightSide(int **polygon, int sizeOfPolygon, int &sizeOfOutput)
get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with a...
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
#define ASSERT(expression, message)
static const int SW_RATIONAL
set to 1 for computations over Q
#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 )
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
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
static 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...
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
This file implements functions to map between extensions of finite fields.
GLOBAL_VAR flint_rand_t FLINTrandom
generate random integers, random elements of finite fields
VAR void(* factoryError)(const char *s)
int ipower(int b, int m)
int ipower ( int b, int m )
generate random elements in F_p(alpha)
CanonicalForm generate() const
class to iterate through CanonicalForm's
DegreePattern provides a functionality to create, intersect and refine degree patterns.
int find(const int x) const
find an element x
void intersect(const DegreePattern °Pat)
intersect two degree patterns
int getLength() const
getter
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored....
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
class to do operations mod p^k for int's p and k
functions to print debug output
#define DEBOUTLN(stream, objects)
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)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList biFactorize(const CanonicalForm &F, const Variable &v)
const Variable & v
< [in] a sqrfree bivariate poly
CFList *& Aeval
<[in] poly
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
CFArray logarithmicDerivative(const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
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)
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
This file provides utility functions for bivariate factorization.
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoringmultivariate polynomials over a f...
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
CFList extFurtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
return mod(mulNTL(buf1, buf2, b), M)
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern °Pat, const CanonicalForm &eval)
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
CFList furtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval)
void deleteFactors(CFList &factors, int *factorsFoundIndex)
void extReconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
int liftAndComputeLatticeFq2Fp(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const Variable &alpha)
CFList extReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const ExtensionInfo &info, const CanonicalForm &evaluation)
int liftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
CFList extEarlyReconstructionAndLifting(const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, const ExtensionInfo &info, const CanonicalForm &evaluation)
int * extractZeroOneVecs(const mat_zz_p &M)
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
CFList monicReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N)
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval)
CFList reconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval)
CFList extSieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &evaluation, const ExtensionInfo &info)
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, const ExtensionInfo &info, DegreePattern °s, const CanonicalForm &eval, int s, int thres)
naive factor recombination as decribed in "Factoringmultivariate polynomials over a finite field" by ...
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
CFList sieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &eval)
void refineAndRestartLift(const CanonicalForm &F, const nmod_mat_t FLINTN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant)
void reconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_pE &N, const CanonicalForm &eval, bool beenInThres)
void earlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, int deg, const CanonicalForm &eval, const modpk &b, CanonicalForm &den)
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 ...
long isReduced(const mat_zz_p &M)
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern °s, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoringmultivariate polynomials over a finite field" by ...
CFList earlyReconstructionAndLifting(const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation)
int extLiftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo)
const CanonicalForm const modpk & b
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
CFList furtherLiftingAndIncreasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const Variable &alpha, const CanonicalForm &eval)
This file provides functions for factorizing a bivariate polynomial over , or GF.
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
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...
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
convertFacCF2nmod_poly_t(FLINTmipo, M)
void henselLiftResume12(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b)
resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)...
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
This file defines functions for Hensel lifting.
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate 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.
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)
if(!FE_OPT_NO_SHELL_FLAG)
static BOOLEAN IsOne(number a, const coeffs)
static BOOLEAN IsZero(number a, const coeffs)
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 &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
INST_VAR CanonicalForm gf_mipo
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)