46#include "flint/nmod_poly_factor.h"
47#include "flint/fq_nmod_poly_factor.h"
66 else if (L.length() == 1)
67 return mod (L.getFirst()(0, 1) ,
M);
68 else if (L.length() == 2)
69 return mod (
mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1),
b),
M);
76 for (
int j= 1;
j <=
l;
j++,
i++)
85#if defined(HAVE_NTL) || defined(HAVE_FLINT)
141 if (
find (list, random))
continue;
145 if (!
find (list, random))
151 if (!
find (list, random))
155 }
while (
find (list, random));
160#if defined(HAVE_NTL) || defined(HAVE_FLINT)
165 if (
A.inCoeffDomain())
168 "univariate polynomial expected or constant expected");
184#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
185 nmod_poly_t FLINTmipo, leadingCoeff;
187 fq_nmod_poly_t FLINTA;
188 fq_nmod_poly_factor_t FLINTFactorsA;
196 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
198 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
201 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
206 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
221 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
222 zz_pE multi= to_zz_pE (1);
234 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
235 GF2E multi= to_GF2E (1);
257#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
258 nmod_poly_t FLINTmipo, leadingCoeff;
260 fq_nmod_poly_t FLINTA;
261 fq_nmod_poly_factor_t FLINTFactorsA;
269 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
271 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
274 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
279 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
294 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
295 zz_pE multi= to_zz_pE (1);
307 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
308 GF2E multi= to_GF2E (1);
323 nmod_poly_factor_t
result;
324 nmod_poly_factor_init (
result);
325 mp_limb_t leadingCoeff= nmod_poly_factor (
result, FLINTA);
327 if (factorsA.
getFirst().factor().inCoeffDomain())
329 nmod_poly_factor_clear (
result);
346 vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
347 zz_p multi= to_zz_p (1);
354 vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
355 GF2 multi= to_GF2 (1);
368#if defined(HAVE_NTL) || defined(HAVE_FLINT)
377 if (factors.
length() == 0)
403 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, M) == F " <<
418 int *
v=
new int [
T.length()];
419 for (
int i= 0;
i <
T.length();
i++)
427 bool nosubset=
false;
429 bool trueFactor=
false;
432 while (
T.length() >= 2*
s &&
s <= thres)
434 while (nosubset ==
false)
462 if (!degs.
find (subsetDeg))
507 buf0=
buf (0,
x)*LCBuf;
513 if (
T.length() < 2*
s ||
T.length() ==
s ||
543 if (
T.length() < 2*
s ||
T.length() ==
s)
561 for (
int i= 0;
i <
T.length();
i++)
565 if (
T.length() < 2*
s)
594 if (factors.
length() == 0)
610 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
613 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
627 int *
v=
new int [
T.length()];
628 for (
int i= 0;
i <
T.length();
i++)
630 bool nosubset=
false;
645 while (
T.length() >= 2*
s &&
s <= thres)
647 while (nosubset ==
false)
675 if (!degs.
find (subsetDeg))
709 if (!
Lc (
g).inBaseDomain())
726 denom /=
gcd (denom, denQuot);
742 if (
T.length() < 2*
s ||
T.length() ==
s ||
769 if (
T.length() < 2*
s ||
T.length() ==
s)
785 for (
int i= 0;
i <
T.length();
i++)
790 if (
T.length() < 2*
s)
807#if defined(HAVE_NTL) || defined(HAVE_FLINT)
832 #if defined(HAVE_FLINT)
833 nmod_poly_t Irredpoly;
835 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom,
i*
m+1);
837 #elif defined(HAVE_NTL)
844 BuildIrred (NTLIrredpoly,
i*
m);
855 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
911 if (!
Lc (
g).inBaseDomain())
922 factorsFoundIndex[
l]= 1;
948 if (!
buf.inCoeffDomain())
962 adaptedLiftBound= d + 1;
963 if (adaptedLiftBound < deg)
974 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
980 factorsFoundIndex, degs, success, deg,
eval,
b,
den);
985 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
1002 adaptedLiftBound= 0;
1003 bool trueFactor=
false;
1028 factorsFoundIndex[
l]= 1;
1040 factorsFoundIndex[
l]= 1;
1059 if (!
buf.inCoeffDomain())
1072 adaptedLiftBound= d + 1;
1073 if (adaptedLiftBound < deg)
1092 for (
int i= 0;
i < sizeOfRightSide;
i++)
1098 if (
i.exp() < degreeLC)
1105 ASSERT (
j > 1,
"j > 1 expected" );
1107 int*
result =
new int [
j - 1];
1108 sizeOfOutput=
j - 1;
1124 int sizeOfNewtonPoly;
1126 int sizeOfRightSide;
1127 int * rightSide=
getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1130 delete [] rightSide;
1131 for (
int i= 0;
i < sizeOfNewtonPoly;
i++)
1132 delete [] newtonPolyg[
i];
1133 delete [] newtonPolyg;
1144 if (factorsFoundIndex[
i] == 1)
1152#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1172 CFList bufUniFactors= uniFactors;
1175 if (!
Lc (
A).inBaseDomain())
1190 bool mipoHasDen=
false;
1195 lcA0=
lc (
A (0, 2));
1196 A *=
b.inverse (lcA0);
1217 earlySuccess=
false;
1218 int newLiftBound= 0;
1220 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
1222 int * factorsFoundIndex=
new int [uniFactors.
length()];
1223 for (
int i= 0;
i < uniFactors.
length();
i++)
1224 factorsFoundIndex [
i]= 0;
1228 if (smallFactorDeg >= liftBound ||
degree (
A,
y) <= 4)
1230 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1232 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1240 bufBufUniFactors= bufUniFactors;
1251 factorsFoundIndex, degs, earlySuccess,
1255 factorsFoundIndex, degs, earlySuccess,
1260 factorsFoundIndex, degs, earlySuccess,
info,
1261 eval, smallFactorDeg);
1262 if (degs.
getLength() > 1 && !earlySuccess &&
1263 smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1265 if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1269 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant,
M,
b);
1272 bufBufUniFactors= bufUniFactors;
1280 factorsFoundIndex, degs, earlySuccess,
1281 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1284 factorsFoundIndex, degs, earlySuccess,
1285 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1289 factorsFoundIndex, degs, earlySuccess,
info,
1290 eval, liftPre[sizeOfLiftPre-1] + 1);
1293 else if (earlySuccess)
1294 liftBound= newLiftBound;
1296 int i= sizeOfLiftPre - 1;
1297 while (degs.
getLength() > 1 && !earlySuccess &&
i - 1 >= 0)
1299 if (newLiftBound >= liftPre[
i] + 1)
1303 liftPre[
i-1] + 1, Pi, diophant,
M,
b);
1306 bufBufUniFactors= bufUniFactors;
1314 factorsFoundIndex, degs, earlySuccess,
1318 factorsFoundIndex, degs, earlySuccess,
1323 factorsFoundIndex, degs, earlySuccess,
info,
1324 eval, liftPre[
i-1] + 1);
1328 liftBound= newLiftBound;
1334 liftBound= newLiftBound;
1339 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1347 bufBufUniFactors= bufUniFactors;
1357 factorsFoundIndex, degs, earlySuccess,
1361 factorsFoundIndex, degs, earlySuccess,
1366 factorsFoundIndex, degs, earlySuccess,
info,
1367 eval, smallFactorDeg);
1369 while ((
degree (
A,
y)/4)*
i + 4 <= smallFactorDeg)
1372 if (degs.
getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1376 dummy, Pi, diophant,
M,
b);
1379 bufBufUniFactors= bufUniFactors;
1387 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1391 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1396 factorsFoundIndex, degs, earlySuccess,
info,
1399 while (degs.
getLength() > 1 && !earlySuccess &&
i < 4)
1401 if (newLiftBound >= dummy)
1406 dummy, Pi, diophant,
M,
b);
1409 bufBufUniFactors= bufUniFactors;
1417 factorsFoundIndex, degs, earlySuccess, dummy,
1421 factorsFoundIndex, degs, earlySuccess, dummy,
1426 factorsFoundIndex, degs, earlySuccess,
info,
1431 liftBound= newLiftBound;
1437 liftBound= newLiftBound;
1448 delete [] factorsFoundIndex;
1451 return bufUniFactors;
1473 for (
i = 1;
i <=
M.NumRows();
i++)
1476 for (
j = 1;
j <=
M.NumCols();
j++)
1492 for (
i = 1;
i <= nmod_mat_nrows(
M);
i++)
1495 for (
j = 1;
j <= nmod_mat_ncols (
M);
j++)
1497 if (!(nmod_mat_entry (
M,
i-1,
j-1)==0))
1511 for (
i = 1;
i <=
M.NumRows();
i++)
1514 for (
j = 1;
j <=
M.NumCols();
j++)
1530 bool nonZeroOne=
false;
1531 int *
result=
new int [
M.NumCols()];
1532 for (
i = 1;
i <=
M.NumCols();
i++)
1534 for (
j = 1;
j <=
M.NumRows();
j++)
1556 bool nonZeroOne=
false;
1557 int *
result=
new int [nmod_mat_ncols (
M)];
1558 for (
i = 0;
i < nmod_mat_ncols (
M);
i++)
1560 for (
j = 0;
j < nmod_mat_nrows (
M);
j++)
1562 if (!((nmod_mat_entry (
M,
j,
i) == 1) || (nmod_mat_entry (
M,
j,
i) == 0)))
1582 bool nonZeroOne=
false;
1583 int *
result=
new int [
M.NumCols()];
1584 for (
i = 1;
i <=
M.NumCols();
i++)
1586 for (
j = 1;
j <=
M.NumRows();
j++)
1607 factors,
const int liftBound,
int& factorsFound,
int*&
1616 if (factors.
length() == 2)
1628 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1639 for (
long i= 1;
i <=
N.NumCols();
i++)
1641 if (factorsFoundIndex [
i - 1] == 1)
1657 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1668 factorsFoundIndex[
i - 1]= 1;
1676 if (factorsFound + 1 ==
N.NumCols())
1678 reconstructedFactors.
append (bufF);
1683 if (reconstructedFactors.
length() != 0)
1691 factors,
const int liftBound,
int& factorsFound,
int*&
1700 if (factors.
length() == 2)
1712 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1723 for (
long i= 1;
i <=
N.NumCols();
i++)
1725 if (factorsFoundIndex [
i - 1] == 1)
1741 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1752 factorsFoundIndex[
i - 1]= 1;
1760 if (factorsFound + 1 ==
N.NumCols())
1762 reconstructedFactors.
append (bufF);
1767 if (reconstructedFactors.
length() != 0)
1775 factors,
const int liftBound,
int& factorsFound,
int*&
1784 if (factors.
length() == 2)
1796 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1807 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
1809 if (factorsFoundIndex [
i] == 1)
1825 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
1827 if (!(nmod_mat_entry (
N,
j,
i) == 0))
1836 factorsFoundIndex[
i]= 1;
1844 if (factorsFound + 1 == nmod_mat_ncols (
N))
1847 reconstructedFactors.
append (bufF);
1851 if (reconstructedFactors.
length() != 0)
1868 CFList bufFactors= factors;
1870 for (
long i= 1;
i <=
N.NumCols();
i++)
1872 if (zeroOneVecs [
i - 1] == 0)
1876 factorsConsidered=
CFList();
1877 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1892 bufFactors=
Difference (bufFactors, factorsConsidered);
1897 factors= bufFactors;
1902 factors= bufFactors;
1910 int precision,
const mat_zz_pE&
N
1919 CFList bufFactors= factors;
1920 CFList factorsConsidered;
1922 for (
long i= 1;
i <=
N.NumCols();
i++)
1924 if (zeroOneVecs [
i - 1] == 0)
1928 factorsConsidered=
CFList();
1929 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1945 bufFactors=
Difference (bufFactors, factorsConsidered);
1950 factors= bufFactors;
1955 factors= bufFactors;
1977 CFList bufFactors= factors;
1978 CFList factorsConsidered;
1981 for (
long i= 1;
i <=
N.NumCols();
i++)
1983 if (zeroOneVecs [
i - 1] == 0)
1987 factorsConsidered=
CFList();
1988 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2009 bufFactors=
Difference (bufFactors, factorsConsidered);
2024 bufFactors=
Difference (bufFactors, factorsConsidered);
2031 factors= bufFactors;
2036 factors= bufFactors;
2058 CFList bufFactors= factors;
2059 CFList factorsConsidered;
2062 for (
long i= 0;
i < nmod_mat_ncols(
N);
i++)
2064 if (zeroOneVecs [
i] == 0)
2068 factorsConsidered=
CFList();
2069 for (
long j= 0;
j < nmod_mat_nrows(
N);
j++,
iter++)
2071 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2090 bufFactors=
Difference (bufFactors, factorsConsidered);
2105 bufFactors=
Difference (bufFactors, factorsConsidered);
2112 factors= bufFactors;
2117 factors= bufFactors;
2133 CFList bufFactors= factors;
2134 CFList factorsConsidered;
2136 for (
long i= 1;
i <=
N.NumCols();
i++)
2138 if (zeroOneVecs [
i - 1] == 0)
2142 factorsConsidered=
CFList();
2143 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2158 bufFactors=
Difference (bufFactors, factorsConsidered);
2163 factors= bufFactors;
2168 factors= bufFactors;
2184 CFList bufFactors= factors;
2185 CFList factorsConsidered;
2187 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2189 if (zeroOneVecs [
i] == 0)
2193 factorsConsidered=
CFList();
2194 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2196 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2209 bufFactors=
Difference (bufFactors, factorsConsidered);
2214 factors= bufFactors;
2219 factors= bufFactors;
2227 CFList& factors,
const int liftBound,
int& factorsFound,
2228 int*& factorsFoundIndex, mat_zz_p&
N,
bool beenInThres,
2241 if (factors.
length() == 2)
2251 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2283 for (
long i= 1;
i <=
N.NumCols();
i++)
2285 if (factorsFoundIndex [
i - 1] == 1)
2301 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2317 factorsFoundIndex[
i - 1]= 1;
2332 factorsFoundIndex[
i - 1]= 1;
2343 if (factorsFound + 1 ==
N.NumCols())
2347 reconstructedFactors.
append (tmp);
2357 CFList& factors,
const int liftBound,
int& factorsFound,
2358 int*& factorsFoundIndex, nmod_mat_t
N,
bool beenInThres,
2371 if (factors.
length() == 2)
2381 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2413 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2415 if (factorsFoundIndex [
i] == 1)
2431 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2433 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2447 factorsFoundIndex[
i]= 1;
2462 factorsFoundIndex[
i]= 1;
2473 if (factorsFound + 1 == nmod_mat_nrows (
N))
2477 reconstructedFactors.
append (tmp);
2488 start,
int liftBound,
int minBound,
CFList& factors,
2495 bool wasInBounds=
false;
2496 bool hitBound=
false;
2497 int l= (minBound+1)*2;
2500 bool reduced=
false;
2501 mat_zz_p NTLK, *NTLC;
2507 while (
l <= liftBound)
2523 "time to lift in compute lattice: ");
2531 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2540 "time to compute logarithmic derivative: ");
2542 for (
int i= 0;
i < sizeBounds;
i++)
2544 if (bounds [
i] + 1 <=
l/2)
2547 int k=
tmin (bounds [
i] + 1,
l/2);
2549 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2551 if (
A[ii].
size() - 1 >=
i)
2559 transpose (NTLK, NTLK);
2560 kernel (NTLK, NTLK);
2561 transpose (NTLK, NTLK);
2565 if (NTLN.NumCols() == 1)
2613 start,
int liftBound,
int minBound,
CFList& factors,
2620 bool wasInBounds=
false;
2621 bool hitBound=
false;
2622 int l= (minBound+1)*2;
2625 bool reduced=
false;
2627 nmod_mat_t FLINTK, FLINTC, null;
2633 while (
l <= liftBound)
2649 "time to lift in compute lattice: ");
2657 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2666 "time to compute logarithmic derivative: ");
2668 for (
int i= 0;
i < sizeBounds;
i++)
2670 if (bounds [
i] + 1 <=
l/2)
2673 int k=
tmin (bounds [
i] + 1,
l/2);
2675 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2677 if (
A[ii].
size() - 1 >=
i)
2685 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2687 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2688 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2690 rank= nmod_mat_nullspace (null, FLINTK);
2691 nmod_mat_clear (FLINTK);
2692 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2693 nmod_mat_clear (FLINTC);
2694 nmod_mat_init_set (FLINTC, FLINTN);
2695 nmod_mat_clear (FLINTN);
2696 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2698 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
2700 nmod_mat_clear (FLINTC);
2701 nmod_mat_window_clear (FLINTK);
2702 nmod_mat_clear (null);
2703 if (nmod_mat_ncols (FLINTN) == 1)
2708 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
2752 int liftBound,
int minBound,
int start,
CFList&
2753 factors, mat_zz_p& NTLN,
CFList& diophant,
2762 bool wasInBounds=
false;
2763 bool hitBound=
false;
2774 int l= ((minBound+1)/degMipo+1)*2;
2779 bool reduced=
false;
2786 mat_zz_p* NTLMat, *NTLC, NTLK;
2788 while (
l <= liftBound)
2804 "time to lift in compute lattice: ");
2813 for (
int i= 0;
i <
l*degMipo;
i++)
2816 imBasis= imBasis (
power (
y, degMipo),
y);
2817 imBasis= imBasis (
y, gamma);
2824 *NTLMat= inv (*NTLMat);
2834 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2843 "time to compute logarithmic derivative: ");
2845 for (
int i= 0;
i < sizeBounds;
i++)
2847 if (bounds [
i] + 1 <= (
l/2)*degMipo)
2850 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
2853 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2855 if (
A[ii].
size() - 1 >=
i)
2863 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2872 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2888 transpose (NTLK, NTLK);
2889 kernel (NTLK, NTLK);
2890 transpose (NTLK, NTLK);
2897 if (NTLN.NumCols() == 1)
2912 if (NTLN.NumCols() == 1)
2951 int liftBound,
int minBound,
int start,
CFList&
2952 factors, nmod_mat_t FLINTN,
CFList& diophant,
2961 bool wasInBounds=
false;
2962 bool hitBound=
false;
2973 int l= ((minBound+1)/degMipo+1)*2;
2978 bool reduced=
false;
2986 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
2988 while (
l <= liftBound)
3010 for (
int i= 0;
i <
l*degMipo;
i++)
3013 imBasis= imBasis (
power (
y, degMipo),
y);
3014 imBasis= imBasis (
y, gamma);
3021 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3023 nmod_mat_inv (FLINTMatInv, FLINTMat);
3032 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3041 for (
int i= 0;
i < sizeBounds;
i++)
3043 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3046 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3049 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3051 if (
A[ii].
size() - 1 >=
i)
3059 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3068 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3083 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3085 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3086 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3088 rank= nmod_mat_nullspace (null, FLINTK);
3089 nmod_mat_clear (FLINTK);
3090 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3091 nmod_mat_clear (FLINTC);
3092 nmod_mat_init_set (FLINTC, FLINTN);
3093 nmod_mat_clear (FLINTN);
3094 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3096 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3098 nmod_mat_clear (FLINTC);
3099 nmod_mat_window_clear (FLINTK);
3100 nmod_mat_clear (null);
3105 if (nmod_mat_ncols (FLINTN) == 1)
3118 nmod_mat_clear (FLINTMat);
3119 nmod_mat_clear (FLINTMatInv);
3121 if (nmod_mat_ncols (FLINTN) == 1)
3160 int start,
int liftBound,
int minBound,
CFList& factors,
3167 bool wasInBounds=
false;
3168 bool hitBound=
false;
3169 int l= (minBound+1)*2;
3172 bool reduced=
false;
3174 mat_zz_pE* NTLC, NTLK;
3179 while (
l <= liftBound)
3195 "time to lift in compute lattice: ");
3203 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3205 if (
l == (minBound+1)*2)
3217 "time to compute logarithmic derivative: ");
3219 for (
int i= 0;
i < sizeBounds;
i++)
3221 if (bounds [
i] + 1 <=
l/2)
3224 int k=
tmin (bounds [
i] + 1,
l/2);
3226 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3229 if (
A[ii].
size() - 1 >=
i)
3238 transpose (NTLK, NTLK);
3239 kernel (NTLK, NTLK);
3240 transpose (NTLK, NTLK);
3244 if (NTLN.NumCols() == 1)
3257 if (NTLN.NumCols() == 1)
3295 int start,
int liftBound,
int minBound,
CFList&
3296 factors, nmod_mat_t FLINTN,
CFList& diophant,
3303 int start,
int liftBound,
int minBound,
CFList&
3312 bool wasInBounds=
false;
3313 int l= (minBound+1)*2;
3316 bool hitBound=
false;
3318 bool reduced=
false;
3324 nmod_mat_t FLINTC, FLINTK, null;
3326 mat_zz_p* NTLC, NTLK;
3330 while (
l <= liftBound)
3346 "time to lift in compute lattice: ");
3354 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3356 if (
l == (minBound+1)*2)
3368 "time to compute logarithmic derivative: ");
3370 for (
int i= 0;
i < sizeBounds;
i++)
3372 if (bounds [
i] + 1 <=
l/2)
3375 int k=
tmin (bounds [
i] + 1,
l/2);
3377 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3379 if (
A[ii].
size() - 1 >=
i)
3388 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3390 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3391 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3393 rank= nmod_mat_nullspace (null, FLINTK);
3394 nmod_mat_clear (FLINTK);
3395 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3396 nmod_mat_clear (FLINTC);
3397 nmod_mat_init_set (FLINTC, FLINTN);
3398 nmod_mat_clear (FLINTN);
3399 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3401 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3403 nmod_mat_clear (FLINTC);
3404 nmod_mat_window_clear (FLINTK);
3405 nmod_mat_clear (null);
3409 transpose (NTLK, NTLK);
3410 kernel (NTLK, NTLK);
3411 transpose (NTLK, NTLK);
3417 if (nmod_mat_nrows (FLINTN) == 1)
3419 if (NTLN.NumCols() == 1)
3426 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
3438 if (nmod_mat_ncols (FLINTN) == 1)
3440 if (NTLN.NumCols() == 1)
3478 int oldNumCols,
int oldL,
int precision,
3498 for (
long i=factors.
length()-1;
i >= 0;
i--)
3499 nmod_mat_entry (FLINTN,
i,
i)= 1;
3502 ident (NTLN, factors.
length());
3504 int minBound= bounds[0];
3505 for (
int i= 1;
i < d;
i++)
3508 minBound=
tmin (minBound, bounds[
i]);
3510 int l=
tmax (2*(minBound + 1), oldL);
3513 bool useOldQs=
false;
3514 bool hitBound=
false;
3520 nmod_mat_t FLINTC, FLINTK, null;
3522 mat_zz_p* NTLC, NTLK;
3525 while (
l <= precision)
3531 for (
int i= 0;
i < factors.
length();
i++,
j++)
3538 for (
int i= 0;
i < factors.
length();
i++,
j++)
3542 for (
int i= 0;
i < d;
i++)
3544 if (bounds [
i] + 1 <=
l/2)
3546 int k=
tmin (bounds [
i] + 1,
l/2);
3548 for (
int ii= 0; ii < factors.
length(); ii++)
3550 if (
A[ii].
size() - 1 >=
i)
3558 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3560 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3561 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3563 rank= nmod_mat_nullspace (null, FLINTK);
3564 nmod_mat_clear (FLINTK);
3565 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3566 nmod_mat_clear (FLINTC);
3567 nmod_mat_init_set (FLINTC, FLINTN);
3568 nmod_mat_clear (FLINTN);
3569 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3571 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3573 nmod_mat_clear (FLINTC);
3574 nmod_mat_window_clear (FLINTK);
3575 nmod_mat_clear (null);
3579 transpose (NTLK, NTLK);
3580 kernel (NTLK, NTLK);
3581 transpose (NTLK, NTLK);
3586 if (nmod_mat_ncols (FLINTN) == 1)
3588 nmod_mat_clear (FLINTN);
3590 if (NTLN.NumCols() == 1)
3603 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3607 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
3608 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
3610 if (NTLN.NumCols() < oldNumCols - factorsFound)
3614 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3615 for (
long i= 0;
i < NTLN.NumCols();
i++)
3617 factorsFoundIndex[
i]= 0;
3618 int factorsFound2= 0;
3623 factorsFoundIndex, FLINTN,
eval,
false
3625 if (
result.length() == nmod_mat_ncols (FLINTN))
3627 nmod_mat_clear (FLINTN);
3630 factorsFoundIndex, NTLN,
eval,
false
3632 if (
result.length() == NTLN.NumCols())
3635 delete [] factorsFoundIndex;
3641 delete [] factorsFoundIndex;
3643 else if (
l == precision)
3649 nmod_mat_clear (FLINTN);
3676 nmod_mat_clear (FLINTN);
3687 int oldNumCols,
int oldL,
const Variable&,
3705 ident (NTLN, factors.
length());
3706 int minBound= bounds[0];
3707 for (
int i= 1;
i < d;
i++)
3710 minBound=
tmin (minBound, bounds[
i]);
3712 int l=
tmax (2*(minBound + 1), oldL);
3715 bool useOldQs=
false;
3716 bool hitBound=
false;
3719 mat_zz_pE* NTLC, NTLK;
3722 while (
l <= precision)
3728 for (
int i= 0;
i < factors.
length();
i++,
j++)
3735 for (
int i= 0;
i < factors.
length();
i++,
j++)
3739 for (
int i= 0;
i < d;
i++)
3741 if (bounds [
i] + 1 <=
l/2)
3743 int k=
tmin (bounds [
i] + 1,
l/2);
3745 for (
int ii= 0; ii < factors.
length(); ii++)
3747 if (
A[ii].
size() - 1 >=
i)
3755 transpose (NTLK, NTLK);
3756 kernel (NTLK, NTLK);
3757 transpose (NTLK, NTLK);
3760 if (NTLN.NumCols() == 1)
3771 if (NTLN.NumCols() < oldNumCols - factorsFound)
3775 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3776 for (
long i= 0;
i < NTLN.NumCols();
i++)
3777 factorsFoundIndex[
i]= 0;
3778 int factorsFound2= 0;
3782 factorsFoundIndex, NTLN,
eval,
false);
3783 if (
result.length() == NTLN.NumCols())
3785 delete [] factorsFoundIndex;
3791 delete [] factorsFoundIndex;
3793 else if (
l == precision)
3856 for (
long i=factors.
length()-1;
i >= 0;
i--)
3857 nmod_mat_entry (FLINTN,
i,
i)= 1;
3865 ident (NTLN, factors.
length());
3867 int minBound= bounds[0];
3868 for (
int i= 1;
i < d;
i++)
3871 minBound=
tmin (minBound, bounds[
i]);
3873 int l=
tmax (oldL, 2*((minBound+1)/degMipo+1));
3876 bool useOldQs=
false;
3877 bool hitBound=
false;
3888 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
3890 mat_zz_p* NTLMat,*NTLC, NTLK;
3893 while (
l <= precision)
3900 for (
int i= 0;
i <
l*degMipo;
i++)
3903 imBasis= imBasis (
power (
y, degMipo),
y);
3904 imBasis= imBasis (
y, gamma);
3912 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3914 nmod_mat_inv (FLINTMatInv, FLINTMat);
3917 *NTLMat= inv (*NTLMat);
3926 for (
int i= 0;
i < factors.
length();
i++,
j++)
3933 for (
int i= 0;
i < factors.
length();
i++,
j++)
3937 for (
int i= 0;
i < d;
i++)
3939 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3941 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3943 for (
int ii= 0; ii < factors.
length(); ii++)
3945 if (
A[ii].
size() - 1 >=
i)
3953 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3966 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3986 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3988 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3989 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3991 rank= nmod_mat_nullspace (null, FLINTK);
3992 nmod_mat_clear (FLINTK);
3993 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3994 nmod_mat_clear (FLINTC);
3995 nmod_mat_init_set (FLINTC, FLINTN);
3996 nmod_mat_clear (FLINTN);
3997 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3999 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4001 nmod_mat_clear (FLINTC);
4002 nmod_mat_window_clear (FLINTK);
4003 nmod_mat_clear (null);
4007 transpose (NTLK, NTLK);
4008 kernel (NTLK, NTLK);
4009 transpose (NTLK, NTLK);
4018 if (nmod_mat_ncols (FLINTN) == 1)
4020 nmod_mat_clear (FLINTMat);
4021 nmod_mat_clear (FLINTMatInv);
4022 nmod_mat_clear (FLINTN);
4024 if (NTLN.NumCols() == 1)
4041 nmod_mat_clear (FLINTMat);
4042 nmod_mat_clear (FLINTMatInv);
4048 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4052 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4053 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4055 if (NTLN.NumCols() < oldNumCols - factorsFound)
4059 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4060 for (
long i= 0;
i < NTLN.NumCols();
i++)
4062 factorsFoundIndex[
i]= 0;
4063 int factorsFound2= 0;
4070 if (
result.length() == nmod_mat_ncols (FLINTN))
4072 nmod_mat_clear (FLINTN);
4077 if (
result.length() == NTLN.NumCols())
4080 delete [] factorsFoundIndex;
4086 delete [] factorsFoundIndex;
4088 else if (
l == precision)
4096 nmod_mat_clear (FLINTN);
4126 nmod_mat_clear (FLINTN);
4157 ident (NTLN, factors.
length());
4158 int minBound= bounds[0];
4159 for (
int i= 1;
i < d;
i++)
4162 minBound=
tmin (minBound, bounds[
i]);
4164 int l=
tmin (2*(minBound + 1), precision);
4167 bool useOldQs=
false;
4168 bool hitBound=
false;
4172 mat_zz_pE* NTLC, NTLK;
4175 while (
l <= precision)
4181 for (
int i= 0;
i < factors.
length();
i++,
j++)
4186 for (
int i= 0;
i < factors.
length();
i++,
j++)
4190 for (
int i= 0;
i < d;
i++)
4192 if (bounds [
i] + 1 <=
l/2)
4194 int k=
tmin (bounds [
i] + 1,
l/2);
4196 for (
int ii= 0; ii < factors.
length(); ii++)
4198 if (
A[ii].
size() - 1 >=
i)
4206 transpose (NTLK, NTLK);
4207 kernel (NTLK, NTLK);
4208 transpose (NTLK, NTLK);
4212 if (NTLN.NumCols() == 1)
4225 CFList bufFactors= factors;
4229 if (
result.length() != NTLN.NumCols() &&
l != precision)
4230 factors= bufFactors;
4231 if (
result.length() == NTLN.NumCols())
4291 for (
long i=factors.
length()-1;
i >= 0;
i--)
4292 nmod_mat_entry (FLINTN,
i,
i)= 1;
4295 ident (NTLN, factors.
length());
4297 int minBound= bounds[0];
4298 for (
int i= 1;
i < d;
i++)
4301 minBound=
tmin (minBound, bounds[
i]);
4303 int l=
tmax (2*(minBound + 1), oldL);
4306 bool useOldQs=
false;
4307 bool hitBound=
false;
4312 nmod_mat_t FLINTC, FLINTK, null;
4314 mat_zz_p* NTLC, NTLK;
4318 while (
l <= precision)
4324 for (
int i= 0;
i < factors.
length();
i++,
j++)
4331 for (
int i= 0;
i < factors.
length();
i++,
j++)
4335 for (
int i= 0;
i < d;
i++)
4337 if (bounds [
i] + 1 <=
l/2)
4339 int k=
tmin (bounds [
i] + 1,
l/2);
4341 for (
int ii= 0; ii < factors.
length(); ii++)
4343 if (
A[ii].
size() - 1 >=
i)
4351 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4353 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4354 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4356 rank= nmod_mat_nullspace (null, FLINTK);
4357 nmod_mat_clear (FLINTK);
4358 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4359 nmod_mat_clear (FLINTC);
4360 nmod_mat_init_set (FLINTC, FLINTN);
4361 nmod_mat_clear (FLINTN);
4362 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4364 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4366 nmod_mat_clear (FLINTC);
4367 nmod_mat_window_clear (FLINTK);
4368 nmod_mat_clear (null);
4372 transpose (NTLK, NTLK);
4373 kernel (NTLK, NTLK);
4374 transpose (NTLK, NTLK);
4379 if (nmod_mat_ncols (FLINTN) == 1)
4381 nmod_mat_clear (FLINTN);
4383 if (NTLN.NumCols() == 1)
4396 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4400 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4401 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4403 if (NTLN.NumCols() < oldNumCols - factorsFound)
4407 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4408 for (
long i= 0;
i < NTLN.NumCols();
i++)
4410 factorsFoundIndex[
i]= 0;
4411 int factorsFound2= 0;
4416 factorsFoundIndex, FLINTN,
eval,
false
4418 if (
result.length() == nmod_mat_ncols (FLINTN))
4420 nmod_mat_clear (FLINTN);
4423 factorsFoundIndex, NTLN,
eval,
false
4425 if (
result.length() == NTLN.NumCols())
4428 delete [] factorsFoundIndex;
4434 delete [] factorsFoundIndex;
4436 else if (
l == precision)
4442 nmod_mat_clear (FLINTN);
4469 nmod_mat_clear (FLINTN);
4481 l,
int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
4487 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
4495 bool hitBound=
false;
4497 if (nmod_mat_nrows (FLINTN) != factors.
length())
4499 nmod_mat_clear (FLINTN);
4501 for (
long i=factors.
length()-1;
i >= 0;
i--)
4502 nmod_mat_entry (FLINTN,
i,
i)= 1;
4506 if (NTLN.NumRows() != factors.
length())
4508 ident (NTLN, factors.
length());
4512 bool useOldQs=
false;
4518 nmod_mat_t FLINTC, FLINTK, null;
4520 mat_zz_p* NTLC, NTLK;
4531 for (
int i= 0;
i < factors.
length();
i++,
j++)
4538 for (
int i= 0;
i < factors.
length();
i++,
j++)
4543 for (
int i= 0;
i < d;
i++)
4545 if (bounds [
i] + 1 <= oldL/2)
4547 int k=
tmin (bounds [
i] + 1, oldL/2);
4549 for (
int ii= 0; ii < factors.
length(); ii++)
4551 if (
A[ii].
size() - 1 >=
i)
4559 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4561 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4562 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4564 rank= nmod_mat_nullspace (null, FLINTK);
4565 nmod_mat_clear (FLINTK);
4566 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4567 nmod_mat_clear (FLINTC);
4568 nmod_mat_init_set (FLINTC, FLINTN);
4569 nmod_mat_clear (FLINTN);
4570 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4572 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4574 nmod_mat_clear (FLINTC);
4575 nmod_mat_window_clear (FLINTK);
4576 nmod_mat_clear (null);
4580 transpose (NTLK, NTLK);
4581 kernel (NTLK, NTLK);
4582 transpose (NTLK, NTLK);
4587 if (nmod_mat_ncols (FLINTN) == 1)
4589 if (NTLN.NumCols() == 1)
4598 if (nmod_mat_ncols (FLINTN) == 1)
4600 if (NTLN.NumCols() == 1)
4613 bufUniFactors= factors;
4619 delete [] zeroOneVecs;
4623 factors= bufUniFactors;
4650 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_pE& NTLN,
4657 bool hitBound=
false;
4658 bool useOldQs=
false;
4659 if (NTLN.NumRows() != factors.
length())
4660 ident (NTLN, factors.
length());
4664 mat_zz_pE* NTLC, NTLK;
4674 for (
int i= 0;
i < factors.
length();
i++,
j++)
4681 for (
int i= 0;
i < factors.
length();
i++,
j++)
4686 for (
int i= 0;
i < d;
i++)
4688 if (bounds [
i] + 1 <= oldL/2)
4690 int k=
tmin (bounds [
i] + 1, oldL/2);
4692 for (
int ii= 0; ii < factors.
length(); ii++)
4694 if (
A[ii].
size() - 1 >=
i)
4702 transpose (NTLK, NTLK);
4703 kernel (NTLK, NTLK);
4704 transpose (NTLK, NTLK);
4708 if (NTLN.NumCols() == 1)
4715 if (NTLN.NumCols() == 1)
4724 bufUniFactors= factors;
4726 delete [] zeroOneVecs;
4730 factors= bufUniFactors;
4759 int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
const
4766 int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
const
4775 bool hitBound=
false;
4776 bool useOldQs=
false;
4785 nmod_mat_clear (FLINTN);
4787 for (
long i=factors.
length()-1;
i >= 0;
i--)
4788 nmod_mat_entry (FLINTN,
i,
i)= 1;
4790 if (NTLN.NumRows() != factors.
length())
4791 ident (NTLN, factors.
length());
4801 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
4803 mat_zz_p* NTLC, NTLK, *NTLMat;
4812 powX=
power (
y-gamma, oldL);
4813 Mat=
CFMatrix (oldL*degMipo, oldL*degMipo);
4814 for (
int i= 0;
i < oldL*degMipo;
i++)
4817 imBasis= imBasis (
power (
y, degMipo),
y);
4818 imBasis= imBasis (
y, gamma);
4826 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
4828 nmod_mat_inv (FLINTMatInv, FLINTMat);
4831 *NTLMat= inv (*NTLMat);
4840 for (
int i= 0;
i < factors.
length();
i++,
j++)
4846 for (
int i= 0;
i < factors.
length();
i++,
j++)
4851 for (
int i= 0;
i < d;
i++)
4853 if (bounds [
i] + 1 <= oldL/2)
4855 int k=
tmin (bounds [
i] + 1, oldL/2);
4857 for (
int ii= 0; ii < factors.
length(); ii++)
4859 if (
A[ii].
size() - 1 >=
i)
4867 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4880 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4900 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4902 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4903 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4905 rank= nmod_mat_nullspace (null, FLINTK);
4906 nmod_mat_clear (FLINTK);
4907 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4908 nmod_mat_clear (FLINTC);
4909 nmod_mat_init_set (FLINTC, FLINTN);
4910 nmod_mat_clear (FLINTN);
4911 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4913 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4915 nmod_mat_clear (FLINTC);
4916 nmod_mat_window_clear (FLINTK);
4917 nmod_mat_clear (null);
4921 transpose (NTLK, NTLK);
4922 kernel (NTLK, NTLK);
4923 transpose (NTLK, NTLK);
4932 if (nmod_mat_ncols (FLINTN) == 1)
4934 nmod_mat_clear (FLINTMat);
4935 nmod_mat_clear (FLINTMatInv);
4937 if (NTLN.NumCols() == 1)
4952 nmod_mat_clear (FLINTMat);
4953 nmod_mat_clear (FLINTMatInv);
4959 if (nmod_mat_ncols (FLINTN) == 1)
4961 if (NTLN.NumCols() == 1)
4974 bufUniFactors= factors;
4986 delete [] zeroOneVecs;
4990 factors= bufUniFactors;
5017 int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
5023 int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
5032 bool hitBound=
false;
5033 bool useOldQs=
false;
5035 if (nmod_mat_nrows (FLINTN) != factors.
length())
5037 nmod_mat_clear (FLINTN);
5039 for (
long i=factors.
length()-1;
i >= 0;
i--)
5040 nmod_mat_entry (FLINTN,
i,
i)= 1;
5043 if (NTLN.NumRows() != factors.
length())
5044 ident (NTLN, factors.
length());
5051 nmod_mat_t FLINTC, FLINTK, null;
5053 mat_zz_p* NTLC, NTLK;
5064 for (
int i= 0;
i < factors.
length();
i++,
j++)
5071 for (
int i= 0;
i < factors.
length();
i++,
j++)
5076 for (
int i= 0;
i < d;
i++)
5078 if (bounds [
i] + 1 <= oldL/2)
5080 int k=
tmin (bounds [
i] + 1, oldL/2);
5082 for (
int ii= 0; ii < factors.
length(); ii++)
5084 if (
A[ii].
size() - 1 >=
i)
5092 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5094 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5095 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5097 rank= nmod_mat_nullspace (null, FLINTK);
5098 nmod_mat_clear (FLINTK);
5099 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5100 nmod_mat_clear (FLINTC);
5101 nmod_mat_init_set (FLINTC, FLINTN);
5102 nmod_mat_clear (FLINTN);
5103 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5105 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5107 nmod_mat_clear (FLINTC);
5108 nmod_mat_window_clear (FLINTK);
5109 nmod_mat_clear (null);
5113 transpose (NTLK, NTLK);
5114 kernel (NTLK, NTLK);
5115 transpose (NTLK, NTLK);
5120 if (nmod_mat_ncols (FLINTN) == 1)
5122 if (NTLN.NumCols() == 1)
5139 bufUniFactors= factors;
5145 delete [] zeroOneVecs;
5149 factors= bufUniFactors;
5177 factors,
int l,
int liftBound,
int d,
int*
5178 bounds, nmod_mat_t FLINTN,
CFList& diophant,
5185 factors,
int l,
int liftBound,
int d,
int*
5186 bounds, mat_zz_p& NTLN,
CFList& diophant,
5195 CFList bufFactors= factors;
5198 bool useOldQs=
false;
5199 bool hitBound=
false;
5204 if (nmod_mat_nrows (FLINTN) != factors.
length())
5206 nmod_mat_clear (FLINTN);
5208 for (
long i=factors.
length()-1;
i >= 0;
i--)
5209 nmod_mat_entry (FLINTN,
i,
i)= 1;
5212 if (NTLN.NumRows() != factors.
length())
5213 ident (NTLN, factors.
length());
5220 nmod_mat_t FLINTC, FLINTK, null;
5222 mat_zz_p* NTLC, NTLK;
5226 while (
l <= liftBound)
5234 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5240 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5243 for (
int i= 0;
i < d;
i++)
5245 if (bounds [
i] + 1 <=
l/2)
5247 int k=
tmin (bounds [
i] + 1,
l/2);
5249 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5251 if (
A[ii].
size() - 1 >=
i)
5259 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5261 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5262 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5264 rank= nmod_mat_nullspace (null, FLINTK);
5265 nmod_mat_clear (FLINTK);
5266 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5267 nmod_mat_clear (FLINTC);
5268 nmod_mat_init_set (FLINTC, FLINTN);
5269 nmod_mat_clear (FLINTN);
5270 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5272 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5274 nmod_mat_clear (FLINTC);
5275 nmod_mat_window_clear (FLINTK);
5276 nmod_mat_clear (null);
5280 transpose (NTLK, NTLK);
5281 kernel (NTLK, NTLK);
5282 transpose (NTLK, NTLK);
5287 if (nmod_mat_ncols (FLINTN) == 1)
5289 if (NTLN.NumCols() == 1)
5299 if (nmod_mat_ncols (FLINTN) == 1)
5301 if (NTLN.NumCols() == 1)
5314 bufBufFactors= bufFactors;
5320 delete [] zeroOneVecs;
5324 factors= bufFactors;
5331 bufFactors= bufBufFactors;
5340 int factorsFound= 0;
5343 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5344 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5346 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5347 for (
long i= 0;
i < NTLN.NumCols();
i++)
5349 factorsFoundIndex[
i]= 0;
5353 factorsFoundIndex, FLINTN,
eval,
false
5357 degree (
LCF), factorsFound, factorsFoundIndex,
5361 if (nmod_mat_ncols (FLINTN) ==
result.length())
5365 factorsFoundIndex, NTLN,
eval,
false
5369 degree (
LCF), factorsFound, factorsFoundIndex,
5373 if (NTLN.NumCols() ==
result.length())
5377 delete [] factorsFoundIndex;
5380 delete [] factorsFoundIndex;
5403 factors= bufFactors;
5412 factors,
int l,
int liftBound,
int d,
int*
5413 bounds, mat_zz_pE& NTLN,
CFList& diophant,
5421 CFList bufFactors= factors;
5424 bool useOldQs=
false;
5425 bool hitBound=
false;
5429 if (NTLN.NumRows() != factors.
length())
5430 ident (NTLN, factors.
length());
5433 mat_zz_pE* NTLC, NTLK;
5436 while (
l <= liftBound)
5444 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5450 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5453 for (
int i= 0;
i < d;
i++)
5455 if (bounds [
i] + 1 <=
l/2)
5457 int k=
tmin (bounds [
i] + 1,
l/2);
5459 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5461 if (
A[ii].
size() - 1 >=
i)
5469 transpose (NTLK, NTLK);
5470 kernel (NTLK, NTLK);
5471 transpose (NTLK, NTLK);
5474 if (NTLN.NumCols() == 1)
5481 if (NTLN.NumCols() == 1)
5489 bufBufFactors= bufFactors;
5491 delete [] zeroOneVecs;
5495 factors= bufFactors;
5502 bufFactors= bufBufFactors;
5507 int factorsFound= 0;
5509 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5510 for (
long i= 0;
i < NTLN.NumCols();
i++)
5511 factorsFoundIndex[
i]= 0;
5514 factorsFoundIndex, NTLN,
eval,
false
5518 degree (
LCF), factorsFound, factorsFoundIndex,
5521 if (NTLN.NumCols() ==
result.length())
5524 delete [] factorsFoundIndex;
5527 delete [] factorsFoundIndex;
5550 factors= bufFactors;
5560 int liftBound,
int d,
int* bounds,
5561 nmod_mat_t FLINTN,
CFList& diophant,
5570 int liftBound,
int d,
int* bounds,
5571 mat_zz_p& NTLN,
CFList& diophant,
5582 CFList bufFactors= factors;
5585 bool useOldQs=
false;
5586 bool hitBound=
false;
5597 nmod_mat_clear (FLINTN);
5599 for (
long i=factors.
length()-1;
i >= 0;
i--)
5600 nmod_mat_entry (FLINTN,
i,
i)= 1;
5602 if (NTLN.NumRows() != factors.
length())
5603 ident (NTLN, factors.
length());
5611 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
5613 mat_zz_p* NTLMat,*NTLC, NTLK;
5617 while (
l <= liftBound)
5627 for (
int i= 0;
i <
l*degMipo;
i++)
5631 imBasis= imBasis (
power (
y, degMipo),
y);
5632 imBasis= imBasis (
y, gamma);
5640 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
5642 nmod_mat_inv (FLINTMatInv, FLINTMat);
5645 *NTLMat= inv (*NTLMat);
5655 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5661 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5664 for (
int i= 0;
i < d;
i++)
5666 if (bounds [
i] + 1 <=
l/2)
5668 int k=
tmin (bounds [
i] + 1,
l/2);
5670 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5672 if (
A[ii].
size() - 1 >=
i)
5680 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5693 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5713 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5715 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5716 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5718 rank= nmod_mat_nullspace (null, FLINTK);
5719 nmod_mat_clear (FLINTK);
5720 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5721 nmod_mat_clear (FLINTC);
5722 nmod_mat_init_set (FLINTC, FLINTN);
5723 nmod_mat_clear (FLINTN);
5724 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5726 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5728 nmod_mat_clear (FLINTC);
5729 nmod_mat_window_clear (FLINTK);
5730 nmod_mat_clear (null);
5734 transpose (NTLK, NTLK);
5735 kernel (NTLK, NTLK);
5736 transpose (NTLK, NTLK);
5745 if (nmod_mat_ncols (FLINTN) == 1)
5747 if (NTLN.NumCols() == 1)
5757 nmod_mat_clear (FLINTMat);
5758 nmod_mat_clear (FLINTMatInv);
5759 if (nmod_mat_ncols (FLINTN) == 1)
5762 if (NTLN.NumCols() == 1)
5770 bufBufFactors= bufFactors;
5782 delete [] zeroOneVecs;
5786 factors= bufFactors;
5793 bufFactors= bufBufFactors;
5802 int factorsFound= 0;
5805 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5806 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5808 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5809 for (
long i= 0;
i < NTLN.NumCols();
i++)
5811 factorsFoundIndex[
i]= 0;
5819 degree (
LCF), factorsFound, factorsFoundIndex,
5822 if (nmod_mat_ncols (FLINTN) ==
result.length())
5830 degree (
LCF), factorsFound, factorsFoundIndex,
5833 if (NTLN.NumCols() ==
result.length())
5837 delete [] factorsFoundIndex;
5840 delete [] factorsFoundIndex;
5867 factors= bufFactors;
5876 l,
int liftBound,
int d,
int* bounds,
5877 nmod_mat_t FLINTN,
CFList& diophant,
5885 l,
int liftBound,
int d,
int* bounds,
5886 mat_zz_p& NTLN,
CFList& diophant,
5896 CFList bufFactors= factors;
5899 bool useOldQs=
false;
5901 bool hitBound=
false;
5906 if (nmod_mat_nrows (FLINTN) != factors.
length())
5908 nmod_mat_clear (FLINTN);
5910 for (
long i=factors.
length()-1;
i >= 0;
i--)
5911 nmod_mat_entry (FLINTN,
i,
i)= 1;
5914 if (NTLN.NumRows() != factors.
length())
5915 ident (NTLN, factors.
length());
5921 nmod_mat_t FLINTC, FLINTK, null;
5923 mat_zz_p* NTLC, NTLK;
5927 while (
l <= liftBound)
5935 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5941 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5944 for (
int i= 0;
i < d;
i++)
5946 if (bounds [
i] + 1 <=
l/2)
5948 int k=
tmin (bounds [
i] + 1,
l/2);
5950 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5953 if (
A[ii].
size() - 1 >=
i)
5961 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5963 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5964 nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5966 rank= nmod_mat_nullspace (null, FLINTK);
5967 nmod_mat_clear (FLINTK);
5968 nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5969 nmod_mat_clear (FLINTC);
5970 nmod_mat_init_set (FLINTC, FLINTN);
5971 nmod_mat_clear (FLINTN);
5972 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5974 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5976 nmod_mat_clear (FLINTC);
5977 nmod_mat_window_clear (FLINTK);
5978 nmod_mat_clear (null);
5982 transpose (NTLK, NTLK);
5983 kernel (NTLK, NTLK);
5984 transpose (NTLK, NTLK);
5989 if (nmod_mat_ncols (FLINTN) == 1)
5991 if (NTLN.NumCols() == 1)
6000 if (nmod_mat_ncols (FLINTN) == 1)
6002 if (NTLN.NumCols() == 1)
6015 bufBufFactors= bufFactors;
6021 delete [] zeroOneVecs;
6025 factors= bufFactors;
6032 bufFactors= bufBufFactors;
6041 int factorsFound= 0;
6044 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6045 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6047 int* factorsFoundIndex=
new int [NTLN.NumCols()];
6048 for (
long i= 0;
i < NTLN.NumCols();
i++)
6050 factorsFoundIndex[
i]= 0;
6054 factorsFoundIndex, FLINTN,
eval,
false
6058 degree (
LCF), factorsFound, factorsFoundIndex,
6061 if (nmod_mat_ncols (FLINTN) ==
result.length())
6065 factorsFoundIndex, NTLN,
eval,
false
6069 degree (
LCF), factorsFound, factorsFoundIndex,
6072 if (NTLN.NumCols() ==
result.length())
6076 delete [] factorsFoundIndex;
6079 delete [] factorsFoundIndex;
6102 factors= bufFactors;
6119 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6123 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6130 factors= bufFactors;
6152 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6156 for (
long j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
6158 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
6163 factors= bufFactors;
6185 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6189 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6196 factors= bufFactors;
6209 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6217 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6230 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6233 nmod_mat_init_set (FLINTN,
N);
6234 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6235 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6238 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6239 for (
long i= 0;
i < NTLN.NumCols();
i++)
6241 factorsFoundIndex [
i]= 0;
6243 if (
degree (F) + 1 > smallFactorDeg)
6245 if (
l < smallFactorDeg)
6256 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6259 if (
result.length() == nmod_mat_ncols (FLINTN))
6261 nmod_mat_clear (FLINTN);
6265 factorsFoundIndex, NTLN,
evaluation, beenInThres
6268 if (
result.length() == NTLN.NumCols())
6272 delete [] factorsFoundIndex;
6277 int i= sizeOfLiftPre - 1;
6279 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6283 if (
l < liftPre[
i-1] + 1)
6289 l= liftPre[
i-1] + 1;
6300 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6303 if (
result.length() == nmod_mat_ncols (FLINTN))
6305 nmod_mat_clear (FLINTN);
6309 factorsFoundIndex, NTLN,
evaluation, beenInThres
6312 if (
result.length() == NTLN.NumCols())
6316 delete [] factorsFoundIndex;
6325 while (((
degree (F,
y)/4)*
i+1) + 4 <= smallFactorDeg)
6337 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6338 LC (F,1).inCoeffDomain() &&
6352 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6357 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6366 if (check1/
Lc (check1) == check2/
Lc (check2))
6369 nmod_mat_clear (FLINTN);
6371 result.append (oldcheck1);
6374 delete [] factorsFoundIndex;
6388 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6391 if (
result.length() == nmod_mat_ncols (FLINTN))
6393 nmod_mat_clear (FLINTN);
6397 factorsFoundIndex, NTLN,
evaluation, beenInThres
6400 if (
result.length() == NTLN.NumCols())
6404 delete [] factorsFoundIndex;
6412 nmod_mat_clear (FLINTN);
6415 delete [] factorsFoundIndex;
6423 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6434 int smallFactorDeg= 11;
6436 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6437 for (
long i= 0;
i < NTLN.NumCols();
i++)
6438 factorsFoundIndex [
i]= 0;
6440 if (
degree (F) + 1 > smallFactorDeg)
6442 if (
l < smallFactorDeg)
6452 factorsFoundIndex, NTLN,
evaluation, beenInThres
6455 if (
result.length() == NTLN.NumCols())
6458 delete [] factorsFoundIndex;
6463 int i= sizeOfLiftPre - 1;
6465 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6469 if (
l < liftPre[
i-1] + 1)
6475 l= liftPre[
i-1] + 1;
6485 factorsFoundIndex, NTLN,
evaluation, beenInThres
6488 if (
result.length() == NTLN.NumCols())
6491 delete [] factorsFoundIndex;
6500 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6512 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6513 LC (F,1).inCoeffDomain() &&
6527 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6532 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6541 if (check1/
Lc (check1) == check2/
Lc (check2))
6543 result.append (oldcheck1);
6546 delete [] factorsFoundIndex;
6559 factorsFoundIndex, NTLN,
evaluation, beenInThres
6562 if (
result.length() == NTLN.NumCols())
6565 delete [] factorsFoundIndex;
6573 delete [] factorsFoundIndex;
6583 int& factorsFound,
bool beenInThres,
CFMatrix&
6592 int& factorsFound,
bool beenInThres,
CFMatrix&
6605 int smallFactorDeg= 11;
6608 nmod_mat_init_set (FLINTN,
N);
6609 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6610 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6613 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6614 for (
long i= 0;
i < NTLN.NumCols();
i++)
6616 factorsFoundIndex [
i]= 0;
6618 if (
degree (F) + 1 > smallFactorDeg)
6620 if (
l < smallFactorDeg)
6631 factorsFoundIndex, FLINTN, beenInThres,
info,
6636 factorsFoundIndex, NTLN, beenInThres,
info,
6642 if (
result.length() == nmod_mat_ncols (FLINTN))
6644 nmod_mat_clear (FLINTN);
6646 if (
result.length() == NTLN.NumCols())
6650 delete [] factorsFoundIndex;
6655 int i= sizeOfLiftPre - 1;
6657 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6661 if (
l < liftPre[
i-1] + 1)
6667 l= liftPre[
i-1] + 1;
6678 factorsFoundIndex, FLINTN, beenInThres,
info,
6683 factorsFoundIndex, NTLN, beenInThres,
info,
6689 if (
result.length() == nmod_mat_ncols (FLINTN))
6691 nmod_mat_clear (FLINTN);
6693 if (
result.length() == NTLN.NumCols())
6697 delete [] factorsFoundIndex;
6706 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6728 factorsFoundIndex, FLINTN, beenInThres,
info,
6733 factorsFoundIndex, NTLN, beenInThres,
info,
6739 if (
result.length() == nmod_mat_ncols (FLINTN))
6741 nmod_mat_clear (FLINTN);
6743 if (
result.length() == NTLN.NumCols())
6747 delete [] factorsFoundIndex;
6755 nmod_mat_clear (FLINTN);
6758 delete [] factorsFoundIndex;
6770 CFList bufUniFactors= uniFactors;
6772 int smallFactorDeg= d;
6774 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6775 int adaptedLiftBound;
6777 int * factorsFoundIndex=
new int [uniFactors.
length()];
6778 for (
int i= 0;
i < uniFactors.
length();
i++)
6779 factorsFoundIndex [
i]= 0;
6782 factorsFoundIndex, degs, success, smallFactorDeg,
eval);
6783 delete [] factorsFoundIndex;
6787 return earlyFactors;
6792 return earlyFactors;
6794 int sizeOldF=
size (
G);
6795 if (
size (F) < sizeOldF)
6799 return earlyFactors;
6803 uniFactors= bufUniFactors;
6818 CFList bufUniFactors= uniFactors;
6820 int smallFactorDeg= d;
6822 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6823 int adaptedLiftBound;
6825 int * factorsFoundIndex=
new int [uniFactors.
length()];
6826 for (
int i= 0;
i < uniFactors.
length();
i++)
6827 factorsFoundIndex [
i]= 0;
6832 delete [] factorsFoundIndex;
6836 return earlyFactors;
6841 return earlyFactors;
6844 int sizeOldF=
size (
G);
6845 if (
size (F) < sizeOldF)
6849 return earlyFactors;
6853 uniFactors= bufUniFactors;
6879 int minBound= bounds[0];
6880 for (
int i= 1;
i < d;
i++)
6883 minBound=
tmin (minBound, bounds[
i]);
6886 CFList bufUniFactors= uniFactors;
6894 bool success=
false;
6896 success, minBound + 1,
eval
6899 if (smallFactors.
length() > 0)
6901 if (smallFactors.
length() == 1)
6912 return smallFactors;
6939 return smallFactors;
6951 return smallFactors;
6955 minBound= bounds[0];
6956 for (
int i= 1;
i < d;
i++)
6959 minBound=
tmin (minBound, bounds[
i]);
6972 return smallFactors;
7002 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7003 nmod_mat_entry (FLINTN,
i,
i)= 1;
7005 ident (NTLN, bufUniFactors.
length() - 1);
7014 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7015 nmod_mat_entry (FLINTN,
i,
i)= 1;
7018 ident (NTLN, bufUniFactors.
length() - 1);
7021 ident (NTLNe, bufUniFactors.
length() - 1);
7034 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7036 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7045 minBound, bufUniFactors, FLINTN,
7047 minBound, bufUniFactors, NTLN,
7054 bufUniFactors, NTLNe, diophant,
M, Pi, bufQ,
7065 minBound, bufUniFactors, FLINTN, diophant,
M,
7067 minBound, bufUniFactors, NTLN, diophant,
M,
7076 liftBound, minBound, bufUniFactors,
7078 FLINTN, diophant,
M, Pi, bufQ,
7080 NTLN, diophant,
M, Pi, bufQ,
7086 minBound, bufUniFactors, NTLNe, diophant,
7093 "time to compute a reduced lattice: ");
7095 if (oldL > liftBound)
7099 nmod_mat_clear (FLINTN);
7102 return Union (smallFactors,
7115 nmod_mat_clear (FLINTN);
7126 int * factorsFoundIndex;
7130 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7131 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7133 factorsFoundIndex=
new int [NTLN.NumCols()];
7134 for (
long i= 0;
i < NTLN.NumCols();
i++)
7136 factorsFoundIndex[
i]= 0;
7140 factorsFoundIndex=
new int [NTLNe.NumCols()];
7141 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7142 factorsFoundIndex[
i]= 0;
7144 int factorsFound= 0;
7149 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7151 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7156 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7161 if (
result.length() == nmod_mat_ncols (FLINTN))
7164 nmod_mat_clear (FLINTN);
7166 if (
result.length() == NTLN.NumCols())
7169 delete [] factorsFoundIndex;
7176 if (
result.length() == NTLNe.NumCols())
7178 delete [] factorsFoundIndex;
7183 delete [] factorsFoundIndex;
7187 int * factorsFoundIndex;
7191 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7192 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7194 factorsFoundIndex=
new int [NTLN.NumCols()];
7195 for (
long i= 0;
i < NTLN.NumCols();
i++)
7197 factorsFoundIndex[
i]= 0;
7201 factorsFoundIndex=
new int [NTLNe.NumCols()];
7202 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7203 factorsFoundIndex[
i]= 0;
7206 int factorsFound= 0;
7210 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7212 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7217 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7222 if (
result.length() == nmod_mat_ncols(FLINTN))
7224 nmod_mat_clear (FLINTN);
7226 if (
result.length() == NTLN.NumCols())
7229 delete [] factorsFoundIndex;
7236 if (
result.length() == NTLNe.NumCols())
7238 delete [] factorsFoundIndex;
7243 delete [] factorsFoundIndex;
7247 bool beenInThres=
false;
7254 if (nmod_mat_ncols (FLINTN) < bufUniFactors.
length())
7258 if (NTLN.NumCols() < bufUniFactors.
length())
7260 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7269 if (NTLNe.NumCols() < bufUniFactors.
length())
7271 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
7280 int factorsFound= 0;
7284 result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
7286 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7288 factorsFound, beenInThres, M, Pi,
7289 diophant, symmetric, eval
7293 if (result.length() == nmod_mat_ncols (FLINTN))
7295 nmod_mat_clear (FLINTN);
7297 if (result.length() == NTLN.NumCols())
7301 return Union (result, smallFactors);
7306 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
7307 factorsFound, beenInThres, M, Pi,
7308 diophant, symmetric, eval
7311 if (result.length() == NTLNe.NumCols())
7314 return Union (result, smallFactors);
7323 for (CFListIterator i= result; i.hasItem(); i++)
7326 tmp1= mod (i.getItem(), y-eval);
7328 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7330 tmp2= mod (j.getItem(), y);
7344 long numCols, numRows;
7345 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7348 numCols= nmod_mat_ncols (FLINTN);
7349 numRows= nmod_mat_nrows (FLINTN);
7350 zeroOne= extractZeroOneVecs (FLINTN);
7352 numCols= NTLN.NumCols();
7353 numRows= NTLN.NumRows();
7354 zeroOne= extractZeroOneVecs (NTLN);
7359 numCols= NTLNe.NumCols();
7360 numRows= NTLNe.NumRows();
7361 zeroOne= extractZeroOneVecs (NTLNe);
7363 CFList bufBufUniFactors= bufUniFactors;
7366 CFList factorsConsidered;
7368 for (
int i= 0;
i < numCols;
i++)
7370 if (zeroOne [
i] == 0)
7372 iter= bufUniFactors;
7374 factorsConsidered=
CFList();
7375 for (
int j= 0;
j < numRows;
j++,
iter++)
7380 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
7399 for (iter2=
result; iter2.hasItem(); iter2++)
7401 tmp=
mod (iter2.getItem(),
y-
eval);
7405 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
7410 bufUniFactors= bufBufUniFactors;
7421 oldNumCols= nmod_mat_ncols (FLINTN);
7423 oldNumCols= NTLN.NumCols();
7426 oldNumCols, oldL,
l,
eval
7434 oldNumCols= nmod_mat_ncols (FLINTN);
7436 oldNumCols= NTLN.NumCols();
7445 oldNumCols= NTLNe.NumCols();
7457 nmod_mat_clear (FLINTN);
7477 nmod_mat_clear (FLINTN);
7484 nmod_mat_clear (FLINTN);
7487 alpha, degs, symmetric,
7527 if (
result.length()== nmod_mat_ncols (FLINTN))
7529 nmod_mat_clear (FLINTN);
7531 if (
result.length()== NTLN.NumCols())
7541 if (
result.length()== NTLNe.NumCols())
7554 liftBound,d,bounds,FLINTN,
7556 liftBound, d, bounds, NTLN,
7558 diophant,
M, Pi, bufQ,
eval
7564 liftBound, d, bounds,
7566 FLINTN, diophant,
M,
7574 liftBound, d, bounds,
7583 if (
result.length() == nmod_mat_ncols (FLINTN))
7585 nmod_mat_clear (FLINTN);
7587 if (
result.length() == NTLN.NumCols())
7597 if (
result.length() == NTLNe.NumCols())
7607 DEBOUTLN (cerr,
"lattice recombination failed");
7617 nmod_mat_clear (FLINTN);
7626 minBound= bounds[0];
7627 for (
int i= 1;
i < d;
i++)
7630 minBound=
tmin (minBound, bounds[
i]);
7633 if (minBound > 16 ||
result.length() == 0)
7650 degs,symmetric,
eval
7697 imPrimElemAlpha=
map (primElemAlpha,
alpha, bufEvaluation, gamma);
7726 CFList bufUniFactors= uniFactors;
7746 int minBound= bounds[0];
7747 for (
int i= 1;
i < d;
i++)
7750 minBound=
tmin (minBound, bounds[
i]);
7762 bool success=
false;
7767 if (smallFactors.
length() > 0)
7769 if (smallFactors.
length() == 1)
7783 return smallFactors;
7810 return smallFactors;
7824 smallFactors.
append (tmp);
7825 return smallFactors;
7829 minBound= bounds[0];
7830 for (
int i= 1;
i < d;
i++)
7833 minBound=
tmin (minBound, bounds[
i]);
7849 smallFactors.
append (tmp);
7850 return smallFactors;
7859 nmod_mat_init (FLINTN, bufUniFactors.
length()-1, bufUniFactors.
length()-1,
7861 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7862 nmod_mat_entry (FLINTN,
i,
i)= 1;
7872 ident (NTLN, bufUniFactors.
length() - 1);
7884 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7889 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7898 minBound+1, bufUniFactors, FLINTN, diophant,
7904 minBound + 1, bufUniFactors, NTLN, diophant,
7911 "time to compute a reduced lattice: ");
7914 if (oldL > liftBound)
7917 nmod_mat_clear (FLINTN);
7932 nmod_mat_clear (FLINTN);
7946 int * factorsFoundIndex;
7949 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7950 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7952 factorsFoundIndex=
new int [NTLN.NumCols()];
7953 for (
long i= 0;
i < NTLN.NumCols();
i++)
7955 factorsFoundIndex[
i]= 0;
7957 int factorsFound= 0;
7962 factorsFound, factorsFoundIndex, FLINTN,
false,
info,
7966 if (
result.length() == nmod_mat_ncols (FLINTN))
7968 nmod_mat_clear (FLINTN);
7971 factorsFound, factorsFoundIndex, NTLN,
false,
info,
7975 if (
result.length() == NTLN.NumCols())
7978 delete [] factorsFoundIndex;
7983 delete [] factorsFoundIndex;
7987 int * factorsFoundIndex;
7989 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7990 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7992 factorsFoundIndex=
new int [NTLN.NumCols()];
7993 for (
long i= 0;
i < NTLN.NumCols();
i++)
7995 factorsFoundIndex[
i]= 0;
7997 int factorsFound= 0;
8001 factorsFound, factorsFoundIndex, FLINTN,
false,
8005 if (
result.length() == nmod_mat_ncols (FLINTN))
8007 nmod_mat_clear (FLINTN);
8010 factorsFound, factorsFoundIndex, NTLN,
false,
8014 if (
result.length() == NTLN.NumCols())
8017 delete [] factorsFoundIndex;
8021 delete [] factorsFoundIndex;
8025 bool beenInThres=
false;
8028 if (
l <= thres && bufUniFactors.
length() > nmod_mat_ncols (FLINTN))
8034 if (
l <= thres && bufUniFactors.
length() > NTLN.NumCols())
8045 int factorsFound= 0;
8049 factorsFound, beenInThres,
M, Pi,
8053 if (
result.length() == nmod_mat_ncols (FLINTN))
8055 nmod_mat_clear (FLINTN);
8058 factorsFound, beenInThres,
M, Pi,
8062 if (
result.length() == NTLN.NumCols())
8099 CFList bufBufUniFactors= bufUniFactors;
8102 CFList factorsConsidered;
8104 for (
int i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
8106 for (
int i= 0;
i < NTLN.NumCols();
i++)
8109 if (zeroOne [
i] == 0)
8111 iter= bufUniFactors;
8113 factorsConsidered=
CFList();
8115 for (
int j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
8117 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
8119 for (
int j= 0;
j < NTLN.NumRows();
j++,
iter++)
8135 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
8140 bufUniFactors= bufBufUniFactors;
8149 oldNumCols= nmod_mat_ncols (FLINTN);
8154 nmod_mat_clear (FLINTN);
8156 oldNumCols= NTLN.NumCols();
8192 if (
l/degMipo < liftBound)
8199 if (
result.length()== nmod_mat_ncols (FLINTN))
8201 nmod_mat_clear (FLINTN);
8207 if (
result.length()== NTLN.NumCols())
8219 liftBound, d,bounds,FLINTN,
8220 diophant,
M, Pi, bufQ,
8224 if (
result.length()== nmod_mat_ncols (FLINTN))
8226 nmod_mat_clear (FLINTN);
8229 liftBound, d, bounds, NTLN,
8230 diophant,
M, Pi, bufQ,
8234 if (
result.length()== NTLN.NumCols())
8245 nmod_mat_clear (FLINTN);
8248 DEBOUTLN (cerr,
"lattice recombination failed");
8262 smallFactors.
append (tmp);
8266 minBound= bounds[0];
8267 for (
int i= 1;
i < d;
i++)
8270 minBound=
tmin (minBound, bounds[
i]);
8273 if (minBound > 16 ||
result.length() == 0)
8319 if (
A.isUnivariate())
8321 if (extension ==
false)
8342 A=
A/(contentAx*contentAy);
8343 CFList contentAxFactors, contentAyFactors;
8353 if (
A.inCoeffDomain())
8355 append (factors, contentAxFactors);
8356 append (factors, contentAyFactors);
8360 else if (
A.isUnivariate())
8363 append (factors, contentAxFactors);
8364 append (factors, contentAyFactors);
8385 bool derivXZero=
false;
8392 gcdDerivX=
gcd (
A, derivX);
8393 if (
degree (gcdDerivX) > 0)
8398 append (factorsG, contentAxFactors);
8399 append (factorsG, contentAyFactors);
8406 bool derivYZero=
false;
8413 gcdDerivY=
gcd (
A, derivY);
8414 if (
degree (gcdDerivY) > 0)
8419 append (factorsG, contentAxFactors);
8420 append (factorsG, contentAyFactors);
8435 derivXZero= derivYZero;
8457 int minBound= bounds[0];
8458 for (
int i= 1;
i < boundsLength;
i++)
8461 minBound=
tmin (minBound, bounds[
i]);
8466 int minBound2= bounds2[0];
8467 for (
int i= 1;
i < boundsLength2;
i++)
8469 if (bounds2[
i] != 0)
8470 minBound2=
tmin (minBound2, bounds2[
i]);
8476 CFList uniFactors, list, bufUniFactors;
8481 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8482 CFList bufUniFactors2, list2, uniFactors2;
8493 bool symmetric=
false;
8496 for (
int i= 0;
i < factorNums;
i++)
8502 if (!derivXZero && !fail2 && !symmetric)
8513 "time to find eval point wrt y: ");
8516 if (fail && (
i == 0))
8518 if (!derivXZero && !fail2 && !symmetric)
8520 bufEvaluation= bufEvaluation2;
8521 int dummy= subCheck2;
8522 subCheck2= subCheck1;
8527 bufAeval= bufAeval2;
8536 if (fail && (
i == 0))
8549 if (fail && (
i != 0))
8556 "time for univariate factorization over Fq: ");
8557 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8558 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8560 if (!derivXZero && !fail2 && !symmetric)
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8567 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8570 if (bufUniFactors.
length() == 1 ||
8571 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8591 if (
i == 0 && !extension)
8597 if (subCheck > 1 && (subCheck1%subCheck == 0))
8600 subst (bufA, bufA, subCheck,
x);
8613 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8617 if (subCheck > 1 && (subCheck2%subCheck == 0))
8620 subst (bufA, bufA, subCheck,
y);
8636 if (!derivXZero && !fail2 && !symmetric)
8643 uniFactors= bufUniFactors;
8645 if (!derivXZero && !fail2 && !symmetric)
8648 evaluation2= bufEvaluation2;
8649 uniFactors2= bufUniFactors2;
8656 if (!derivXZero && !fail2 && !symmetric)
8661 uniFactors2= bufUniFactors2;
8663 evaluation2= bufEvaluation2;
8668 uniFactors= bufUniFactors;
8673 list.
append (bufEvaluation);
8674 if (!derivXZero && !fail2 && !symmetric)
8675 list2.
append (bufEvaluation2);
8678 "total time for univariate factorizations: ");
8680 if (!derivXZero && !fail2 && !symmetric)
8682 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8687 uniFactors= uniFactors2;
8719 minBound= minBound2;
8725 "time to shift eval to zero: ");
8731 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8733 if ((GF && !extension) || (GF && extension &&
k != 1))
8735 bool earlySuccess=
false;
8739 (
A, earlySuccess, earlyFactors, degs, liftBound,
8742 "time for bivariate hensel lifting over Fq: ");
8743 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8755 "time for naive bivariate factor recombi over Fq: ");
8758 factors=
Union (earlyFactors, factors);
8759 else if (!earlySuccess && degs.
getLength() == 1)
8760 factors= earlyFactors;
8770 factors=
Union (lll, factors);
8776 factors=
Union (lll, factors);
8778 else if (!extension && (
alpha !=
x || GF))
8782 factors=
Union (lll, factors);
8785 "time to bivar lift and LLL recombi over Fq: ");
8786 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8790 bool earlySuccess=
false;
8794 (
A, earlySuccess, earlyFactors, degs, liftBound,
8797 "time for bivar hensel lifting over Fq: ");
8798 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8806 "time for small subset naive recombi over Fq: ");
8808 int oldUniFactorsLength= uniFactors.
length();
8829 "time to increase precision: ");
8830 factors=
Union (factors, tmp);
8832 && uniFactors.
length() != oldUniFactorsLength)
8880 int oldUniFactorsLength= uniFactors.
length();
8889 info2, source, dest, liftBound
8891 factors=
Union (factors, tmp);
8893 && uniFactors.
length() != oldUniFactorsLength)
8910 factors=
Union (earlyFactors, factors);
8911 else if (!earlySuccess && degs.
getLength() == 1)
8912 factors= earlyFactors;
8945 bool extension=
true;
8971 else if (!GF && (
alpha !=
x))
8989 bool primFail=
false;
8992 ASSERT (!primFail,
"failure in integer factorizer");
9009 bool primFail=
false;
9011 ASSERT (!primFail,
"failure in integer factorizer");
9033 bool extension=
true;
9037 if (
ipower (
p, extensionDeg) < (1<<16))
9063 if (
ipower (
p, 2*extensionDeg) < (1<<16))
9079 bool primFail=
false;
9082 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
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.
int getGFDegree() const
getter
bool isInExtension() const
getter
CanonicalForm getGamma() const
getter
CanonicalForm getDelta() const
getter
char getGFName() const
getter
Variable getAlpha() const
getter
Variable getBeta() const
getter
generate random elements in F_p
CanonicalForm generate() const
generate random elements in GF
CanonicalForm generate() const
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
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
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)
for(int j=1;j<=l;j++, i++) tmp1.append(i.getItem())
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)
TIMING_DEFINE_PRINT(fac_fq_uni_factorizer) TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_bi_evaluation) TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_logarithmic) TIMING_DEFINE_PRINT(fac_fq_compute_lattice_lift) TIMING_DEFINE_PRINT(fac_fq_till_reduced) TIMING_DEFINE_PRINT(fac_fq_reconstruction) TIMING_DEFINE_PRINT(fac_fq_lift) TIMING_DEFINE_PRINT(fac_fq_uni_total) CanonicalForm prodMod0(const CFList &L
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...
const ExtensionInfo & info
< [in] sqrfree poly
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)
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
bool delta(X x, Y y, D d)
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)