64 else if (L.length() == 1)
65 return mod (L.getFirst()(0, 1) ,
M);
66 else if (L.length() == 2)
67 return mod (
mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1),
b),
M);
74 for (
int j= 1;
j <=
l;
j++,
i++)
83#if defined(HAVE_NTL) || defined(HAVE_FLINT)
139 if (
find (list, random))
continue;
143 if (!
find (list, random))
149 if (!
find (list, random))
153 }
while (
find (list, random));
158#if defined(HAVE_NTL) || defined(HAVE_FLINT)
163 if (
A.inCoeffDomain())
166 "univariate polynomial expected or constant expected");
182#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
183 nmod_poly_t FLINTmipo, leadingCoeff;
185 fq_nmod_poly_t FLINTA;
186 fq_nmod_poly_factor_t FLINTFactorsA;
194 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
196 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
199 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
204 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
216 zz_pE::init (NTLMipo);
219 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
220 zz_pE multi= to_zz_pE (1);
229 GF2E::init (NTLMipo);
232 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
233 GF2E multi= to_GF2E (1);
255#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
256 nmod_poly_t FLINTmipo, leadingCoeff;
258 fq_nmod_poly_t FLINTA;
259 fq_nmod_poly_factor_t FLINTFactorsA;
267 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
269 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
272 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
277 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
289 zz_pE::init (NTLMipo);
292 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
293 zz_pE multi= to_zz_pE (1);
302 GF2E::init (NTLMipo);
305 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
306 GF2E multi= to_GF2E (1);
321 nmod_poly_factor_t
result;
322 nmod_poly_factor_init (
result);
323 mp_limb_t leadingCoeff= nmod_poly_factor (
result, FLINTA);
325 if (factorsA.
getFirst().factor().inCoeffDomain())
327 nmod_poly_factor_clear (
result);
344 vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
345 zz_p multi= to_zz_p (1);
352 vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
353 GF2 multi= to_GF2 (1);
366#if defined(HAVE_NTL) || defined(HAVE_FLINT)
375 if (factors.
length() == 0)
387 int k=
info.getGFDegree();
401 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, M) == F " <<
416 int *
v=
new int [
T.length()];
417 for (
int i= 0;
i <
T.length();
i++)
425 bool nosubset=
false;
427 bool trueFactor=
false;
430 while (
T.length() >= 2*
s &&
s <= thres)
432 while (nosubset ==
false)
460 if (!degs.
find (subsetDeg))
505 buf0=
buf (0,
x)*LCBuf;
511 if (
T.length() < 2*
s ||
T.length() ==
s ||
541 if (
T.length() < 2*
s ||
T.length() ==
s)
559 for (
int i= 0;
i <
T.length();
i++)
563 if (
T.length() < 2*
s)
592 if (factors.
length() == 0)
608 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
611 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
625 int *
v=
new int [
T.length()];
626 for (
int i= 0;
i <
T.length();
i++)
628 bool nosubset=
false;
643 while (
T.length() >= 2*
s &&
s <= thres)
645 while (nosubset ==
false)
673 if (!degs.
find (subsetDeg))
707 if (!
Lc (
g).inBaseDomain())
724 denom /=
gcd (denom, denQuot);
740 if (
T.length() < 2*
s ||
T.length() ==
s ||
767 if (
T.length() < 2*
s ||
T.length() ==
s)
783 for (
int i= 0;
i <
T.length();
i++)
788 if (
T.length() < 2*
s)
805#if defined(HAVE_NTL) || defined(HAVE_FLINT)
830 #if defined(HAVE_FLINT)
831 nmod_poly_t Irredpoly;
833 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom,
i*
m+1);
835 #elif defined(HAVE_NTL)
842 BuildIrred (NTLIrredpoly,
i*
m);
853 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
909 if (!
Lc (
g).inBaseDomain())
920 factorsFoundIndex[
l]= 1;
946 if (!
buf.inCoeffDomain())
960 adaptedLiftBound= d + 1;
961 if (adaptedLiftBound < deg)
972 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
978 factorsFoundIndex, degs, success, deg,
eval,
b,
den);
983 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
992 int k=
info.getGFDegree();
1000 adaptedLiftBound= 0;
1001 bool trueFactor=
false;
1026 factorsFoundIndex[
l]= 1;
1038 factorsFoundIndex[
l]= 1;
1057 if (!
buf.inCoeffDomain())
1070 adaptedLiftBound= d + 1;
1071 if (adaptedLiftBound < deg)
1090 for (
int i= 0;
i < sizeOfRightSide;
i++)
1096 if (
i.exp() < degreeLC)
1103 ASSERT (
j > 1,
"j > 1 expected" );
1105 int*
result =
new int [
j - 1];
1106 sizeOfOutput=
j - 1;
1122 int sizeOfNewtonPoly;
1124 int sizeOfRightSide;
1125 int * rightSide=
getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1128 delete [] rightSide;
1129 for (
int i= 0;
i < sizeOfNewtonPoly;
i++)
1130 delete [] newtonPolyg[
i];
1131 delete [] newtonPolyg;
1142 if (factorsFoundIndex[
i] == 1)
1150#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1161 bool extension=
info.isInExtension();
1170 CFList bufUniFactors= uniFactors;
1173 if (!
Lc (
A).inBaseDomain())
1188 bool mipoHasDen=
false;
1193 lcA0=
lc (
A (0, 2));
1194 A *=
b.inverse (lcA0);
1215 earlySuccess=
false;
1216 int newLiftBound= 0;
1218 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
1220 int * factorsFoundIndex=
new int [uniFactors.
length()];
1221 for (
int i= 0;
i < uniFactors.
length();
i++)
1222 factorsFoundIndex [
i]= 0;
1226 if (smallFactorDeg >= liftBound ||
degree (
A,
y) <= 4)
1228 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1230 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1238 bufBufUniFactors= bufUniFactors;
1249 factorsFoundIndex, degs, earlySuccess,
1253 factorsFoundIndex, degs, earlySuccess,
1258 factorsFoundIndex, degs, earlySuccess,
info,
1259 eval, smallFactorDeg);
1260 if (degs.
getLength() > 1 && !earlySuccess &&
1261 smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1263 if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1267 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant,
M,
b);
1270 bufBufUniFactors= bufUniFactors;
1278 factorsFoundIndex, degs, earlySuccess,
1279 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1282 factorsFoundIndex, degs, earlySuccess,
1283 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1287 factorsFoundIndex, degs, earlySuccess,
info,
1288 eval, liftPre[sizeOfLiftPre-1] + 1);
1291 else if (earlySuccess)
1292 liftBound= newLiftBound;
1294 int i= sizeOfLiftPre - 1;
1295 while (degs.
getLength() > 1 && !earlySuccess &&
i - 1 >= 0)
1297 if (newLiftBound >= liftPre[
i] + 1)
1301 liftPre[
i-1] + 1, Pi, diophant,
M,
b);
1304 bufBufUniFactors= bufUniFactors;
1312 factorsFoundIndex, degs, earlySuccess,
1316 factorsFoundIndex, degs, earlySuccess,
1321 factorsFoundIndex, degs, earlySuccess,
info,
1322 eval, liftPre[
i-1] + 1);
1326 liftBound= newLiftBound;
1332 liftBound= newLiftBound;
1337 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1345 bufBufUniFactors= bufUniFactors;
1355 factorsFoundIndex, degs, earlySuccess,
1359 factorsFoundIndex, degs, earlySuccess,
1364 factorsFoundIndex, degs, earlySuccess,
info,
1365 eval, smallFactorDeg);
1367 while ((
degree (
A,
y)/4)*
i + 4 <= smallFactorDeg)
1370 if (degs.
getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1374 dummy, Pi, diophant,
M,
b);
1377 bufBufUniFactors= bufUniFactors;
1385 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1389 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1394 factorsFoundIndex, degs, earlySuccess,
info,
1397 while (degs.
getLength() > 1 && !earlySuccess &&
i < 4)
1399 if (newLiftBound >= dummy)
1404 dummy, Pi, diophant,
M,
b);
1407 bufBufUniFactors= bufUniFactors;
1415 factorsFoundIndex, degs, earlySuccess, dummy,
1419 factorsFoundIndex, degs, earlySuccess, dummy,
1424 factorsFoundIndex, degs, earlySuccess,
info,
1429 liftBound= newLiftBound;
1435 liftBound= newLiftBound;
1446 delete [] factorsFoundIndex;
1449 return bufUniFactors;
1471 for (
i = 1;
i <=
M.NumRows();
i++)
1474 for (
j = 1;
j <=
M.NumCols();
j++)
1490 for (
i = 1;
i <= nmod_mat_nrows(
M);
i++)
1493 for (
j = 1;
j <= nmod_mat_ncols (
M);
j++)
1495 if (!(nmod_mat_entry (
M,
i-1,
j-1)==0))
1509 for (
i = 1;
i <=
M.NumRows();
i++)
1512 for (
j = 1;
j <=
M.NumCols();
j++)
1528 bool nonZeroOne=
false;
1529 int *
result=
new int [
M.NumCols()];
1530 for (
i = 1;
i <=
M.NumCols();
i++)
1532 for (
j = 1;
j <=
M.NumRows();
j++)
1554 bool nonZeroOne=
false;
1555 int *
result=
new int [nmod_mat_ncols (
M)];
1556 for (
i = 0;
i < nmod_mat_ncols (
M);
i++)
1558 for (
j = 0;
j < nmod_mat_nrows (
M);
j++)
1560 if (!((nmod_mat_entry (
M,
j,
i) == 1) || (nmod_mat_entry (
M,
j,
i) == 0)))
1580 bool nonZeroOne=
false;
1581 int *
result=
new int [
M.NumCols()];
1582 for (
i = 1;
i <=
M.NumCols();
i++)
1584 for (
j = 1;
j <=
M.NumRows();
j++)
1605 factors,
const int liftBound,
int& factorsFound,
int*&
1614 if (factors.
length() == 2)
1626 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1637 for (
long i= 1;
i <=
N.NumCols();
i++)
1639 if (factorsFoundIndex [
i - 1] == 1)
1655 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1666 factorsFoundIndex[
i - 1]= 1;
1674 if (factorsFound + 1 ==
N.NumCols())
1676 reconstructedFactors.
append (bufF);
1681 if (reconstructedFactors.
length() != 0)
1689 factors,
const int liftBound,
int& factorsFound,
int*&
1698 if (factors.
length() == 2)
1710 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1721 for (
long i= 1;
i <=
N.NumCols();
i++)
1723 if (factorsFoundIndex [
i - 1] == 1)
1739 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1750 factorsFoundIndex[
i - 1]= 1;
1758 if (factorsFound + 1 ==
N.NumCols())
1760 reconstructedFactors.
append (bufF);
1765 if (reconstructedFactors.
length() != 0)
1773 factors,
const int liftBound,
int& factorsFound,
int*&
1782 if (factors.
length() == 2)
1794 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1805 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
1807 if (factorsFoundIndex [
i] == 1)
1823 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
1825 if (!(nmod_mat_entry (
N,
j,
i) == 0))
1834 factorsFoundIndex[
i]= 1;
1842 if (factorsFound + 1 == nmod_mat_ncols (
N))
1845 reconstructedFactors.
append (bufF);
1849 if (reconstructedFactors.
length() != 0)
1866 CFList bufFactors= factors;
1868 for (
long i= 1;
i <=
N.NumCols();
i++)
1870 if (zeroOneVecs [
i - 1] == 0)
1874 factorsConsidered=
CFList();
1875 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1890 bufFactors=
Difference (bufFactors, factorsConsidered);
1895 factors= bufFactors;
1900 factors= bufFactors;
1908 int precision,
const mat_zz_pE&
N
1917 CFList bufFactors= factors;
1918 CFList factorsConsidered;
1920 for (
long i= 1;
i <=
N.NumCols();
i++)
1922 if (zeroOneVecs [
i - 1] == 0)
1926 factorsConsidered=
CFList();
1927 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1943 bufFactors=
Difference (bufFactors, factorsConsidered);
1948 factors= bufFactors;
1953 factors= bufFactors;
1969 int k=
info.getGFDegree();
1975 CFList bufFactors= factors;
1976 CFList factorsConsidered;
1979 for (
long i= 1;
i <=
N.NumCols();
i++)
1981 if (zeroOneVecs [
i - 1] == 0)
1985 factorsConsidered=
CFList();
1986 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2007 bufFactors=
Difference (bufFactors, factorsConsidered);
2022 bufFactors=
Difference (bufFactors, factorsConsidered);
2029 factors= bufFactors;
2034 factors= bufFactors;
2050 int k=
info.getGFDegree();
2056 CFList bufFactors= factors;
2057 CFList factorsConsidered;
2060 for (
long i= 0;
i < nmod_mat_ncols(
N);
i++)
2062 if (zeroOneVecs [
i] == 0)
2066 factorsConsidered=
CFList();
2067 for (
long j= 0;
j < nmod_mat_nrows(
N);
j++,
iter++)
2069 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2088 bufFactors=
Difference (bufFactors, factorsConsidered);
2103 bufFactors=
Difference (bufFactors, factorsConsidered);
2110 factors= bufFactors;
2115 factors= bufFactors;
2131 CFList bufFactors= factors;
2132 CFList factorsConsidered;
2134 for (
long i= 1;
i <=
N.NumCols();
i++)
2136 if (zeroOneVecs [
i - 1] == 0)
2140 factorsConsidered=
CFList();
2141 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2156 bufFactors=
Difference (bufFactors, factorsConsidered);
2161 factors= bufFactors;
2166 factors= bufFactors;
2182 CFList bufFactors= factors;
2183 CFList factorsConsidered;
2185 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2187 if (zeroOneVecs [
i] == 0)
2191 factorsConsidered=
CFList();
2192 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2194 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2207 bufFactors=
Difference (bufFactors, factorsConsidered);
2212 factors= bufFactors;
2217 factors= bufFactors;
2225 CFList& factors,
const int liftBound,
int& factorsFound,
2226 int*& factorsFoundIndex, mat_zz_p&
N,
bool beenInThres,
2234 int k=
info.getGFDegree();
2239 if (factors.
length() == 2)
2249 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2281 for (
long i= 1;
i <=
N.NumCols();
i++)
2283 if (factorsFoundIndex [
i - 1] == 1)
2299 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2315 factorsFoundIndex[
i - 1]= 1;
2330 factorsFoundIndex[
i - 1]= 1;
2341 if (factorsFound + 1 ==
N.NumCols())
2345 reconstructedFactors.
append (tmp);
2355 CFList& factors,
const int liftBound,
int& factorsFound,
2356 int*& factorsFoundIndex, nmod_mat_t
N,
bool beenInThres,
2364 int k=
info.getGFDegree();
2369 if (factors.
length() == 2)
2379 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2411 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2413 if (factorsFoundIndex [
i] == 1)
2429 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2431 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2445 factorsFoundIndex[
i]= 1;
2460 factorsFoundIndex[
i]= 1;
2471 if (factorsFound + 1 == nmod_mat_nrows (
N))
2475 reconstructedFactors.
append (tmp);
2486 start,
int liftBound,
int minBound,
CFList& factors,
2493 bool wasInBounds=
false;
2494 bool hitBound=
false;
2495 int l= (minBound+1)*2;
2498 bool reduced=
false;
2499 mat_zz_p NTLK, *NTLC;
2505 while (
l <= liftBound)
2521 "time to lift in compute lattice: ");
2529 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2538 "time to compute logarithmic derivative: ");
2540 for (
int i= 0;
i < sizeBounds;
i++)
2542 if (bounds [
i] + 1 <=
l/2)
2545 int k=
tmin (bounds [
i] + 1,
l/2);
2547 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2549 if (
A[ii].
size() - 1 >=
i)
2557 transpose (NTLK, NTLK);
2558 kernel (NTLK, NTLK);
2559 transpose (NTLK, NTLK);
2563 if (NTLN.NumCols() == 1)
2611 start,
int liftBound,
int minBound,
CFList& factors,
2618 bool wasInBounds=
false;
2619 bool hitBound=
false;
2620 int l= (minBound+1)*2;
2623 bool reduced=
false;
2625 nmod_mat_t FLINTK, FLINTC, null;
2631 while (
l <= liftBound)
2647 "time to lift in compute lattice: ");
2655 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2664 "time to compute logarithmic derivative: ");
2666 for (
int i= 0;
i < sizeBounds;
i++)
2668 if (bounds [
i] + 1 <=
l/2)
2671 int k=
tmin (bounds [
i] + 1,
l/2);
2673 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2675 if (
A[ii].
size() - 1 >=
i)
2683 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2685 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2686 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2688 rank= nmod_mat_nullspace (null, FLINTK);
2689 nmod_mat_clear (FLINTK);
2690 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2691 nmod_mat_clear (FLINTC);
2692 nmod_mat_init_set (FLINTC, FLINTN);
2693 nmod_mat_clear (FLINTN);
2694 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2696 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
2698 nmod_mat_clear (FLINTC);
2699 nmod_mat_window_clear (FLINTK);
2700 nmod_mat_clear (null);
2701 if (nmod_mat_ncols (FLINTN) == 1)
2706 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
2750 int liftBound,
int minBound,
int start,
CFList&
2751 factors, mat_zz_p& NTLN,
CFList& diophant,
2760 bool wasInBounds=
false;
2761 bool hitBound=
false;
2772 int l= ((minBound+1)/degMipo+1)*2;
2777 bool reduced=
false;
2784 mat_zz_p* NTLMat, *NTLC, NTLK;
2786 while (
l <= liftBound)
2802 "time to lift in compute lattice: ");
2811 for (
int i= 0;
i <
l*degMipo;
i++)
2814 imBasis= imBasis (
power (
y, degMipo),
y);
2815 imBasis= imBasis (
y, gamma);
2822 *NTLMat= inv (*NTLMat);
2832 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2841 "time to compute logarithmic derivative: ");
2843 for (
int i= 0;
i < sizeBounds;
i++)
2845 if (bounds [
i] + 1 <= (
l/2)*degMipo)
2848 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
2851 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2853 if (
A[ii].
size() - 1 >=
i)
2861 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2870 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2886 transpose (NTLK, NTLK);
2887 kernel (NTLK, NTLK);
2888 transpose (NTLK, NTLK);
2895 if (NTLN.NumCols() == 1)
2910 if (NTLN.NumCols() == 1)
2949 int liftBound,
int minBound,
int start,
CFList&
2950 factors, nmod_mat_t FLINTN,
CFList& diophant,
2959 bool wasInBounds=
false;
2960 bool hitBound=
false;
2971 int l= ((minBound+1)/degMipo+1)*2;
2976 bool reduced=
false;
2984 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
2986 while (
l <= liftBound)
3008 for (
int i= 0;
i <
l*degMipo;
i++)
3011 imBasis= imBasis (
power (
y, degMipo),
y);
3012 imBasis= imBasis (
y, gamma);
3019 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3021 nmod_mat_inv (FLINTMatInv, FLINTMat);
3030 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3039 for (
int i= 0;
i < sizeBounds;
i++)
3041 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3044 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3047 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3049 if (
A[ii].
size() - 1 >=
i)
3057 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3066 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3081 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3083 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3084 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3086 rank= nmod_mat_nullspace (null, FLINTK);
3087 nmod_mat_clear (FLINTK);
3088 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3089 nmod_mat_clear (FLINTC);
3090 nmod_mat_init_set (FLINTC, FLINTN);
3091 nmod_mat_clear (FLINTN);
3092 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3094 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3096 nmod_mat_clear (FLINTC);
3097 nmod_mat_window_clear (FLINTK);
3098 nmod_mat_clear (null);
3103 if (nmod_mat_ncols (FLINTN) == 1)
3116 nmod_mat_clear (FLINTMat);
3117 nmod_mat_clear (FLINTMatInv);
3119 if (nmod_mat_ncols (FLINTN) == 1)
3158 int start,
int liftBound,
int minBound,
CFList& factors,
3165 bool wasInBounds=
false;
3166 bool hitBound=
false;
3167 int l= (minBound+1)*2;
3170 bool reduced=
false;
3172 mat_zz_pE* NTLC, NTLK;
3177 while (
l <= liftBound)
3193 "time to lift in compute lattice: ");
3201 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3203 if (
l == (minBound+1)*2)
3215 "time to compute logarithmic derivative: ");
3217 for (
int i= 0;
i < sizeBounds;
i++)
3219 if (bounds [
i] + 1 <=
l/2)
3222 int k=
tmin (bounds [
i] + 1,
l/2);
3224 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3227 if (
A[ii].
size() - 1 >=
i)
3236 transpose (NTLK, NTLK);
3237 kernel (NTLK, NTLK);
3238 transpose (NTLK, NTLK);
3242 if (NTLN.NumCols() == 1)
3255 if (NTLN.NumCols() == 1)
3293 int start,
int liftBound,
int minBound,
CFList&
3294 factors, nmod_mat_t FLINTN,
CFList& diophant,
3301 int start,
int liftBound,
int minBound,
CFList&
3310 bool wasInBounds=
false;
3311 int l= (minBound+1)*2;
3314 bool hitBound=
false;
3316 bool reduced=
false;
3322 nmod_mat_t FLINTC, FLINTK, null;
3324 mat_zz_p* NTLC, NTLK;
3328 while (
l <= liftBound)
3344 "time to lift in compute lattice: ");
3352 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3354 if (
l == (minBound+1)*2)
3366 "time to compute logarithmic derivative: ");
3368 for (
int i= 0;
i < sizeBounds;
i++)
3370 if (bounds [
i] + 1 <=
l/2)
3373 int k=
tmin (bounds [
i] + 1,
l/2);
3375 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3377 if (
A[ii].
size() - 1 >=
i)
3386 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3388 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3389 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3391 rank= nmod_mat_nullspace (null, FLINTK);
3392 nmod_mat_clear (FLINTK);
3393 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3394 nmod_mat_clear (FLINTC);
3395 nmod_mat_init_set (FLINTC, FLINTN);
3396 nmod_mat_clear (FLINTN);
3397 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3399 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3401 nmod_mat_clear (FLINTC);
3402 nmod_mat_window_clear (FLINTK);
3403 nmod_mat_clear (null);
3407 transpose (NTLK, NTLK);
3408 kernel (NTLK, NTLK);
3409 transpose (NTLK, NTLK);
3415 if (nmod_mat_nrows (FLINTN) == 1)
3417 if (NTLN.NumCols() == 1)
3424 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
3436 if (nmod_mat_ncols (FLINTN) == 1)
3438 if (NTLN.NumCols() == 1)
3476 int oldNumCols,
int oldL,
int precision,
3496 for (
long i=factors.
length()-1;
i >= 0;
i--)
3497 nmod_mat_entry (FLINTN,
i,
i)= 1;
3500 ident (NTLN, factors.
length());
3502 int minBound= bounds[0];
3503 for (
int i= 1;
i < d;
i++)
3506 minBound=
tmin (minBound, bounds[
i]);
3508 int l=
tmax (2*(minBound + 1), oldL);
3511 bool useOldQs=
false;
3512 bool hitBound=
false;
3518 nmod_mat_t FLINTC, FLINTK, null;
3520 mat_zz_p* NTLC, NTLK;
3523 while (
l <= precision)
3529 for (
int i= 0;
i < factors.
length();
i++,
j++)
3536 for (
int i= 0;
i < factors.
length();
i++,
j++)
3540 for (
int i= 0;
i < d;
i++)
3542 if (bounds [
i] + 1 <=
l/2)
3544 int k=
tmin (bounds [
i] + 1,
l/2);
3546 for (
int ii= 0; ii < factors.
length(); ii++)
3548 if (
A[ii].
size() - 1 >=
i)
3556 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3558 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3559 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3561 rank= nmod_mat_nullspace (null, FLINTK);
3562 nmod_mat_clear (FLINTK);
3563 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3564 nmod_mat_clear (FLINTC);
3565 nmod_mat_init_set (FLINTC, FLINTN);
3566 nmod_mat_clear (FLINTN);
3567 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3569 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3571 nmod_mat_clear (FLINTC);
3572 nmod_mat_window_clear (FLINTK);
3573 nmod_mat_clear (null);
3577 transpose (NTLK, NTLK);
3578 kernel (NTLK, NTLK);
3579 transpose (NTLK, NTLK);
3584 if (nmod_mat_ncols (FLINTN) == 1)
3586 nmod_mat_clear (FLINTN);
3588 if (NTLN.NumCols() == 1)
3601 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3605 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
3606 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
3608 if (NTLN.NumCols() < oldNumCols - factorsFound)
3612 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3613 for (
long i= 0;
i < NTLN.NumCols();
i++)
3615 factorsFoundIndex[
i]= 0;
3616 int factorsFound2= 0;
3621 factorsFoundIndex, FLINTN,
eval,
false
3623 if (
result.length() == nmod_mat_ncols (FLINTN))
3625 nmod_mat_clear (FLINTN);
3628 factorsFoundIndex, NTLN,
eval,
false
3630 if (
result.length() == NTLN.NumCols())
3633 delete [] factorsFoundIndex;
3639 delete [] factorsFoundIndex;
3641 else if (
l == precision)
3647 nmod_mat_clear (FLINTN);
3674 nmod_mat_clear (FLINTN);
3685 int oldNumCols,
int oldL,
const Variable&,
3703 ident (NTLN, factors.
length());
3704 int minBound= bounds[0];
3705 for (
int i= 1;
i < d;
i++)
3708 minBound=
tmin (minBound, bounds[
i]);
3710 int l=
tmax (2*(minBound + 1), oldL);
3713 bool useOldQs=
false;
3714 bool hitBound=
false;
3717 mat_zz_pE* NTLC, NTLK;
3720 while (
l <= precision)
3726 for (
int i= 0;
i < factors.
length();
i++,
j++)
3733 for (
int i= 0;
i < factors.
length();
i++,
j++)
3737 for (
int i= 0;
i < d;
i++)
3739 if (bounds [
i] + 1 <=
l/2)
3741 int k=
tmin (bounds [
i] + 1,
l/2);
3743 for (
int ii= 0; ii < factors.
length(); ii++)
3745 if (
A[ii].
size() - 1 >=
i)
3753 transpose (NTLK, NTLK);
3754 kernel (NTLK, NTLK);
3755 transpose (NTLK, NTLK);
3758 if (NTLN.NumCols() == 1)
3769 if (NTLN.NumCols() < oldNumCols - factorsFound)
3773 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3774 for (
long i= 0;
i < NTLN.NumCols();
i++)
3775 factorsFoundIndex[
i]= 0;
3776 int factorsFound2= 0;
3780 factorsFoundIndex, NTLN,
eval,
false);
3781 if (
result.length() == NTLN.NumCols())
3783 delete [] factorsFoundIndex;
3789 delete [] factorsFoundIndex;
3791 else if (
l == precision)
3854 for (
long i=factors.
length()-1;
i >= 0;
i--)
3855 nmod_mat_entry (FLINTN,
i,
i)= 1;
3863 ident (NTLN, factors.
length());
3865 int minBound= bounds[0];
3866 for (
int i= 1;
i < d;
i++)
3869 minBound=
tmin (minBound, bounds[
i]);
3871 int l=
tmax (oldL, 2*((minBound+1)/degMipo+1));
3874 bool useOldQs=
false;
3875 bool hitBound=
false;
3886 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
3888 mat_zz_p* NTLMat,*NTLC, NTLK;
3891 while (
l <= precision)
3898 for (
int i= 0;
i <
l*degMipo;
i++)
3901 imBasis= imBasis (
power (
y, degMipo),
y);
3902 imBasis= imBasis (
y, gamma);
3910 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3912 nmod_mat_inv (FLINTMatInv, FLINTMat);
3915 *NTLMat= inv (*NTLMat);
3924 for (
int i= 0;
i < factors.
length();
i++,
j++)
3931 for (
int i= 0;
i < factors.
length();
i++,
j++)
3935 for (
int i= 0;
i < d;
i++)
3937 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3939 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3941 for (
int ii= 0; ii < factors.
length(); ii++)
3943 if (
A[ii].
size() - 1 >=
i)
3951 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3964 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3984 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3986 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3987 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3989 rank= nmod_mat_nullspace (null, FLINTK);
3990 nmod_mat_clear (FLINTK);
3991 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3992 nmod_mat_clear (FLINTC);
3993 nmod_mat_init_set (FLINTC, FLINTN);
3994 nmod_mat_clear (FLINTN);
3995 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3997 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3999 nmod_mat_clear (FLINTC);
4000 nmod_mat_window_clear (FLINTK);
4001 nmod_mat_clear (null);
4005 transpose (NTLK, NTLK);
4006 kernel (NTLK, NTLK);
4007 transpose (NTLK, NTLK);
4016 if (nmod_mat_ncols (FLINTN) == 1)
4018 nmod_mat_clear (FLINTMat);
4019 nmod_mat_clear (FLINTMatInv);
4020 nmod_mat_clear (FLINTN);
4022 if (NTLN.NumCols() == 1)
4039 nmod_mat_clear (FLINTMat);
4040 nmod_mat_clear (FLINTMatInv);
4046 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4050 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4051 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4053 if (NTLN.NumCols() < oldNumCols - factorsFound)
4057 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4058 for (
long i= 0;
i < NTLN.NumCols();
i++)
4060 factorsFoundIndex[
i]= 0;
4061 int factorsFound2= 0;
4068 if (
result.length() == nmod_mat_ncols (FLINTN))
4070 nmod_mat_clear (FLINTN);
4075 if (
result.length() == NTLN.NumCols())
4078 delete [] factorsFoundIndex;
4084 delete [] factorsFoundIndex;
4086 else if (
l == precision)
4094 nmod_mat_clear (FLINTN);
4124 nmod_mat_clear (FLINTN);
4153 zz_pE::init (NTLMipo);
4155 ident (NTLN, factors.
length());
4156 int minBound= bounds[0];
4157 for (
int i= 1;
i < d;
i++)
4160 minBound=
tmin (minBound, bounds[
i]);
4162 int l=
tmin (2*(minBound + 1), precision);
4165 bool useOldQs=
false;
4166 bool hitBound=
false;
4170 mat_zz_pE* NTLC, NTLK;
4173 while (
l <= precision)
4179 for (
int i= 0;
i < factors.
length();
i++,
j++)
4184 for (
int i= 0;
i < factors.
length();
i++,
j++)
4188 for (
int i= 0;
i < d;
i++)
4190 if (bounds [
i] + 1 <=
l/2)
4192 int k=
tmin (bounds [
i] + 1,
l/2);
4194 for (
int ii= 0; ii < factors.
length(); ii++)
4196 if (
A[ii].
size() - 1 >=
i)
4204 transpose (NTLK, NTLK);
4205 kernel (NTLK, NTLK);
4206 transpose (NTLK, NTLK);
4210 if (NTLN.NumCols() == 1)
4223 CFList bufFactors= factors;
4227 if (
result.length() != NTLN.NumCols() &&
l != precision)
4228 factors= bufFactors;
4229 if (
result.length() == NTLN.NumCols())
4289 for (
long i=factors.
length()-1;
i >= 0;
i--)
4290 nmod_mat_entry (FLINTN,
i,
i)= 1;
4293 ident (NTLN, factors.
length());
4295 int minBound= bounds[0];
4296 for (
int i= 1;
i < d;
i++)
4299 minBound=
tmin (minBound, bounds[
i]);
4301 int l=
tmax (2*(minBound + 1), oldL);
4304 bool useOldQs=
false;
4305 bool hitBound=
false;
4310 nmod_mat_t FLINTC, FLINTK, null;
4312 mat_zz_p* NTLC, NTLK;
4316 while (
l <= precision)
4322 for (
int i= 0;
i < factors.
length();
i++,
j++)
4329 for (
int i= 0;
i < factors.
length();
i++,
j++)
4333 for (
int i= 0;
i < d;
i++)
4335 if (bounds [
i] + 1 <=
l/2)
4337 int k=
tmin (bounds [
i] + 1,
l/2);
4339 for (
int ii= 0; ii < factors.
length(); ii++)
4341 if (
A[ii].
size() - 1 >=
i)
4349 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4351 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4352 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4354 rank= nmod_mat_nullspace (null, FLINTK);
4355 nmod_mat_clear (FLINTK);
4356 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4357 nmod_mat_clear (FLINTC);
4358 nmod_mat_init_set (FLINTC, FLINTN);
4359 nmod_mat_clear (FLINTN);
4360 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4362 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4364 nmod_mat_clear (FLINTC);
4365 nmod_mat_window_clear (FLINTK);
4366 nmod_mat_clear (null);
4370 transpose (NTLK, NTLK);
4371 kernel (NTLK, NTLK);
4372 transpose (NTLK, NTLK);
4377 if (nmod_mat_ncols (FLINTN) == 1)
4379 nmod_mat_clear (FLINTN);
4381 if (NTLN.NumCols() == 1)
4394 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4398 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4399 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4401 if (NTLN.NumCols() < oldNumCols - factorsFound)
4405 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4406 for (
long i= 0;
i < NTLN.NumCols();
i++)
4408 factorsFoundIndex[
i]= 0;
4409 int factorsFound2= 0;
4414 factorsFoundIndex, FLINTN,
eval,
false
4416 if (
result.length() == nmod_mat_ncols (FLINTN))
4418 nmod_mat_clear (FLINTN);
4421 factorsFoundIndex, NTLN,
eval,
false
4423 if (
result.length() == NTLN.NumCols())
4426 delete [] factorsFoundIndex;
4432 delete [] factorsFoundIndex;
4434 else if (
l == precision)
4440 nmod_mat_clear (FLINTN);
4467 nmod_mat_clear (FLINTN);
4479 l,
int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
4485 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
4493 bool hitBound=
false;
4495 if (nmod_mat_nrows (FLINTN) != factors.
length())
4497 nmod_mat_clear (FLINTN);
4499 for (
long i=factors.
length()-1;
i >= 0;
i--)
4500 nmod_mat_entry (FLINTN,
i,
i)= 1;
4504 if (NTLN.NumRows() != factors.
length())
4506 ident (NTLN, factors.
length());
4510 bool useOldQs=
false;
4516 nmod_mat_t FLINTC, FLINTK, null;
4518 mat_zz_p* NTLC, NTLK;
4529 for (
int i= 0;
i < factors.
length();
i++,
j++)
4536 for (
int i= 0;
i < factors.
length();
i++,
j++)
4541 for (
int i= 0;
i < d;
i++)
4543 if (bounds [
i] + 1 <= oldL/2)
4545 int k=
tmin (bounds [
i] + 1, oldL/2);
4547 for (
int ii= 0; ii < factors.
length(); ii++)
4549 if (
A[ii].
size() - 1 >=
i)
4557 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4559 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4560 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4562 rank= nmod_mat_nullspace (null, FLINTK);
4563 nmod_mat_clear (FLINTK);
4564 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4565 nmod_mat_clear (FLINTC);
4566 nmod_mat_init_set (FLINTC, FLINTN);
4567 nmod_mat_clear (FLINTN);
4568 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4570 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4572 nmod_mat_clear (FLINTC);
4573 nmod_mat_window_clear (FLINTK);
4574 nmod_mat_clear (null);
4578 transpose (NTLK, NTLK);
4579 kernel (NTLK, NTLK);
4580 transpose (NTLK, NTLK);
4585 if (nmod_mat_ncols (FLINTN) == 1)
4587 if (NTLN.NumCols() == 1)
4596 if (nmod_mat_ncols (FLINTN) == 1)
4598 if (NTLN.NumCols() == 1)
4611 bufUniFactors= factors;
4617 delete [] zeroOneVecs;
4621 factors= bufUniFactors;
4648 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_pE& NTLN,
4655 bool hitBound=
false;
4656 bool useOldQs=
false;
4657 if (NTLN.NumRows() != factors.
length())
4658 ident (NTLN, factors.
length());
4662 mat_zz_pE* NTLC, NTLK;
4672 for (
int i= 0;
i < factors.
length();
i++,
j++)
4679 for (
int i= 0;
i < factors.
length();
i++,
j++)
4684 for (
int i= 0;
i < d;
i++)
4686 if (bounds [
i] + 1 <= oldL/2)
4688 int k=
tmin (bounds [
i] + 1, oldL/2);
4690 for (
int ii= 0; ii < factors.
length(); ii++)
4692 if (
A[ii].
size() - 1 >=
i)
4700 transpose (NTLK, NTLK);
4701 kernel (NTLK, NTLK);
4702 transpose (NTLK, NTLK);
4706 if (NTLN.NumCols() == 1)
4713 if (NTLN.NumCols() == 1)
4722 bufUniFactors= factors;
4724 delete [] zeroOneVecs;
4728 factors= bufUniFactors;
4757 int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
const
4764 int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
const
4773 bool hitBound=
false;
4774 bool useOldQs=
false;
4783 nmod_mat_clear (FLINTN);
4785 for (
long i=factors.
length()-1;
i >= 0;
i--)
4786 nmod_mat_entry (FLINTN,
i,
i)= 1;
4788 if (NTLN.NumRows() != factors.
length())
4789 ident (NTLN, factors.
length());
4799 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
4801 mat_zz_p* NTLC, NTLK, *NTLMat;
4810 powX=
power (
y-gamma, oldL);
4811 Mat=
CFMatrix (oldL*degMipo, oldL*degMipo);
4812 for (
int i= 0;
i < oldL*degMipo;
i++)
4815 imBasis= imBasis (
power (
y, degMipo),
y);
4816 imBasis= imBasis (
y, gamma);
4824 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
4826 nmod_mat_inv (FLINTMatInv, FLINTMat);
4829 *NTLMat= inv (*NTLMat);
4838 for (
int i= 0;
i < factors.
length();
i++,
j++)
4844 for (
int i= 0;
i < factors.
length();
i++,
j++)
4849 for (
int i= 0;
i < d;
i++)
4851 if (bounds [
i] + 1 <= oldL/2)
4853 int k=
tmin (bounds [
i] + 1, oldL/2);
4855 for (
int ii= 0; ii < factors.
length(); ii++)
4857 if (
A[ii].
size() - 1 >=
i)
4865 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4878 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4898 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4900 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4901 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4903 rank= nmod_mat_nullspace (null, FLINTK);
4904 nmod_mat_clear (FLINTK);
4905 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4906 nmod_mat_clear (FLINTC);
4907 nmod_mat_init_set (FLINTC, FLINTN);
4908 nmod_mat_clear (FLINTN);
4909 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4911 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4913 nmod_mat_clear (FLINTC);
4914 nmod_mat_window_clear (FLINTK);
4915 nmod_mat_clear (null);
4919 transpose (NTLK, NTLK);
4920 kernel (NTLK, NTLK);
4921 transpose (NTLK, NTLK);
4930 if (nmod_mat_ncols (FLINTN) == 1)
4932 nmod_mat_clear (FLINTMat);
4933 nmod_mat_clear (FLINTMatInv);
4935 if (NTLN.NumCols() == 1)
4950 nmod_mat_clear (FLINTMat);
4951 nmod_mat_clear (FLINTMatInv);
4957 if (nmod_mat_ncols (FLINTN) == 1)
4959 if (NTLN.NumCols() == 1)
4972 bufUniFactors= factors;
4984 delete [] zeroOneVecs;
4988 factors= bufUniFactors;
5015 int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
5021 int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
5030 bool hitBound=
false;
5031 bool useOldQs=
false;
5033 if (nmod_mat_nrows (FLINTN) != factors.
length())
5035 nmod_mat_clear (FLINTN);
5037 for (
long i=factors.
length()-1;
i >= 0;
i--)
5038 nmod_mat_entry (FLINTN,
i,
i)= 1;
5041 if (NTLN.NumRows() != factors.
length())
5042 ident (NTLN, factors.
length());
5049 nmod_mat_t FLINTC, FLINTK, null;
5051 mat_zz_p* NTLC, NTLK;
5062 for (
int i= 0;
i < factors.
length();
i++,
j++)
5069 for (
int i= 0;
i < factors.
length();
i++,
j++)
5074 for (
int i= 0;
i < d;
i++)
5076 if (bounds [
i] + 1 <= oldL/2)
5078 int k=
tmin (bounds [
i] + 1, oldL/2);
5080 for (
int ii= 0; ii < factors.
length(); ii++)
5082 if (
A[ii].
size() - 1 >=
i)
5090 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5092 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5093 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5095 rank= nmod_mat_nullspace (null, FLINTK);
5096 nmod_mat_clear (FLINTK);
5097 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5098 nmod_mat_clear (FLINTC);
5099 nmod_mat_init_set (FLINTC, FLINTN);
5100 nmod_mat_clear (FLINTN);
5101 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5103 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5105 nmod_mat_clear (FLINTC);
5106 nmod_mat_window_clear (FLINTK);
5107 nmod_mat_clear (null);
5111 transpose (NTLK, NTLK);
5112 kernel (NTLK, NTLK);
5113 transpose (NTLK, NTLK);
5118 if (nmod_mat_ncols (FLINTN) == 1)
5120 if (NTLN.NumCols() == 1)
5137 bufUniFactors= factors;
5143 delete [] zeroOneVecs;
5147 factors= bufUniFactors;
5175 factors,
int l,
int liftBound,
int d,
int*
5176 bounds, nmod_mat_t FLINTN,
CFList& diophant,
5183 factors,
int l,
int liftBound,
int d,
int*
5184 bounds, mat_zz_p& NTLN,
CFList& diophant,
5193 CFList bufFactors= factors;
5196 bool useOldQs=
false;
5197 bool hitBound=
false;
5202 if (nmod_mat_nrows (FLINTN) != factors.
length())
5204 nmod_mat_clear (FLINTN);
5206 for (
long i=factors.
length()-1;
i >= 0;
i--)
5207 nmod_mat_entry (FLINTN,
i,
i)= 1;
5210 if (NTLN.NumRows() != factors.
length())
5211 ident (NTLN, factors.
length());
5218 nmod_mat_t FLINTC, FLINTK, null;
5220 mat_zz_p* NTLC, NTLK;
5224 while (
l <= liftBound)
5232 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5238 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5241 for (
int i= 0;
i < d;
i++)
5243 if (bounds [
i] + 1 <=
l/2)
5245 int k=
tmin (bounds [
i] + 1,
l/2);
5247 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5249 if (
A[ii].
size() - 1 >=
i)
5257 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5259 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5260 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5262 rank= nmod_mat_nullspace (null, FLINTK);
5263 nmod_mat_clear (FLINTK);
5264 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5265 nmod_mat_clear (FLINTC);
5266 nmod_mat_init_set (FLINTC, FLINTN);
5267 nmod_mat_clear (FLINTN);
5268 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5270 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5272 nmod_mat_clear (FLINTC);
5273 nmod_mat_window_clear (FLINTK);
5274 nmod_mat_clear (null);
5278 transpose (NTLK, NTLK);
5279 kernel (NTLK, NTLK);
5280 transpose (NTLK, NTLK);
5285 if (nmod_mat_ncols (FLINTN) == 1)
5287 if (NTLN.NumCols() == 1)
5297 if (nmod_mat_ncols (FLINTN) == 1)
5299 if (NTLN.NumCols() == 1)
5312 bufBufFactors= bufFactors;
5318 delete [] zeroOneVecs;
5322 factors= bufFactors;
5329 bufFactors= bufBufFactors;
5338 int factorsFound= 0;
5341 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5342 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5344 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5345 for (
long i= 0;
i < NTLN.NumCols();
i++)
5347 factorsFoundIndex[
i]= 0;
5351 factorsFoundIndex, FLINTN,
eval,
false
5355 degree (
LCF), factorsFound, factorsFoundIndex,
5359 if (nmod_mat_ncols (FLINTN) ==
result.length())
5363 factorsFoundIndex, NTLN,
eval,
false
5367 degree (
LCF), factorsFound, factorsFoundIndex,
5371 if (NTLN.NumCols() ==
result.length())
5375 delete [] factorsFoundIndex;
5378 delete [] factorsFoundIndex;
5401 factors= bufFactors;
5410 factors,
int l,
int liftBound,
int d,
int*
5411 bounds, mat_zz_pE& NTLN,
CFList& diophant,
5419 CFList bufFactors= factors;
5422 bool useOldQs=
false;
5423 bool hitBound=
false;
5427 if (NTLN.NumRows() != factors.
length())
5428 ident (NTLN, factors.
length());
5431 mat_zz_pE* NTLC, NTLK;
5434 while (
l <= liftBound)
5442 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5448 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5451 for (
int i= 0;
i < d;
i++)
5453 if (bounds [
i] + 1 <=
l/2)
5455 int k=
tmin (bounds [
i] + 1,
l/2);
5457 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5459 if (
A[ii].
size() - 1 >=
i)
5467 transpose (NTLK, NTLK);
5468 kernel (NTLK, NTLK);
5469 transpose (NTLK, NTLK);
5472 if (NTLN.NumCols() == 1)
5479 if (NTLN.NumCols() == 1)
5487 bufBufFactors= bufFactors;
5489 delete [] zeroOneVecs;
5493 factors= bufFactors;
5500 bufFactors= bufBufFactors;
5505 int factorsFound= 0;
5507 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5508 for (
long i= 0;
i < NTLN.NumCols();
i++)
5509 factorsFoundIndex[
i]= 0;
5512 factorsFoundIndex, NTLN,
eval,
false
5516 degree (
LCF), factorsFound, factorsFoundIndex,
5519 if (NTLN.NumCols() ==
result.length())
5522 delete [] factorsFoundIndex;
5525 delete [] factorsFoundIndex;
5548 factors= bufFactors;
5558 int liftBound,
int d,
int* bounds,
5559 nmod_mat_t FLINTN,
CFList& diophant,
5568 int liftBound,
int d,
int* bounds,
5569 mat_zz_p& NTLN,
CFList& diophant,
5580 CFList bufFactors= factors;
5583 bool useOldQs=
false;
5584 bool hitBound=
false;
5595 nmod_mat_clear (FLINTN);
5597 for (
long i=factors.
length()-1;
i >= 0;
i--)
5598 nmod_mat_entry (FLINTN,
i,
i)= 1;
5600 if (NTLN.NumRows() != factors.
length())
5601 ident (NTLN, factors.
length());
5609 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
5611 mat_zz_p* NTLMat,*NTLC, NTLK;
5615 while (
l <= liftBound)
5625 for (
int i= 0;
i <
l*degMipo;
i++)
5629 imBasis= imBasis (
power (
y, degMipo),
y);
5630 imBasis= imBasis (
y, gamma);
5638 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
5640 nmod_mat_inv (FLINTMatInv, FLINTMat);
5643 *NTLMat= inv (*NTLMat);
5653 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5659 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5662 for (
int i= 0;
i < d;
i++)
5664 if (bounds [
i] + 1 <=
l/2)
5666 int k=
tmin (bounds [
i] + 1,
l/2);
5668 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5670 if (
A[ii].
size() - 1 >=
i)
5678 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5691 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5711 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5713 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5714 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5716 rank= nmod_mat_nullspace (null, FLINTK);
5717 nmod_mat_clear (FLINTK);
5718 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5719 nmod_mat_clear (FLINTC);
5720 nmod_mat_init_set (FLINTC, FLINTN);
5721 nmod_mat_clear (FLINTN);
5722 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5724 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5726 nmod_mat_clear (FLINTC);
5727 nmod_mat_window_clear (FLINTK);
5728 nmod_mat_clear (null);
5732 transpose (NTLK, NTLK);
5733 kernel (NTLK, NTLK);
5734 transpose (NTLK, NTLK);
5743 if (nmod_mat_ncols (FLINTN) == 1)
5745 if (NTLN.NumCols() == 1)
5755 nmod_mat_clear (FLINTMat);
5756 nmod_mat_clear (FLINTMatInv);
5757 if (nmod_mat_ncols (FLINTN) == 1)
5760 if (NTLN.NumCols() == 1)
5768 bufBufFactors= bufFactors;
5780 delete [] zeroOneVecs;
5784 factors= bufFactors;
5791 bufFactors= bufBufFactors;
5800 int factorsFound= 0;
5803 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5804 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5806 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5807 for (
long i= 0;
i < NTLN.NumCols();
i++)
5809 factorsFoundIndex[
i]= 0;
5817 degree (
LCF), factorsFound, factorsFoundIndex,
5820 if (nmod_mat_ncols (FLINTN) ==
result.length())
5828 degree (
LCF), factorsFound, factorsFoundIndex,
5831 if (NTLN.NumCols() ==
result.length())
5835 delete [] factorsFoundIndex;
5838 delete [] factorsFoundIndex;
5865 factors= bufFactors;
5874 l,
int liftBound,
int d,
int* bounds,
5875 nmod_mat_t FLINTN,
CFList& diophant,
5883 l,
int liftBound,
int d,
int* bounds,
5884 mat_zz_p& NTLN,
CFList& diophant,
5894 CFList bufFactors= factors;
5897 bool useOldQs=
false;
5899 bool hitBound=
false;
5904 if (nmod_mat_nrows (FLINTN) != factors.
length())
5906 nmod_mat_clear (FLINTN);
5908 for (
long i=factors.
length()-1;
i >= 0;
i--)
5909 nmod_mat_entry (FLINTN,
i,
i)= 1;
5912 if (NTLN.NumRows() != factors.
length())
5913 ident (NTLN, factors.
length());
5919 nmod_mat_t FLINTC, FLINTK, null;
5921 mat_zz_p* NTLC, NTLK;
5925 while (
l <= liftBound)
5933 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5939 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5942 for (
int i= 0;
i < d;
i++)
5944 if (bounds [
i] + 1 <=
l/2)
5946 int k=
tmin (bounds [
i] + 1,
l/2);
5948 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5951 if (
A[ii].
size() - 1 >=
i)
5959 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5961 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5962 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5964 rank= nmod_mat_nullspace (null, FLINTK);
5965 nmod_mat_clear (FLINTK);
5966 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5967 nmod_mat_clear (FLINTC);
5968 nmod_mat_init_set (FLINTC, FLINTN);
5969 nmod_mat_clear (FLINTN);
5970 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5972 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5974 nmod_mat_clear (FLINTC);
5975 nmod_mat_window_clear (FLINTK);
5976 nmod_mat_clear (null);
5980 transpose (NTLK, NTLK);
5981 kernel (NTLK, NTLK);
5982 transpose (NTLK, NTLK);
5987 if (nmod_mat_ncols (FLINTN) == 1)
5989 if (NTLN.NumCols() == 1)
5998 if (nmod_mat_ncols (FLINTN) == 1)
6000 if (NTLN.NumCols() == 1)
6013 bufBufFactors= bufFactors;
6019 delete [] zeroOneVecs;
6023 factors= bufFactors;
6030 bufFactors= bufBufFactors;
6039 int factorsFound= 0;
6042 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6043 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6045 int* factorsFoundIndex=
new int [NTLN.NumCols()];
6046 for (
long i= 0;
i < NTLN.NumCols();
i++)
6048 factorsFoundIndex[
i]= 0;
6052 factorsFoundIndex, FLINTN,
eval,
false
6056 degree (
LCF), factorsFound, factorsFoundIndex,
6059 if (nmod_mat_ncols (FLINTN) ==
result.length())
6063 factorsFoundIndex, NTLN,
eval,
false
6067 degree (
LCF), factorsFound, factorsFoundIndex,
6070 if (NTLN.NumCols() ==
result.length())
6074 delete [] factorsFoundIndex;
6077 delete [] factorsFoundIndex;
6100 factors= bufFactors;
6117 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6121 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6128 factors= bufFactors;
6150 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6154 for (
long j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
6156 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
6161 factors= bufFactors;
6183 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6187 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6194 factors= bufFactors;
6207 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6215 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6228 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6231 nmod_mat_init_set (FLINTN,
N);
6232 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6233 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6236 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6237 for (
long i= 0;
i < NTLN.NumCols();
i++)
6239 factorsFoundIndex [
i]= 0;
6241 if (
degree (F) + 1 > smallFactorDeg)
6243 if (
l < smallFactorDeg)
6254 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6257 if (
result.length() == nmod_mat_ncols (FLINTN))
6259 nmod_mat_clear (FLINTN);
6263 factorsFoundIndex, NTLN,
evaluation, beenInThres
6266 if (
result.length() == NTLN.NumCols())
6270 delete [] factorsFoundIndex;
6275 int i= sizeOfLiftPre - 1;
6277 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6281 if (
l < liftPre[
i-1] + 1)
6287 l= liftPre[
i-1] + 1;
6298 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6301 if (
result.length() == nmod_mat_ncols (FLINTN))
6303 nmod_mat_clear (FLINTN);
6307 factorsFoundIndex, NTLN,
evaluation, beenInThres
6310 if (
result.length() == NTLN.NumCols())
6314 delete [] factorsFoundIndex;
6323 while (((
degree (F,
y)/4)*
i+1) + 4 <= smallFactorDeg)
6335 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6336 LC (F,1).inCoeffDomain() &&
6350 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6355 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6364 if (check1/
Lc (check1) == check2/
Lc (check2))
6367 nmod_mat_clear (FLINTN);
6369 result.append (oldcheck1);
6372 delete [] factorsFoundIndex;
6386 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6389 if (
result.length() == nmod_mat_ncols (FLINTN))
6391 nmod_mat_clear (FLINTN);
6395 factorsFoundIndex, NTLN,
evaluation, beenInThres
6398 if (
result.length() == NTLN.NumCols())
6402 delete [] factorsFoundIndex;
6410 nmod_mat_clear (FLINTN);
6413 delete [] factorsFoundIndex;
6421 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6432 int smallFactorDeg= 11;
6434 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6435 for (
long i= 0;
i < NTLN.NumCols();
i++)
6436 factorsFoundIndex [
i]= 0;
6438 if (
degree (F) + 1 > smallFactorDeg)
6440 if (
l < smallFactorDeg)
6450 factorsFoundIndex, NTLN,
evaluation, beenInThres
6453 if (
result.length() == NTLN.NumCols())
6456 delete [] factorsFoundIndex;
6461 int i= sizeOfLiftPre - 1;
6463 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6467 if (
l < liftPre[
i-1] + 1)
6473 l= liftPre[
i-1] + 1;
6483 factorsFoundIndex, NTLN,
evaluation, beenInThres
6486 if (
result.length() == NTLN.NumCols())
6489 delete [] factorsFoundIndex;
6498 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6510 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6511 LC (F,1).inCoeffDomain() &&
6525 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6530 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6539 if (check1/
Lc (check1) == check2/
Lc (check2))
6541 result.append (oldcheck1);
6544 delete [] factorsFoundIndex;
6557 factorsFoundIndex, NTLN,
evaluation, beenInThres
6560 if (
result.length() == NTLN.NumCols())
6563 delete [] factorsFoundIndex;
6571 delete [] factorsFoundIndex;
6581 int& factorsFound,
bool beenInThres,
CFMatrix&
6590 int& factorsFound,
bool beenInThres,
CFMatrix&
6603 int smallFactorDeg= 11;
6606 nmod_mat_init_set (FLINTN,
N);
6607 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6608 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6611 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6612 for (
long i= 0;
i < NTLN.NumCols();
i++)
6614 factorsFoundIndex [
i]= 0;
6616 if (
degree (F) + 1 > smallFactorDeg)
6618 if (
l < smallFactorDeg)
6629 factorsFoundIndex, FLINTN, beenInThres,
info,
6634 factorsFoundIndex, NTLN, beenInThres,
info,
6640 if (
result.length() == nmod_mat_ncols (FLINTN))
6642 nmod_mat_clear (FLINTN);
6644 if (
result.length() == NTLN.NumCols())
6648 delete [] factorsFoundIndex;
6653 int i= sizeOfLiftPre - 1;
6655 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6659 if (
l < liftPre[
i-1] + 1)
6665 l= liftPre[
i-1] + 1;
6676 factorsFoundIndex, FLINTN, beenInThres,
info,
6681 factorsFoundIndex, NTLN, beenInThres,
info,
6687 if (
result.length() == nmod_mat_ncols (FLINTN))
6689 nmod_mat_clear (FLINTN);
6691 if (
result.length() == NTLN.NumCols())
6695 delete [] factorsFoundIndex;
6704 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6726 factorsFoundIndex, FLINTN, beenInThres,
info,
6731 factorsFoundIndex, NTLN, beenInThres,
info,
6737 if (
result.length() == nmod_mat_ncols (FLINTN))
6739 nmod_mat_clear (FLINTN);
6741 if (
result.length() == NTLN.NumCols())
6745 delete [] factorsFoundIndex;
6753 nmod_mat_clear (FLINTN);
6756 delete [] factorsFoundIndex;
6768 CFList bufUniFactors= uniFactors;
6770 int smallFactorDeg= d;
6772 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6773 int adaptedLiftBound;
6775 int * factorsFoundIndex=
new int [uniFactors.
length()];
6776 for (
int i= 0;
i < uniFactors.
length();
i++)
6777 factorsFoundIndex [
i]= 0;
6780 factorsFoundIndex, degs, success, smallFactorDeg,
eval);
6781 delete [] factorsFoundIndex;
6785 return earlyFactors;
6790 return earlyFactors;
6792 int sizeOldF=
size (
G);
6793 if (
size (F) < sizeOldF)
6797 return earlyFactors;
6801 uniFactors= bufUniFactors;
6816 CFList bufUniFactors= uniFactors;
6818 int smallFactorDeg= d;
6820 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6821 int adaptedLiftBound;
6823 int * factorsFoundIndex=
new int [uniFactors.
length()];
6824 for (
int i= 0;
i < uniFactors.
length();
i++)
6825 factorsFoundIndex [
i]= 0;
6830 delete [] factorsFoundIndex;
6834 return earlyFactors;
6839 return earlyFactors;
6842 int sizeOldF=
size (
G);
6843 if (
size (F) < sizeOldF)
6847 return earlyFactors;
6851 uniFactors= bufUniFactors;
6877 int minBound= bounds[0];
6878 for (
int i= 1;
i < d;
i++)
6881 minBound=
tmin (minBound, bounds[
i]);
6884 CFList bufUniFactors= uniFactors;
6892 bool success=
false;
6894 success, minBound + 1,
eval
6897 if (smallFactors.
length() > 0)
6899 if (smallFactors.
length() == 1)
6910 return smallFactors;
6937 return smallFactors;
6949 return smallFactors;
6953 minBound= bounds[0];
6954 for (
int i= 1;
i < d;
i++)
6957 minBound=
tmin (minBound, bounds[
i]);
6970 return smallFactors;
6992 zz_pE::init (NTLMipo);
7000 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7001 nmod_mat_entry (FLINTN,
i,
i)= 1;
7003 ident (NTLN, bufUniFactors.
length() - 1);
7012 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7013 nmod_mat_entry (FLINTN,
i,
i)= 1;
7016 ident (NTLN, bufUniFactors.
length() - 1);
7019 ident (NTLNe, bufUniFactors.
length() - 1);
7032 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7034 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7043 minBound, bufUniFactors, FLINTN,
7045 minBound, bufUniFactors, NTLN,
7052 bufUniFactors, NTLNe, diophant,
M, Pi, bufQ,
7063 minBound, bufUniFactors, FLINTN, diophant,
M,
7065 minBound, bufUniFactors, NTLN, diophant,
M,
7074 liftBound, minBound, bufUniFactors,
7076 FLINTN, diophant,
M, Pi, bufQ,
7078 NTLN, diophant,
M, Pi, bufQ,
7084 minBound, bufUniFactors, NTLNe, diophant,
7091 "time to compute a reduced lattice: ");
7093 if (oldL > liftBound)
7097 nmod_mat_clear (FLINTN);
7100 return Union (smallFactors,
7113 nmod_mat_clear (FLINTN);
7124 int * factorsFoundIndex;
7128 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7129 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7131 factorsFoundIndex=
new int [NTLN.NumCols()];
7132 for (
long i= 0;
i < NTLN.NumCols();
i++)
7134 factorsFoundIndex[
i]= 0;
7138 factorsFoundIndex=
new int [NTLNe.NumCols()];
7139 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7140 factorsFoundIndex[
i]= 0;
7142 int factorsFound= 0;
7147 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7149 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7154 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7159 if (
result.length() == nmod_mat_ncols (FLINTN))
7162 nmod_mat_clear (FLINTN);
7164 if (
result.length() == NTLN.NumCols())
7167 delete [] factorsFoundIndex;
7174 if (
result.length() == NTLNe.NumCols())
7176 delete [] factorsFoundIndex;
7181 delete [] factorsFoundIndex;
7185 int * factorsFoundIndex;
7189 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7190 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7192 factorsFoundIndex=
new int [NTLN.NumCols()];
7193 for (
long i= 0;
i < NTLN.NumCols();
i++)
7195 factorsFoundIndex[
i]= 0;
7199 factorsFoundIndex=
new int [NTLNe.NumCols()];
7200 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7201 factorsFoundIndex[
i]= 0;
7204 int factorsFound= 0;
7208 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7210 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7215 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7220 if (
result.length() == nmod_mat_ncols(FLINTN))
7222 nmod_mat_clear (FLINTN);
7224 if (
result.length() == NTLN.NumCols())
7227 delete [] factorsFoundIndex;
7234 if (
result.length() == NTLNe.NumCols())
7236 delete [] factorsFoundIndex;
7241 delete [] factorsFoundIndex;
7245 bool beenInThres=
false;
7252 if (nmod_mat_ncols (FLINTN) < bufUniFactors.
length())
7256 if (NTLN.NumCols() < bufUniFactors.
length())
7258 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7267 if (NTLNe.NumCols() < bufUniFactors.
length())
7269 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
7278 int factorsFound= 0;
7282 result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
7284 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7286 factorsFound, beenInThres, M, Pi,
7287 diophant, symmetric, eval
7291 if (result.length() == nmod_mat_ncols (FLINTN))
7293 nmod_mat_clear (FLINTN);
7295 if (result.length() == NTLN.NumCols())
7299 return Union (result, smallFactors);
7304 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
7305 factorsFound, beenInThres, M, Pi,
7306 diophant, symmetric, eval
7309 if (result.length() == NTLNe.NumCols())
7312 return Union (result, smallFactors);
7321 for (CFListIterator i= result; i.hasItem(); i++)
7324 tmp1= mod (i.getItem(), y-eval);
7326 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7328 tmp2= mod (j.getItem(), y);
7342 long numCols, numRows;
7343 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7346 numCols= nmod_mat_ncols (FLINTN);
7347 numRows= nmod_mat_nrows (FLINTN);
7348 zeroOne= extractZeroOneVecs (FLINTN);
7350 numCols= NTLN.NumCols();
7351 numRows= NTLN.NumRows();
7352 zeroOne= extractZeroOneVecs (NTLN);
7357 numCols= NTLNe.NumCols();
7358 numRows= NTLNe.NumRows();
7359 zeroOne= extractZeroOneVecs (NTLNe);
7361 CFList bufBufUniFactors= bufUniFactors;
7364 CFList factorsConsidered;
7366 for (
int i= 0;
i < numCols;
i++)
7368 if (zeroOne [
i] == 0)
7370 iter= bufUniFactors;
7372 factorsConsidered=
CFList();
7373 for (
int j= 0;
j < numRows;
j++,
iter++)
7378 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
7397 for (iter2=
result; iter2.hasItem(); iter2++)
7399 tmp=
mod (iter2.getItem(),
y-
eval);
7403 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
7408 bufUniFactors= bufBufUniFactors;
7419 oldNumCols= nmod_mat_ncols (FLINTN);
7421 oldNumCols= NTLN.NumCols();
7424 oldNumCols, oldL,
l,
eval
7432 oldNumCols= nmod_mat_ncols (FLINTN);
7434 oldNumCols= NTLN.NumCols();
7443 oldNumCols= NTLNe.NumCols();
7455 nmod_mat_clear (FLINTN);
7475 nmod_mat_clear (FLINTN);
7482 nmod_mat_clear (FLINTN);
7485 alpha, degs, symmetric,
7525 if (
result.length()== nmod_mat_ncols (FLINTN))
7527 nmod_mat_clear (FLINTN);
7529 if (
result.length()== NTLN.NumCols())
7539 if (
result.length()== NTLNe.NumCols())
7552 liftBound,d,bounds,FLINTN,
7554 liftBound, d, bounds, NTLN,
7556 diophant,
M, Pi, bufQ,
eval
7562 liftBound, d, bounds,
7564 FLINTN, diophant,
M,
7572 liftBound, d, bounds,
7581 if (
result.length() == nmod_mat_ncols (FLINTN))
7583 nmod_mat_clear (FLINTN);
7585 if (
result.length() == NTLN.NumCols())
7595 if (
result.length() == NTLNe.NumCols())
7605 DEBOUTLN (cerr,
"lattice recombination failed");
7615 nmod_mat_clear (FLINTN);
7624 minBound= bounds[0];
7625 for (
int i= 1;
i < d;
i++)
7628 minBound=
tmin (minBound, bounds[
i]);
7631 if (minBound > 16 ||
result.length() == 0)
7648 degs,symmetric,
eval
7695 imPrimElemAlpha=
map (primElemAlpha,
alpha, bufEvaluation, gamma);
7703 imPrimElemAlpha, 1,
info.getGFName(),
true
7724 CFList bufUniFactors= uniFactors;
7744 int minBound= bounds[0];
7745 for (
int i= 1;
i < d;
i++)
7748 minBound=
tmin (minBound, bounds[
i]);
7760 bool success=
false;
7765 if (smallFactors.
length() > 0)
7767 if (smallFactors.
length() == 1)
7781 return smallFactors;
7808 return smallFactors;
7822 smallFactors.
append (tmp);
7823 return smallFactors;
7827 minBound= bounds[0];
7828 for (
int i= 1;
i < d;
i++)
7831 minBound=
tmin (minBound, bounds[
i]);
7847 smallFactors.
append (tmp);
7848 return smallFactors;
7857 nmod_mat_init (FLINTN, bufUniFactors.
length()-1, bufUniFactors.
length()-1,
7859 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7860 nmod_mat_entry (FLINTN,
i,
i)= 1;
7870 ident (NTLN, bufUniFactors.
length() - 1);
7882 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7887 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7896 minBound+1, bufUniFactors, FLINTN, diophant,
7902 minBound + 1, bufUniFactors, NTLN, diophant,
7909 "time to compute a reduced lattice: ");
7912 if (oldL > liftBound)
7915 nmod_mat_clear (FLINTN);
7930 nmod_mat_clear (FLINTN);
7944 int * factorsFoundIndex;
7947 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7948 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7950 factorsFoundIndex=
new int [NTLN.NumCols()];
7951 for (
long i= 0;
i < NTLN.NumCols();
i++)
7953 factorsFoundIndex[
i]= 0;
7955 int factorsFound= 0;
7960 factorsFound, factorsFoundIndex, FLINTN,
false,
info,
7964 if (
result.length() == nmod_mat_ncols (FLINTN))
7966 nmod_mat_clear (FLINTN);
7969 factorsFound, factorsFoundIndex, NTLN,
false,
info,
7973 if (
result.length() == NTLN.NumCols())
7976 delete [] factorsFoundIndex;
7981 delete [] factorsFoundIndex;
7985 int * factorsFoundIndex;
7987 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7988 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7990 factorsFoundIndex=
new int [NTLN.NumCols()];
7991 for (
long i= 0;
i < NTLN.NumCols();
i++)
7993 factorsFoundIndex[
i]= 0;
7995 int factorsFound= 0;
7999 factorsFound, factorsFoundIndex, FLINTN,
false,
8003 if (
result.length() == nmod_mat_ncols (FLINTN))
8005 nmod_mat_clear (FLINTN);
8008 factorsFound, factorsFoundIndex, NTLN,
false,
8012 if (
result.length() == NTLN.NumCols())
8015 delete [] factorsFoundIndex;
8019 delete [] factorsFoundIndex;
8023 bool beenInThres=
false;
8026 if (
l <= thres && bufUniFactors.
length() > nmod_mat_ncols (FLINTN))
8032 if (
l <= thres && bufUniFactors.
length() > NTLN.NumCols())
8043 int factorsFound= 0;
8047 factorsFound, beenInThres,
M, Pi,
8051 if (
result.length() == nmod_mat_ncols (FLINTN))
8053 nmod_mat_clear (FLINTN);
8056 factorsFound, beenInThres,
M, Pi,
8060 if (
result.length() == NTLN.NumCols())
8097 CFList bufBufUniFactors= bufUniFactors;
8100 CFList factorsConsidered;
8102 for (
int i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
8104 for (
int i= 0;
i < NTLN.NumCols();
i++)
8107 if (zeroOne [
i] == 0)
8109 iter= bufUniFactors;
8111 factorsConsidered=
CFList();
8113 for (
int j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
8115 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
8117 for (
int j= 0;
j < NTLN.NumRows();
j++,
iter++)
8133 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
8138 bufUniFactors= bufBufUniFactors;
8147 oldNumCols= nmod_mat_ncols (FLINTN);
8152 nmod_mat_clear (FLINTN);
8154 oldNumCols= NTLN.NumCols();
8190 if (
l/degMipo < liftBound)
8197 if (
result.length()== nmod_mat_ncols (FLINTN))
8199 nmod_mat_clear (FLINTN);
8205 if (
result.length()== NTLN.NumCols())
8217 liftBound, d,bounds,FLINTN,
8218 diophant,
M, Pi, bufQ,
8222 if (
result.length()== nmod_mat_ncols (FLINTN))
8224 nmod_mat_clear (FLINTN);
8227 liftBound, d, bounds, NTLN,
8228 diophant,
M, Pi, bufQ,
8232 if (
result.length()== NTLN.NumCols())
8243 nmod_mat_clear (FLINTN);
8246 DEBOUTLN (cerr,
"lattice recombination failed");
8260 smallFactors.
append (tmp);
8264 minBound= bounds[0];
8265 for (
int i= 1;
i < d;
i++)
8268 minBound=
tmin (minBound, bounds[
i]);
8271 if (minBound > 16 ||
result.length() == 0)
8315 int k=
info.getGFDegree();
8316 bool extension=
info.isInExtension();
8317 if (
A.isUnivariate())
8319 if (extension ==
false)
8340 A=
A/(contentAx*contentAy);
8341 CFList contentAxFactors, contentAyFactors;
8351 if (
A.inCoeffDomain())
8353 append (factors, contentAxFactors);
8354 append (factors, contentAyFactors);
8358 else if (
A.isUnivariate())
8361 append (factors, contentAxFactors);
8362 append (factors, contentAyFactors);
8383 bool derivXZero=
false;
8390 gcdDerivX=
gcd (
A, derivX);
8391 if (
degree (gcdDerivX) > 0)
8396 append (factorsG, contentAxFactors);
8397 append (factorsG, contentAyFactors);
8404 bool derivYZero=
false;
8411 gcdDerivY=
gcd (
A, derivY);
8412 if (
degree (gcdDerivY) > 0)
8417 append (factorsG, contentAxFactors);
8418 append (factorsG, contentAyFactors);
8433 derivXZero= derivYZero;
8455 int minBound= bounds[0];
8456 for (
int i= 1;
i < boundsLength;
i++)
8459 minBound=
tmin (minBound, bounds[
i]);
8464 int minBound2= bounds2[0];
8465 for (
int i= 1;
i < boundsLength2;
i++)
8467 if (bounds2[
i] != 0)
8468 minBound2=
tmin (minBound2, bounds2[
i]);
8474 CFList uniFactors, list, bufUniFactors;
8479 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8480 CFList bufUniFactors2, list2, uniFactors2;
8491 bool symmetric=
false;
8494 for (
int i= 0;
i < factorNums;
i++)
8500 if (!derivXZero && !fail2 && !symmetric)
8511 "time to find eval point wrt y: ");
8514 if (fail && (
i == 0))
8516 if (!derivXZero && !fail2 && !symmetric)
8518 bufEvaluation= bufEvaluation2;
8519 int dummy= subCheck2;
8520 subCheck2= subCheck1;
8525 bufAeval= bufAeval2;
8534 if (fail && (
i == 0))
8547 if (fail && (
i != 0))
8554 "time for univariate factorization over Fq: ");
8555 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8556 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8558 if (!derivXZero && !fail2 && !symmetric)
8563 "time for univariate factorization in y over Fq: ");
8564 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8565 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8568 if (bufUniFactors.
length() == 1 ||
8569 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8589 if (
i == 0 && !extension)
8595 if (subCheck > 1 && (subCheck1%subCheck == 0))
8598 subst (bufA, bufA, subCheck,
x);
8611 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8615 if (subCheck > 1 && (subCheck2%subCheck == 0))
8618 subst (bufA, bufA, subCheck,
y);
8634 if (!derivXZero && !fail2 && !symmetric)
8641 uniFactors= bufUniFactors;
8643 if (!derivXZero && !fail2 && !symmetric)
8646 evaluation2= bufEvaluation2;
8647 uniFactors2= bufUniFactors2;
8654 if (!derivXZero && !fail2 && !symmetric)
8659 uniFactors2= bufUniFactors2;
8661 evaluation2= bufEvaluation2;
8666 uniFactors= bufUniFactors;
8671 list.
append (bufEvaluation);
8672 if (!derivXZero && !fail2 && !symmetric)
8673 list2.
append (bufEvaluation2);
8676 "total time for univariate factorizations: ");
8678 if (!derivXZero && !fail2 && !symmetric)
8680 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8685 uniFactors= uniFactors2;
8717 minBound= minBound2;
8723 "time to shift eval to zero: ");
8729 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8731 if ((GF && !extension) || (GF && extension &&
k != 1))
8733 bool earlySuccess=
false;
8737 (
A, earlySuccess, earlyFactors, degs, liftBound,
8740 "time for bivariate hensel lifting over Fq: ");
8741 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8753 "time for naive bivariate factor recombi over Fq: ");
8756 factors=
Union (earlyFactors, factors);
8757 else if (!earlySuccess && degs.
getLength() == 1)
8758 factors= earlyFactors;
8768 factors=
Union (lll, factors);
8774 factors=
Union (lll, factors);
8776 else if (!extension && (
alpha !=
x || GF))
8780 factors=
Union (lll, factors);
8783 "time to bivar lift and LLL recombi over Fq: ");
8784 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8788 bool earlySuccess=
false;
8792 (
A, earlySuccess, earlyFactors, degs, liftBound,
8795 "time for bivar hensel lifting over Fq: ");
8796 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8804 "time for small subset naive recombi over Fq: ");
8806 int oldUniFactorsLength= uniFactors.
length();
8827 "time to increase precision: ");
8828 factors=
Union (factors, tmp);
8830 && uniFactors.
length() != oldUniFactorsLength)
8878 int oldUniFactorsLength= uniFactors.
length();
8887 info2, source, dest, liftBound
8889 factors=
Union (factors, tmp);
8891 && uniFactors.
length() != oldUniFactorsLength)
8908 factors=
Union (earlyFactors, factors);
8909 else if (!earlySuccess && degs.
getLength() == 1)
8910 factors= earlyFactors;
8934 int k=
info.getGFDegree();
8935 char cGFName=
info.getGFName();
8943 bool extension=
true;
8969 else if (!GF && (
alpha !=
x))
8987 bool primFail=
false;
8990 ASSERT (!primFail,
"failure in integer factorizer");
9007 bool primFail=
false;
9009 ASSERT (!primFail,
"failure in integer factorizer");
9019 bufA=
mapUp (bufA,
beta,
v, delta, imPrimElem, source, dest);
9031 bool extension=
true;
9035 if (
ipower (
p, extensionDeg) < (1<<16))
9061 if (
ipower (
p, 2*extensionDeg) < (1<<16))
9077 bool primFail=
false;
9080 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
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
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)
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 "Factoring multivariate polynomials over a ...
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 "Factoring multivariate 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 "Factoring multivariate 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...
for(j=0;j< factors.length();j++)
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.
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)
void prune(Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables