62 else if (L.length() == 1)
63 return mod (L.getFirst()(0, 1) ,
M);
64 else if (L.length() == 2)
65 return mod (
mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1),
b),
M);
72 for (
int j= 1;
j <=
l;
j++,
i++)
136 if (
find (list, random))
continue;
140 if (!
find (list, random))
146 if (!
find (list, random))
150 }
while (
find (list, random));
159 if (
A.inCoeffDomain())
162 "univariate polynomial expected or constant expected");
174 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
175 nmod_poly_t FLINTmipo, leadingCoeff;
177 fq_nmod_poly_t FLINTA;
178 fq_nmod_poly_factor_t FLINTFactorsA;
186 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
188 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
191 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
196 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
208 zz_pE::init (NTLMipo);
211 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
212 zz_pE multi= to_zz_pE (1);
220 GF2E::init (NTLMipo);
223 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
224 GF2E multi= to_GF2E (1);
241 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
242 nmod_poly_t FLINTmipo, leadingCoeff;
244 fq_nmod_poly_t FLINTA;
245 fq_nmod_poly_factor_t FLINTFactorsA;
253 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
255 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
258 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
263 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
275 zz_pE::init (NTLMipo);
278 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
279 zz_pE multi= to_zz_pE (1);
287 GF2E::init (NTLMipo);
290 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
291 GF2E multi= to_GF2E (1);
303 nmod_poly_factor_t
result;
304 nmod_poly_factor_init (
result);
305 mp_limb_t leadingCoeff= nmod_poly_factor (
result, FLINTA);
307 if (factorsA.
getFirst().factor().inCoeffDomain())
309 nmod_poly_factor_clear (
result);
323 vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
324 zz_p multi= to_zz_p (1);
331 vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
332 GF2 multi= to_GF2 (1);
351 if (factors.
length() == 0)
377 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, M) == F " <<
392 int *
v=
new int [
T.length()];
393 for (
int i= 0;
i <
T.length();
i++)
401 bool nosubset=
false;
403 bool trueFactor=
false;
406 while (
T.length() >= 2*
s &&
s <= thres)
408 while (nosubset ==
false)
436 if (!degs.
find (subsetDeg))
481 buf0=
buf (0,
x)*LCBuf;
487 if (
T.length() < 2*
s ||
T.length() ==
s ||
517 if (
T.length() < 2*
s ||
T.length() ==
s)
535 for (
int i= 0;
i <
T.length();
i++)
539 if (
T.length() < 2*
s)
567 if (factors.
length() == 0)
583 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
586 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
600 int *
v=
new int [
T.length()];
601 for (
int i= 0;
i <
T.length();
i++)
603 bool nosubset=
false;
618 while (
T.length() >= 2*
s &&
s <= thres)
620 while (nosubset ==
false)
648 if (!degs.
find (subsetDeg))
682 if (!
Lc (
g).inBaseDomain())
699 denom /=
gcd (denom, denQuot);
715 if (
T.length() < 2*
s ||
T.length() ==
s ||
742 if (
T.length() < 2*
s ||
T.length() ==
s)
758 for (
int i= 0;
i <
T.length();
i++)
763 if (
T.length() < 2*
s)
810 BuildIrred (NTLIrredpoly,
i*
m);
817 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
873 if (!
Lc (
g).inBaseDomain())
884 factorsFoundIndex[
l]= 1;
910 if (!
buf.inCoeffDomain())
924 adaptedLiftBound= d + 1;
925 if (adaptedLiftBound < deg)
936 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
942 factorsFoundIndex, degs, success, deg,
eval,
b,
den);
947 factors,
int& adaptedLiftBound,
int*& factorsFoundIndex,
965 bool trueFactor=
false;
990 factorsFoundIndex[
l]= 1;
1002 factorsFoundIndex[
l]= 1;
1021 if (!
buf.inCoeffDomain())
1034 adaptedLiftBound= d + 1;
1035 if (adaptedLiftBound < deg)
1054 for (
int i= 0;
i < sizeOfRightSide;
i++)
1060 if (
i.exp() < degreeLC)
1067 ASSERT (
j > 1,
"j > 1 expected" );
1069 int*
result =
new int [
j - 1];
1070 sizeOfOutput=
j - 1;
1086 int sizeOfNewtonPoly;
1088 int sizeOfRightSide;
1089 int * rightSide=
getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1092 delete [] rightSide;
1093 for (
int i= 0;
i < sizeOfNewtonPoly;
i++)
1094 delete [] newtonPolyg[
i];
1095 delete [] newtonPolyg;
1106 if (factorsFoundIndex[
i] == 1)
1133 CFList bufUniFactors= uniFactors;
1136 if (!
Lc (
A).inBaseDomain())
1151 bool mipoHasDen=
false;
1156 lcA0=
lc (
A (0, 2));
1157 A *=
b.inverse (lcA0);
1178 earlySuccess=
false;
1179 int newLiftBound= 0;
1181 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
1183 int * factorsFoundIndex=
new int [uniFactors.
length()];
1184 for (
int i= 0;
i < uniFactors.
length();
i++)
1185 factorsFoundIndex [
i]= 0;
1189 if (smallFactorDeg >= liftBound ||
degree (
A,
y) <= 4)
1191 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1193 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1201 bufBufUniFactors= bufUniFactors;
1212 factorsFoundIndex, degs, earlySuccess,
1216 factorsFoundIndex, degs, earlySuccess,
1221 factorsFoundIndex, degs, earlySuccess,
info,
1222 eval, smallFactorDeg);
1223 if (degs.
getLength() > 1 && !earlySuccess &&
1224 smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1226 if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1230 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant,
M,
b);
1233 bufBufUniFactors= bufUniFactors;
1241 factorsFoundIndex, degs, earlySuccess,
1242 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1245 factorsFoundIndex, degs, earlySuccess,
1246 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1250 factorsFoundIndex, degs, earlySuccess,
info,
1251 eval, liftPre[sizeOfLiftPre-1] + 1);
1254 else if (earlySuccess)
1255 liftBound= newLiftBound;
1257 int i= sizeOfLiftPre - 1;
1258 while (degs.
getLength() > 1 && !earlySuccess &&
i - 1 >= 0)
1260 if (newLiftBound >= liftPre[
i] + 1)
1264 liftPre[
i-1] + 1, Pi, diophant,
M,
b);
1267 bufBufUniFactors= bufUniFactors;
1275 factorsFoundIndex, degs, earlySuccess,
1279 factorsFoundIndex, degs, earlySuccess,
1284 factorsFoundIndex, degs, earlySuccess,
info,
1285 eval, liftPre[
i-1] + 1);
1289 liftBound= newLiftBound;
1295 liftBound= newLiftBound;
1300 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1308 bufBufUniFactors= bufUniFactors;
1318 factorsFoundIndex, degs, earlySuccess,
1322 factorsFoundIndex, degs, earlySuccess,
1327 factorsFoundIndex, degs, earlySuccess,
info,
1328 eval, smallFactorDeg);
1330 while ((
degree (
A,
y)/4)*
i + 4 <= smallFactorDeg)
1333 if (degs.
getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1337 dummy, Pi, diophant,
M,
b);
1340 bufBufUniFactors= bufUniFactors;
1348 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1352 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1357 factorsFoundIndex, degs, earlySuccess,
info,
1360 while (degs.
getLength() > 1 && !earlySuccess &&
i < 4)
1362 if (newLiftBound >= dummy)
1367 dummy, Pi, diophant,
M,
b);
1370 bufBufUniFactors= bufUniFactors;
1378 factorsFoundIndex, degs, earlySuccess, dummy,
1382 factorsFoundIndex, degs, earlySuccess, dummy,
1387 factorsFoundIndex, degs, earlySuccess,
info,
1392 liftBound= newLiftBound;
1398 liftBound= newLiftBound;
1409 delete [] factorsFoundIndex;
1412 return bufUniFactors;
1431 for (
i = 1;
i <=
M.NumRows();
i++)
1434 for (
j = 1;
j <=
M.NumCols();
j++)
1450 for (
i = 1;
i <= nmod_mat_nrows(
M);
i++)
1453 for (
j = 1;
j <= nmod_mat_ncols (
M);
j++)
1455 if (!(nmod_mat_entry (
M,
i-1,
j-1)==0))
1468 for (
i = 1;
i <=
M.NumRows();
i++)
1471 for (
j = 1;
j <=
M.NumCols();
j++)
1486 bool nonZeroOne=
false;
1487 int *
result=
new int [
M.NumCols()];
1488 for (
i = 1;
i <=
M.NumCols();
i++)
1490 for (
j = 1;
j <=
M.NumRows();
j++)
1512 bool nonZeroOne=
false;
1513 int *
result=
new int [nmod_mat_ncols (
M)];
1514 for (
i = 0;
i < nmod_mat_ncols (
M);
i++)
1516 for (
j = 0;
j < nmod_mat_nrows (
M);
j++)
1518 if (!((nmod_mat_entry (
M,
j,
i) == 1) || (nmod_mat_entry (
M,
j,
i) == 0)))
1537 bool nonZeroOne=
false;
1538 int *
result=
new int [
M.NumCols()];
1539 for (
i = 1;
i <=
M.NumCols();
i++)
1541 for (
j = 1;
j <=
M.NumRows();
j++)
1560 factors,
const int liftBound,
int& factorsFound,
int*&
1569 if (factors.
length() == 2)
1581 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1592 for (
long i= 1;
i <=
N.NumCols();
i++)
1594 if (factorsFoundIndex [
i - 1] == 1)
1610 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1621 factorsFoundIndex[
i - 1]= 1;
1629 if (factorsFound + 1 ==
N.NumCols())
1631 reconstructedFactors.
append (bufF);
1636 if (reconstructedFactors.
length() != 0)
1643 factors,
const int liftBound,
int& factorsFound,
int*&
1652 if (factors.
length() == 2)
1664 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1675 for (
long i= 1;
i <=
N.NumCols();
i++)
1677 if (factorsFoundIndex [
i - 1] == 1)
1693 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1704 factorsFoundIndex[
i - 1]= 1;
1712 if (factorsFound + 1 ==
N.NumCols())
1714 reconstructedFactors.
append (bufF);
1719 if (reconstructedFactors.
length() != 0)
1727 factors,
const int liftBound,
int& factorsFound,
int*&
1736 if (factors.
length() == 2)
1748 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1759 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
1761 if (factorsFoundIndex [
i] == 1)
1777 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
1779 if (!(nmod_mat_entry (
N,
j,
i) == 0))
1788 factorsFoundIndex[
i]= 1;
1796 if (factorsFound + 1 == nmod_mat_ncols (
N))
1799 reconstructedFactors.
append (bufF);
1803 if (reconstructedFactors.
length() != 0)
1819 CFList bufFactors= factors;
1821 for (
long i= 1;
i <=
N.NumCols();
i++)
1823 if (zeroOneVecs [
i - 1] == 0)
1827 factorsConsidered=
CFList();
1828 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1843 bufFactors=
Difference (bufFactors, factorsConsidered);
1848 factors= bufFactors;
1853 factors= bufFactors;
1859 int precision,
const mat_zz_pE&
N
1868 CFList bufFactors= factors;
1869 CFList factorsConsidered;
1871 for (
long i= 1;
i <=
N.NumCols();
i++)
1873 if (zeroOneVecs [
i - 1] == 0)
1877 factorsConsidered=
CFList();
1878 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1894 bufFactors=
Difference (bufFactors, factorsConsidered);
1899 factors= bufFactors;
1904 factors= bufFactors;
1925 CFList bufFactors= factors;
1926 CFList factorsConsidered;
1929 for (
long i= 1;
i <=
N.NumCols();
i++)
1931 if (zeroOneVecs [
i - 1] == 0)
1935 factorsConsidered=
CFList();
1936 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1957 bufFactors=
Difference (bufFactors, factorsConsidered);
1972 bufFactors=
Difference (bufFactors, factorsConsidered);
1979 factors= bufFactors;
1984 factors= bufFactors;
2006 CFList bufFactors= factors;
2007 CFList factorsConsidered;
2010 for (
long i= 0;
i < nmod_mat_ncols(
N);
i++)
2012 if (zeroOneVecs [
i] == 0)
2016 factorsConsidered=
CFList();
2017 for (
long j= 0;
j < nmod_mat_nrows(
N);
j++,
iter++)
2019 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2038 bufFactors=
Difference (bufFactors, factorsConsidered);
2053 bufFactors=
Difference (bufFactors, factorsConsidered);
2060 factors= bufFactors;
2065 factors= bufFactors;
2081 CFList bufFactors= factors;
2082 CFList factorsConsidered;
2084 for (
long i= 1;
i <=
N.NumCols();
i++)
2086 if (zeroOneVecs [
i - 1] == 0)
2090 factorsConsidered=
CFList();
2091 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2106 bufFactors=
Difference (bufFactors, factorsConsidered);
2111 factors= bufFactors;
2116 factors= bufFactors;
2132 CFList bufFactors= factors;
2133 CFList factorsConsidered;
2135 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2137 if (zeroOneVecs [
i] == 0)
2141 factorsConsidered=
CFList();
2142 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2144 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2157 bufFactors=
Difference (bufFactors, factorsConsidered);
2162 factors= bufFactors;
2167 factors= bufFactors;
2175 CFList& factors,
const int liftBound,
int& factorsFound,
2176 int*& factorsFoundIndex, mat_zz_p&
N,
bool beenInThres,
2189 if (factors.
length() == 2)
2199 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2231 for (
long i= 1;
i <=
N.NumCols();
i++)
2233 if (factorsFoundIndex [
i - 1] == 1)
2249 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2265 factorsFoundIndex[
i - 1]= 1;
2280 factorsFoundIndex[
i - 1]= 1;
2291 if (factorsFound + 1 ==
N.NumCols())
2295 reconstructedFactors.
append (tmp);
2305 CFList& factors,
const int liftBound,
int& factorsFound,
2306 int*& factorsFoundIndex, nmod_mat_t
N,
bool beenInThres,
2319 if (factors.
length() == 2)
2329 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2361 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2363 if (factorsFoundIndex [
i] == 1)
2379 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2381 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2395 factorsFoundIndex[
i]= 1;
2410 factorsFoundIndex[
i]= 1;
2421 if (factorsFound + 1 == nmod_mat_nrows (
N))
2425 reconstructedFactors.
append (tmp);
2436 start,
int liftBound,
int minBound,
CFList& factors,
2443 bool wasInBounds=
false;
2444 bool hitBound=
false;
2445 int l= (minBound+1)*2;
2448 bool reduced=
false;
2449 mat_zz_p NTLK, *NTLC;
2455 while (
l <= liftBound)
2471 "time to lift in compute lattice: ");
2479 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2488 "time to compute logarithmic derivative: ");
2490 for (
int i= 0;
i < sizeBounds;
i++)
2492 if (bounds [
i] + 1 <=
l/2)
2495 int k=
tmin (bounds [
i] + 1,
l/2);
2497 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2499 if (
A[ii].
size() - 1 >=
i)
2507 transpose (NTLK, NTLK);
2508 kernel (NTLK, NTLK);
2509 transpose (NTLK, NTLK);
2513 if (NTLN.NumCols() == 1)
2560 start,
int liftBound,
int minBound,
CFList& factors,
2567 bool wasInBounds=
false;
2568 bool hitBound=
false;
2569 int l= (minBound+1)*2;
2572 bool reduced=
false;
2574 nmod_mat_t FLINTK, FLINTC,
null;
2580 while (
l <= liftBound)
2596 "time to lift in compute lattice: ");
2604 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2613 "time to compute logarithmic derivative: ");
2615 for (
int i= 0;
i < sizeBounds;
i++)
2617 if (bounds [
i] + 1 <=
l/2)
2620 int k=
tmin (bounds [
i] + 1,
l/2);
2622 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2624 if (
A[ii].
size() - 1 >=
i)
2632 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2634 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2635 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2637 rank= nmod_mat_nullspace (
null, FLINTK);
2638 nmod_mat_clear (FLINTK);
2639 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
2640 nmod_mat_clear (FLINTC);
2641 nmod_mat_init_set (FLINTC, FLINTN);
2642 nmod_mat_clear (FLINTN);
2643 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2645 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
2647 nmod_mat_clear (FLINTC);
2648 nmod_mat_window_clear (FLINTK);
2649 nmod_mat_clear (
null);
2650 if (nmod_mat_ncols (FLINTN) == 1)
2655 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
2698 int liftBound,
int minBound,
int start,
CFList&
2699 factors, mat_zz_p& NTLN,
CFList& diophant,
2708 bool wasInBounds=
false;
2709 bool hitBound=
false;
2720 int l= ((minBound+1)/degMipo+1)*2;
2725 bool reduced=
false;
2732 mat_zz_p* NTLMat, *NTLC, NTLK;
2734 while (
l <= liftBound)
2750 "time to lift in compute lattice: ");
2759 for (
int i= 0;
i <
l*degMipo;
i++)
2762 imBasis= imBasis (
power (
y, degMipo),
y);
2763 imBasis= imBasis (
y, gamma);
2770 *NTLMat= inv (*NTLMat);
2780 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2789 "time to compute logarithmic derivative: ");
2791 for (
int i= 0;
i < sizeBounds;
i++)
2793 if (bounds [
i] + 1 <= (
l/2)*degMipo)
2796 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
2799 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2801 if (
A[ii].
size() - 1 >=
i)
2809 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2818 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
2834 transpose (NTLK, NTLK);
2835 kernel (NTLK, NTLK);
2836 transpose (NTLK, NTLK);
2843 if (NTLN.NumCols() == 1)
2858 if (NTLN.NumCols() == 1)
2896 int liftBound,
int minBound,
int start,
CFList&
2897 factors, nmod_mat_t FLINTN,
CFList& diophant,
2906 bool wasInBounds=
false;
2907 bool hitBound=
false;
2918 int l= ((minBound+1)/degMipo+1)*2;
2923 bool reduced=
false;
2931 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
2933 while (
l <= liftBound)
2955 for (
int i= 0;
i <
l*degMipo;
i++)
2958 imBasis= imBasis (
power (
y, degMipo),
y);
2959 imBasis= imBasis (
y, gamma);
2966 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
2968 nmod_mat_inv (FLINTMatInv, FLINTMat);
2977 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2986 for (
int i= 0;
i < sizeBounds;
i++)
2988 if (bounds [
i] + 1 <= (
l/2)*degMipo)
2991 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
2994 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2996 if (
A[ii].
size() - 1 >=
i)
3004 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3013 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3028 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3030 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3031 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3033 rank= nmod_mat_nullspace (
null, FLINTK);
3034 nmod_mat_clear (FLINTK);
3035 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3036 nmod_mat_clear (FLINTC);
3037 nmod_mat_init_set (FLINTC, FLINTN);
3038 nmod_mat_clear (FLINTN);
3039 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3041 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3043 nmod_mat_clear (FLINTC);
3044 nmod_mat_window_clear (FLINTK);
3045 nmod_mat_clear (
null);
3050 if (nmod_mat_ncols (FLINTN) == 1)
3063 nmod_mat_clear (FLINTMat);
3064 nmod_mat_clear (FLINTMatInv);
3066 if (nmod_mat_ncols (FLINTN) == 1)
3103 int start,
int liftBound,
int minBound,
CFList& factors,
3110 bool wasInBounds=
false;
3111 bool hitBound=
false;
3112 int l= (minBound+1)*2;
3115 bool reduced=
false;
3117 mat_zz_pE* NTLC, NTLK;
3122 while (
l <= liftBound)
3138 "time to lift in compute lattice: ");
3146 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3148 if (
l == (minBound+1)*2)
3160 "time to compute logarithmic derivative: ");
3162 for (
int i= 0;
i < sizeBounds;
i++)
3164 if (bounds [
i] + 1 <=
l/2)
3167 int k=
tmin (bounds [
i] + 1,
l/2);
3169 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3172 if (
A[ii].
size() - 1 >=
i)
3181 transpose (NTLK, NTLK);
3182 kernel (NTLK, NTLK);
3183 transpose (NTLK, NTLK);
3187 if (NTLN.NumCols() == 1)
3200 if (NTLN.NumCols() == 1)
3236 int start,
int liftBound,
int minBound,
CFList&
3237 factors, nmod_mat_t FLINTN,
CFList& diophant,
3244 int start,
int liftBound,
int minBound,
CFList&
3253 bool wasInBounds=
false;
3254 int l= (minBound+1)*2;
3257 bool hitBound=
false;
3259 bool reduced=
false;
3265 nmod_mat_t FLINTC, FLINTK,
null;
3267 mat_zz_p* NTLC, NTLK;
3271 while (
l <= liftBound)
3287 "time to lift in compute lattice: ");
3295 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3297 if (
l == (minBound+1)*2)
3309 "time to compute logarithmic derivative: ");
3311 for (
int i= 0;
i < sizeBounds;
i++)
3313 if (bounds [
i] + 1 <=
l/2)
3316 int k=
tmin (bounds [
i] + 1,
l/2);
3318 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3320 if (
A[ii].
size() - 1 >=
i)
3329 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3331 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3332 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3334 rank= nmod_mat_nullspace (
null, FLINTK);
3335 nmod_mat_clear (FLINTK);
3336 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3337 nmod_mat_clear (FLINTC);
3338 nmod_mat_init_set (FLINTC, FLINTN);
3339 nmod_mat_clear (FLINTN);
3340 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3342 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3344 nmod_mat_clear (FLINTC);
3345 nmod_mat_window_clear (FLINTK);
3346 nmod_mat_clear (
null);
3350 transpose (NTLK, NTLK);
3351 kernel (NTLK, NTLK);
3352 transpose (NTLK, NTLK);
3358 if (nmod_mat_nrows (FLINTN) == 1)
3360 if (NTLN.NumCols() == 1)
3367 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
3379 if (nmod_mat_ncols (FLINTN) == 1)
3381 if (NTLN.NumCols() == 1)
3417 int oldNumCols,
int oldL,
int precision,
3437 for (
long i=factors.
length()-1;
i >= 0;
i--)
3438 nmod_mat_entry (FLINTN,
i,
i)= 1;
3441 ident (NTLN, factors.
length());
3443 int minBound= bounds[0];
3444 for (
int i= 1;
i < d;
i++)
3447 minBound=
tmin (minBound, bounds[
i]);
3449 int l=
tmax (2*(minBound + 1), oldL);
3452 bool useOldQs=
false;
3453 bool hitBound=
false;
3459 nmod_mat_t FLINTC, FLINTK,
null;
3461 mat_zz_p* NTLC, NTLK;
3464 while (
l <= precision)
3470 for (
int i= 0;
i < factors.
length();
i++,
j++)
3477 for (
int i= 0;
i < factors.
length();
i++,
j++)
3481 for (
int i= 0;
i < d;
i++)
3483 if (bounds [
i] + 1 <=
l/2)
3485 int k=
tmin (bounds [
i] + 1,
l/2);
3487 for (
int ii= 0; ii < factors.
length(); ii++)
3489 if (
A[ii].
size() - 1 >=
i)
3497 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3499 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3500 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3502 rank= nmod_mat_nullspace (
null, FLINTK);
3503 nmod_mat_clear (FLINTK);
3504 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3505 nmod_mat_clear (FLINTC);
3506 nmod_mat_init_set (FLINTC, FLINTN);
3507 nmod_mat_clear (FLINTN);
3508 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3510 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3512 nmod_mat_clear (FLINTC);
3513 nmod_mat_window_clear (FLINTK);
3514 nmod_mat_clear (
null);
3518 transpose (NTLK, NTLK);
3519 kernel (NTLK, NTLK);
3520 transpose (NTLK, NTLK);
3525 if (nmod_mat_ncols (FLINTN) == 1)
3527 nmod_mat_clear (FLINTN);
3529 if (NTLN.NumCols() == 1)
3542 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3546 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
3547 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
3549 if (NTLN.NumCols() < oldNumCols - factorsFound)
3553 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3554 for (
long i= 0;
i < NTLN.NumCols();
i++)
3556 factorsFoundIndex[
i]= 0;
3557 int factorsFound2= 0;
3562 factorsFoundIndex, FLINTN,
eval,
false
3564 if (
result.length() == nmod_mat_ncols (FLINTN))
3566 nmod_mat_clear (FLINTN);
3569 factorsFoundIndex, NTLN,
eval,
false
3571 if (
result.length() == NTLN.NumCols())
3574 delete [] factorsFoundIndex;
3580 delete [] factorsFoundIndex;
3582 else if (
l == precision)
3588 nmod_mat_clear (FLINTN);
3615 nmod_mat_clear (FLINTN);
3624 int oldNumCols,
int oldL,
const Variable&,
3642 ident (NTLN, factors.
length());
3643 int minBound= bounds[0];
3644 for (
int i= 1;
i < d;
i++)
3647 minBound=
tmin (minBound, bounds[
i]);
3649 int l=
tmax (2*(minBound + 1), oldL);
3652 bool useOldQs=
false;
3653 bool hitBound=
false;
3656 mat_zz_pE* NTLC, NTLK;
3659 while (
l <= precision)
3665 for (
int i= 0;
i < factors.
length();
i++,
j++)
3672 for (
int i= 0;
i < factors.
length();
i++,
j++)
3676 for (
int i= 0;
i < d;
i++)
3678 if (bounds [
i] + 1 <=
l/2)
3680 int k=
tmin (bounds [
i] + 1,
l/2);
3682 for (
int ii= 0; ii < factors.
length(); ii++)
3684 if (
A[ii].
size() - 1 >=
i)
3692 transpose (NTLK, NTLK);
3693 kernel (NTLK, NTLK);
3694 transpose (NTLK, NTLK);
3697 if (NTLN.NumCols() == 1)
3708 if (NTLN.NumCols() < oldNumCols - factorsFound)
3712 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3713 for (
long i= 0;
i < NTLN.NumCols();
i++)
3714 factorsFoundIndex[
i]= 0;
3715 int factorsFound2= 0;
3719 factorsFoundIndex, NTLN,
eval,
false);
3720 if (
result.length() == NTLN.NumCols())
3722 delete [] factorsFoundIndex;
3728 delete [] factorsFoundIndex;
3730 else if (
l == precision)
3791 for (
long i=factors.
length()-1;
i >= 0;
i--)
3792 nmod_mat_entry (FLINTN,
i,
i)= 1;
3800 ident (NTLN, factors.
length());
3802 int minBound= bounds[0];
3803 for (
int i= 1;
i < d;
i++)
3806 minBound=
tmin (minBound, bounds[
i]);
3808 int l=
tmax (oldL, 2*((minBound+1)/degMipo+1));
3811 bool useOldQs=
false;
3812 bool hitBound=
false;
3823 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
3825 mat_zz_p* NTLMat,*NTLC, NTLK;
3828 while (
l <= precision)
3835 for (
int i= 0;
i <
l*degMipo;
i++)
3838 imBasis= imBasis (
power (
y, degMipo),
y);
3839 imBasis= imBasis (
y, gamma);
3847 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3849 nmod_mat_inv (FLINTMatInv, FLINTMat);
3852 *NTLMat= inv (*NTLMat);
3861 for (
int i= 0;
i < factors.
length();
i++,
j++)
3868 for (
int i= 0;
i < factors.
length();
i++,
j++)
3872 for (
int i= 0;
i < d;
i++)
3874 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3876 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3878 for (
int ii= 0; ii < factors.
length(); ii++)
3880 if (
A[ii].
size() - 1 >=
i)
3888 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3901 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3921 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3923 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3924 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3926 rank= nmod_mat_nullspace (
null, FLINTK);
3927 nmod_mat_clear (FLINTK);
3928 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3929 nmod_mat_clear (FLINTC);
3930 nmod_mat_init_set (FLINTC, FLINTN);
3931 nmod_mat_clear (FLINTN);
3932 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3934 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3936 nmod_mat_clear (FLINTC);
3937 nmod_mat_window_clear (FLINTK);
3938 nmod_mat_clear (
null);
3942 transpose (NTLK, NTLK);
3943 kernel (NTLK, NTLK);
3944 transpose (NTLK, NTLK);
3953 if (nmod_mat_ncols (FLINTN) == 1)
3955 nmod_mat_clear (FLINTMat);
3956 nmod_mat_clear (FLINTMatInv);
3957 nmod_mat_clear (FLINTN);
3959 if (NTLN.NumCols() == 1)
3976 nmod_mat_clear (FLINTMat);
3977 nmod_mat_clear (FLINTMatInv);
3983 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3987 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
3988 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
3990 if (NTLN.NumCols() < oldNumCols - factorsFound)
3994 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3995 for (
long i= 0;
i < NTLN.NumCols();
i++)
3997 factorsFoundIndex[
i]= 0;
3998 int factorsFound2= 0;
4005 if (
result.length() == nmod_mat_ncols (FLINTN))
4007 nmod_mat_clear (FLINTN);
4012 if (
result.length() == NTLN.NumCols())
4015 delete [] factorsFoundIndex;
4021 delete [] factorsFoundIndex;
4023 else if (
l == precision)
4031 nmod_mat_clear (FLINTN);
4061 nmod_mat_clear (FLINTN);
4088 zz_pE::init (NTLMipo);
4090 ident (NTLN, factors.
length());
4091 int minBound= bounds[0];
4092 for (
int i= 1;
i < d;
i++)
4095 minBound=
tmin (minBound, bounds[
i]);
4097 int l=
tmin (2*(minBound + 1), precision);
4100 bool useOldQs=
false;
4101 bool hitBound=
false;
4105 mat_zz_pE* NTLC, NTLK;
4108 while (
l <= precision)
4114 for (
int i= 0;
i < factors.
length();
i++,
j++)
4119 for (
int i= 0;
i < factors.
length();
i++,
j++)
4123 for (
int i= 0;
i < d;
i++)
4125 if (bounds [
i] + 1 <=
l/2)
4127 int k=
tmin (bounds [
i] + 1,
l/2);
4129 for (
int ii= 0; ii < factors.
length(); ii++)
4131 if (
A[ii].
size() - 1 >=
i)
4139 transpose (NTLK, NTLK);
4140 kernel (NTLK, NTLK);
4141 transpose (NTLK, NTLK);
4145 if (NTLN.NumCols() == 1)
4158 CFList bufFactors= factors;
4162 if (
result.length() != NTLN.NumCols() &&
l != precision)
4163 factors= bufFactors;
4164 if (
result.length() == NTLN.NumCols())
4222 for (
long i=factors.
length()-1;
i >= 0;
i--)
4223 nmod_mat_entry (FLINTN,
i,
i)= 1;
4226 ident (NTLN, factors.
length());
4228 int minBound= bounds[0];
4229 for (
int i= 1;
i < d;
i++)
4232 minBound=
tmin (minBound, bounds[
i]);
4234 int l=
tmax (2*(minBound + 1), oldL);
4237 bool useOldQs=
false;
4238 bool hitBound=
false;
4243 nmod_mat_t FLINTC, FLINTK,
null;
4245 mat_zz_p* NTLC, NTLK;
4249 while (
l <= precision)
4255 for (
int i= 0;
i < factors.
length();
i++,
j++)
4262 for (
int i= 0;
i < factors.
length();
i++,
j++)
4266 for (
int i= 0;
i < d;
i++)
4268 if (bounds [
i] + 1 <=
l/2)
4270 int k=
tmin (bounds [
i] + 1,
l/2);
4272 for (
int ii= 0; ii < factors.
length(); ii++)
4274 if (
A[ii].
size() - 1 >=
i)
4282 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4284 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4285 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4287 rank= nmod_mat_nullspace (
null, FLINTK);
4288 nmod_mat_clear (FLINTK);
4289 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
4290 nmod_mat_clear (FLINTC);
4291 nmod_mat_init_set (FLINTC, FLINTN);
4292 nmod_mat_clear (FLINTN);
4293 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4295 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4297 nmod_mat_clear (FLINTC);
4298 nmod_mat_window_clear (FLINTK);
4299 nmod_mat_clear (
null);
4303 transpose (NTLK, NTLK);
4304 kernel (NTLK, NTLK);
4305 transpose (NTLK, NTLK);
4310 if (nmod_mat_ncols (FLINTN) == 1)
4312 nmod_mat_clear (FLINTN);
4314 if (NTLN.NumCols() == 1)
4327 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4331 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4332 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4334 if (NTLN.NumCols() < oldNumCols - factorsFound)
4338 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4339 for (
long i= 0;
i < NTLN.NumCols();
i++)
4341 factorsFoundIndex[
i]= 0;
4342 int factorsFound2= 0;
4347 factorsFoundIndex, FLINTN,
eval,
false
4349 if (
result.length() == nmod_mat_ncols (FLINTN))
4351 nmod_mat_clear (FLINTN);
4354 factorsFoundIndex, NTLN,
eval,
false
4356 if (
result.length() == NTLN.NumCols())
4359 delete [] factorsFoundIndex;
4365 delete [] factorsFoundIndex;
4367 else if (
l == precision)
4373 nmod_mat_clear (FLINTN);
4400 nmod_mat_clear (FLINTN);
4410 l,
int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
4416 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
4424 bool hitBound=
false;
4426 if (nmod_mat_nrows (FLINTN) != factors.
length())
4428 nmod_mat_clear (FLINTN);
4430 for (
long i=factors.
length()-1;
i >= 0;
i--)
4431 nmod_mat_entry (FLINTN,
i,
i)= 1;
4435 if (NTLN.NumRows() != factors.
length())
4437 ident (NTLN, factors.
length());
4441 bool useOldQs=
false;
4447 nmod_mat_t FLINTC, FLINTK,
null;
4449 mat_zz_p* NTLC, NTLK;
4460 for (
int i= 0;
i < factors.
length();
i++,
j++)
4467 for (
int i= 0;
i < factors.
length();
i++,
j++)
4472 for (
int i= 0;
i < d;
i++)
4474 if (bounds [
i] + 1 <= oldL/2)
4476 int k=
tmin (bounds [
i] + 1, oldL/2);
4478 for (
int ii= 0; ii < factors.
length(); ii++)
4480 if (
A[ii].
size() - 1 >=
i)
4488 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4490 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4491 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4493 rank= nmod_mat_nullspace (
null, FLINTK);
4494 nmod_mat_clear (FLINTK);
4495 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
4496 nmod_mat_clear (FLINTC);
4497 nmod_mat_init_set (FLINTC, FLINTN);
4498 nmod_mat_clear (FLINTN);
4499 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4501 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4503 nmod_mat_clear (FLINTC);
4504 nmod_mat_window_clear (FLINTK);
4505 nmod_mat_clear (
null);
4509 transpose (NTLK, NTLK);
4510 kernel (NTLK, NTLK);
4511 transpose (NTLK, NTLK);
4516 if (nmod_mat_ncols (FLINTN) == 1)
4518 if (NTLN.NumCols() == 1)
4527 if (nmod_mat_ncols (FLINTN) == 1)
4529 if (NTLN.NumCols() == 1)
4542 bufUniFactors= factors;
4548 delete [] zeroOneVecs;
4552 factors= bufUniFactors;
4577 l,
int d,
int* bounds,
CFArray& bufQ, mat_zz_pE& NTLN,
4584 bool hitBound=
false;
4585 bool useOldQs=
false;
4586 if (NTLN.NumRows() != factors.
length())
4587 ident (NTLN, factors.
length());
4591 mat_zz_pE* NTLC, NTLK;
4601 for (
int i= 0;
i < factors.
length();
i++,
j++)
4608 for (
int i= 0;
i < factors.
length();
i++,
j++)
4613 for (
int i= 0;
i < d;
i++)
4615 if (bounds [
i] + 1 <= oldL/2)
4617 int k=
tmin (bounds [
i] + 1, oldL/2);
4619 for (
int ii= 0; ii < factors.
length(); ii++)
4621 if (
A[ii].
size() - 1 >=
i)
4629 transpose (NTLK, NTLK);
4630 kernel (NTLK, NTLK);
4631 transpose (NTLK, NTLK);
4635 if (NTLN.NumCols() == 1)
4642 if (NTLN.NumCols() == 1)
4651 bufUniFactors= factors;
4653 delete [] zeroOneVecs;
4657 factors= bufUniFactors;
4684 int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
const
4691 int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
const
4700 bool hitBound=
false;
4701 bool useOldQs=
false;
4710 nmod_mat_clear (FLINTN);
4712 for (
long i=factors.
length()-1;
i >= 0;
i--)
4713 nmod_mat_entry (FLINTN,
i,
i)= 1;
4715 if (NTLN.NumRows() != factors.
length())
4716 ident (NTLN, factors.
length());
4726 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
4728 mat_zz_p* NTLC, NTLK, *NTLMat;
4737 powX=
power (
y-gamma, oldL);
4738 Mat=
CFMatrix (oldL*degMipo, oldL*degMipo);
4739 for (
int i= 0;
i < oldL*degMipo;
i++)
4742 imBasis= imBasis (
power (
y, degMipo),
y);
4743 imBasis= imBasis (
y, gamma);
4751 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
4753 nmod_mat_inv (FLINTMatInv, FLINTMat);
4756 *NTLMat= inv (*NTLMat);
4765 for (
int i= 0;
i < factors.
length();
i++,
j++)
4771 for (
int i= 0;
i < factors.
length();
i++,
j++)
4776 for (
int i= 0;
i < d;
i++)
4778 if (bounds [
i] + 1 <= oldL/2)
4780 int k=
tmin (bounds [
i] + 1, oldL/2);
4782 for (
int ii= 0; ii < factors.
length(); ii++)
4784 if (
A[ii].
size() - 1 >=
i)
4792 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4805 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4825 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4827 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4828 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4830 rank= nmod_mat_nullspace (
null, FLINTK);
4831 nmod_mat_clear (FLINTK);
4832 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
4833 nmod_mat_clear (FLINTC);
4834 nmod_mat_init_set (FLINTC, FLINTN);
4835 nmod_mat_clear (FLINTN);
4836 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4838 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4840 nmod_mat_clear (FLINTC);
4841 nmod_mat_window_clear (FLINTK);
4842 nmod_mat_clear (
null);
4846 transpose (NTLK, NTLK);
4847 kernel (NTLK, NTLK);
4848 transpose (NTLK, NTLK);
4857 if (nmod_mat_ncols (FLINTN) == 1)
4859 nmod_mat_clear (FLINTMat);
4860 nmod_mat_clear (FLINTMatInv);
4862 if (NTLN.NumCols() == 1)
4877 nmod_mat_clear (FLINTMat);
4878 nmod_mat_clear (FLINTMatInv);
4884 if (nmod_mat_ncols (FLINTN) == 1)
4886 if (NTLN.NumCols() == 1)
4899 bufUniFactors= factors;
4911 delete [] zeroOneVecs;
4915 factors= bufUniFactors;
4940 int d,
int* bounds,
CFArray& bufQ, nmod_mat_t FLINTN,
4946 int d,
int* bounds,
CFArray& bufQ, mat_zz_p& NTLN,
4955 bool hitBound=
false;
4956 bool useOldQs=
false;
4958 if (nmod_mat_nrows (FLINTN) != factors.
length())
4960 nmod_mat_clear (FLINTN);
4962 for (
long i=factors.
length()-1;
i >= 0;
i--)
4963 nmod_mat_entry (FLINTN,
i,
i)= 1;
4966 if (NTLN.NumRows() != factors.
length())
4967 ident (NTLN, factors.
length());
4974 nmod_mat_t FLINTC, FLINTK,
null;
4976 mat_zz_p* NTLC, NTLK;
4987 for (
int i= 0;
i < factors.
length();
i++,
j++)
4994 for (
int i= 0;
i < factors.
length();
i++,
j++)
4999 for (
int i= 0;
i < d;
i++)
5001 if (bounds [
i] + 1 <= oldL/2)
5003 int k=
tmin (bounds [
i] + 1, oldL/2);
5005 for (
int ii= 0; ii < factors.
length(); ii++)
5007 if (
A[ii].
size() - 1 >=
i)
5015 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5017 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5018 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5020 rank= nmod_mat_nullspace (
null, FLINTK);
5021 nmod_mat_clear (FLINTK);
5022 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5023 nmod_mat_clear (FLINTC);
5024 nmod_mat_init_set (FLINTC, FLINTN);
5025 nmod_mat_clear (FLINTN);
5026 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5028 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5030 nmod_mat_clear (FLINTC);
5031 nmod_mat_window_clear (FLINTK);
5032 nmod_mat_clear (
null);
5036 transpose (NTLK, NTLK);
5037 kernel (NTLK, NTLK);
5038 transpose (NTLK, NTLK);
5043 if (nmod_mat_ncols (FLINTN) == 1)
5045 if (NTLN.NumCols() == 1)
5062 bufUniFactors= factors;
5068 delete [] zeroOneVecs;
5072 factors= bufUniFactors;
5098 factors,
int l,
int liftBound,
int d,
int*
5099 bounds, nmod_mat_t FLINTN,
CFList& diophant,
5106 factors,
int l,
int liftBound,
int d,
int*
5107 bounds, mat_zz_p& NTLN,
CFList& diophant,
5116 CFList bufFactors= factors;
5119 bool useOldQs=
false;
5120 bool hitBound=
false;
5125 if (nmod_mat_nrows (FLINTN) != factors.
length())
5127 nmod_mat_clear (FLINTN);
5129 for (
long i=factors.
length()-1;
i >= 0;
i--)
5130 nmod_mat_entry (FLINTN,
i,
i)= 1;
5133 if (NTLN.NumRows() != factors.
length())
5134 ident (NTLN, factors.
length());
5141 nmod_mat_t FLINTC, FLINTK,
null;
5143 mat_zz_p* NTLC, NTLK;
5147 while (
l <= liftBound)
5155 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5161 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5164 for (
int i= 0;
i < d;
i++)
5166 if (bounds [
i] + 1 <=
l/2)
5168 int k=
tmin (bounds [
i] + 1,
l/2);
5170 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5172 if (
A[ii].
size() - 1 >=
i)
5180 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5182 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5183 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5185 rank= nmod_mat_nullspace (
null, FLINTK);
5186 nmod_mat_clear (FLINTK);
5187 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5188 nmod_mat_clear (FLINTC);
5189 nmod_mat_init_set (FLINTC, FLINTN);
5190 nmod_mat_clear (FLINTN);
5191 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5193 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5195 nmod_mat_clear (FLINTC);
5196 nmod_mat_window_clear (FLINTK);
5197 nmod_mat_clear (
null);
5201 transpose (NTLK, NTLK);
5202 kernel (NTLK, NTLK);
5203 transpose (NTLK, NTLK);
5208 if (nmod_mat_ncols (FLINTN) == 1)
5210 if (NTLN.NumCols() == 1)
5220 if (nmod_mat_ncols (FLINTN) == 1)
5222 if (NTLN.NumCols() == 1)
5235 bufBufFactors= bufFactors;
5241 delete [] zeroOneVecs;
5245 factors= bufFactors;
5252 bufFactors= bufBufFactors;
5261 int factorsFound= 0;
5264 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5265 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5267 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5268 for (
long i= 0;
i < NTLN.NumCols();
i++)
5270 factorsFoundIndex[
i]= 0;
5274 factorsFoundIndex, FLINTN,
eval,
false
5278 degree (
LCF), factorsFound, factorsFoundIndex,
5282 if (nmod_mat_ncols (FLINTN) ==
result.length())
5286 factorsFoundIndex, NTLN,
eval,
false
5290 degree (
LCF), factorsFound, factorsFoundIndex,
5294 if (NTLN.NumCols() ==
result.length())
5298 delete [] factorsFoundIndex;
5301 delete [] factorsFoundIndex;
5324 factors= bufFactors;
5331 factors,
int l,
int liftBound,
int d,
int*
5332 bounds, mat_zz_pE& NTLN,
CFList& diophant,
5340 CFList bufFactors= factors;
5343 bool useOldQs=
false;
5344 bool hitBound=
false;
5348 if (NTLN.NumRows() != factors.
length())
5349 ident (NTLN, factors.
length());
5352 mat_zz_pE* NTLC, NTLK;
5355 while (
l <= liftBound)
5363 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5369 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5372 for (
int i= 0;
i < d;
i++)
5374 if (bounds [
i] + 1 <=
l/2)
5376 int k=
tmin (bounds [
i] + 1,
l/2);
5378 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5380 if (
A[ii].
size() - 1 >=
i)
5388 transpose (NTLK, NTLK);
5389 kernel (NTLK, NTLK);
5390 transpose (NTLK, NTLK);
5393 if (NTLN.NumCols() == 1)
5400 if (NTLN.NumCols() == 1)
5408 bufBufFactors= bufFactors;
5410 delete [] zeroOneVecs;
5414 factors= bufFactors;
5421 bufFactors= bufBufFactors;
5426 int factorsFound= 0;
5428 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5429 for (
long i= 0;
i < NTLN.NumCols();
i++)
5430 factorsFoundIndex[
i]= 0;
5433 factorsFoundIndex, NTLN,
eval,
false
5437 degree (
LCF), factorsFound, factorsFoundIndex,
5440 if (NTLN.NumCols() ==
result.length())
5443 delete [] factorsFoundIndex;
5446 delete [] factorsFoundIndex;
5469 factors= bufFactors;
5477 int liftBound,
int d,
int* bounds,
5478 nmod_mat_t FLINTN,
CFList& diophant,
5487 int liftBound,
int d,
int* bounds,
5488 mat_zz_p& NTLN,
CFList& diophant,
5499 CFList bufFactors= factors;
5502 bool useOldQs=
false;
5503 bool hitBound=
false;
5514 nmod_mat_clear (FLINTN);
5516 for (
long i=factors.
length()-1;
i >= 0;
i--)
5517 nmod_mat_entry (FLINTN,
i,
i)= 1;
5519 if (NTLN.NumRows() != factors.
length())
5520 ident (NTLN, factors.
length());
5528 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
5530 mat_zz_p* NTLMat,*NTLC, NTLK;
5534 while (
l <= liftBound)
5544 for (
int i= 0;
i <
l*degMipo;
i++)
5548 imBasis= imBasis (
power (
y, degMipo),
y);
5549 imBasis= imBasis (
y, gamma);
5557 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
5559 nmod_mat_inv (FLINTMatInv, FLINTMat);
5562 *NTLMat= inv (*NTLMat);
5572 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5578 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5581 for (
int i= 0;
i < d;
i++)
5583 if (bounds [
i] + 1 <=
l/2)
5585 int k=
tmin (bounds [
i] + 1,
l/2);
5587 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5589 if (
A[ii].
size() - 1 >=
i)
5597 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5610 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5630 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5632 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5633 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5635 rank= nmod_mat_nullspace (
null, FLINTK);
5636 nmod_mat_clear (FLINTK);
5637 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5638 nmod_mat_clear (FLINTC);
5639 nmod_mat_init_set (FLINTC, FLINTN);
5640 nmod_mat_clear (FLINTN);
5641 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5643 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5645 nmod_mat_clear (FLINTC);
5646 nmod_mat_window_clear (FLINTK);
5647 nmod_mat_clear (
null);
5651 transpose (NTLK, NTLK);
5652 kernel (NTLK, NTLK);
5653 transpose (NTLK, NTLK);
5662 if (nmod_mat_ncols (FLINTN) == 1)
5664 if (NTLN.NumCols() == 1)
5674 nmod_mat_clear (FLINTMat);
5675 nmod_mat_clear (FLINTMatInv);
5676 if (nmod_mat_ncols (FLINTN) == 1)
5679 if (NTLN.NumCols() == 1)
5687 bufBufFactors= bufFactors;
5699 delete [] zeroOneVecs;
5703 factors= bufFactors;
5710 bufFactors= bufBufFactors;
5719 int factorsFound= 0;
5722 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5723 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5725 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5726 for (
long i= 0;
i < NTLN.NumCols();
i++)
5728 factorsFoundIndex[
i]= 0;
5736 degree (
LCF), factorsFound, factorsFoundIndex,
5739 if (nmod_mat_ncols (FLINTN) ==
result.length())
5747 degree (
LCF), factorsFound, factorsFoundIndex,
5750 if (NTLN.NumCols() ==
result.length())
5754 delete [] factorsFoundIndex;
5757 delete [] factorsFoundIndex;
5784 factors= bufFactors;
5791 l,
int liftBound,
int d,
int* bounds,
5792 nmod_mat_t FLINTN,
CFList& diophant,
5800 l,
int liftBound,
int d,
int* bounds,
5801 mat_zz_p& NTLN,
CFList& diophant,
5811 CFList bufFactors= factors;
5814 bool useOldQs=
false;
5816 bool hitBound=
false;
5821 if (nmod_mat_nrows (FLINTN) != factors.
length())
5823 nmod_mat_clear (FLINTN);
5825 for (
long i=factors.
length()-1;
i >= 0;
i--)
5826 nmod_mat_entry (FLINTN,
i,
i)= 1;
5829 if (NTLN.NumRows() != factors.
length())
5830 ident (NTLN, factors.
length());
5836 nmod_mat_t FLINTC, FLINTK,
null;
5838 mat_zz_p* NTLC, NTLK;
5842 while (
l <= liftBound)
5850 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5856 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5859 for (
int i= 0;
i < d;
i++)
5861 if (bounds [
i] + 1 <=
l/2)
5863 int k=
tmin (bounds [
i] + 1,
l/2);
5865 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5868 if (
A[ii].
size() - 1 >=
i)
5876 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5878 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5879 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5881 rank= nmod_mat_nullspace (
null, FLINTK);
5882 nmod_mat_clear (FLINTK);
5883 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5884 nmod_mat_clear (FLINTC);
5885 nmod_mat_init_set (FLINTC, FLINTN);
5886 nmod_mat_clear (FLINTN);
5887 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5889 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5891 nmod_mat_clear (FLINTC);
5892 nmod_mat_window_clear (FLINTK);
5893 nmod_mat_clear (
null);
5897 transpose (NTLK, NTLK);
5898 kernel (NTLK, NTLK);
5899 transpose (NTLK, NTLK);
5904 if (nmod_mat_ncols (FLINTN) == 1)
5906 if (NTLN.NumCols() == 1)
5915 if (nmod_mat_ncols (FLINTN) == 1)
5917 if (NTLN.NumCols() == 1)
5930 bufBufFactors= bufFactors;
5936 delete [] zeroOneVecs;
5940 factors= bufFactors;
5947 bufFactors= bufBufFactors;
5956 int factorsFound= 0;
5959 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5960 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5962 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5963 for (
long i= 0;
i < NTLN.NumCols();
i++)
5965 factorsFoundIndex[
i]= 0;
5969 factorsFoundIndex, FLINTN,
eval,
false
5973 degree (
LCF), factorsFound, factorsFoundIndex,
5976 if (nmod_mat_ncols (FLINTN) ==
result.length())
5980 factorsFoundIndex, NTLN,
eval,
false
5984 degree (
LCF), factorsFound, factorsFoundIndex,
5987 if (NTLN.NumCols() ==
result.length())
5991 delete [] factorsFoundIndex;
5994 delete [] factorsFoundIndex;
6017 factors= bufFactors;
6033 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6037 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6044 factors= bufFactors;
6065 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6069 for (
long j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
6071 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
6076 factors= bufFactors;
6096 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6100 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6107 factors= bufFactors;
6119 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6127 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6140 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6143 nmod_mat_init_set (FLINTN,
N);
6144 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6145 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6148 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6149 for (
long i= 0;
i < NTLN.NumCols();
i++)
6151 factorsFoundIndex [
i]= 0;
6153 if (
degree (F) + 1 > smallFactorDeg)
6155 if (
l < smallFactorDeg)
6166 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6169 if (
result.length() == nmod_mat_ncols (FLINTN))
6171 nmod_mat_clear (FLINTN);
6175 factorsFoundIndex, NTLN,
evaluation, beenInThres
6178 if (
result.length() == NTLN.NumCols())
6182 delete [] factorsFoundIndex;
6187 int i= sizeOfLiftPre - 1;
6189 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6193 if (
l < liftPre[
i-1] + 1)
6199 l= liftPre[
i-1] + 1;
6210 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6213 if (
result.length() == nmod_mat_ncols (FLINTN))
6215 nmod_mat_clear (FLINTN);
6219 factorsFoundIndex, NTLN,
evaluation, beenInThres
6222 if (
result.length() == NTLN.NumCols())
6226 delete [] factorsFoundIndex;
6235 while (((
degree (F,
y)/4)*
i+1) + 4 <= smallFactorDeg)
6247 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6248 LC (F,1).inCoeffDomain() &&
6262 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6267 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6276 if (check1/
Lc (check1) == check2/
Lc (check2))
6279 nmod_mat_clear (FLINTN);
6281 result.append (oldcheck1);
6284 delete [] factorsFoundIndex;
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;
6322 nmod_mat_clear (FLINTN);
6325 delete [] factorsFoundIndex;
6332 int& factorsFound,
bool beenInThres,
CFMatrix&
M,
6343 int smallFactorDeg= 11;
6345 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6346 for (
long i= 0;
i < NTLN.NumCols();
i++)
6347 factorsFoundIndex [
i]= 0;
6349 if (
degree (F) + 1 > smallFactorDeg)
6351 if (
l < smallFactorDeg)
6361 factorsFoundIndex, NTLN,
evaluation, beenInThres
6364 if (
result.length() == NTLN.NumCols())
6367 delete [] factorsFoundIndex;
6372 int i= sizeOfLiftPre - 1;
6374 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6378 if (
l < liftPre[
i-1] + 1)
6384 l= liftPre[
i-1] + 1;
6394 factorsFoundIndex, NTLN,
evaluation, beenInThres
6397 if (
result.length() == NTLN.NumCols())
6400 delete [] factorsFoundIndex;
6409 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6421 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6422 LC (F,1).inCoeffDomain() &&
6436 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6441 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6450 if (check1/
Lc (check1) == check2/
Lc (check2))
6452 result.append (oldcheck1);
6455 delete [] factorsFoundIndex;
6468 factorsFoundIndex, NTLN,
evaluation, beenInThres
6471 if (
result.length() == NTLN.NumCols())
6474 delete [] factorsFoundIndex;
6482 delete [] factorsFoundIndex;
6491 int& factorsFound,
bool beenInThres,
CFMatrix&
6500 int& factorsFound,
bool beenInThres,
CFMatrix&
6513 int smallFactorDeg= 11;
6516 nmod_mat_init_set (FLINTN,
N);
6517 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6518 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6521 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6522 for (
long i= 0;
i < NTLN.NumCols();
i++)
6524 factorsFoundIndex [
i]= 0;
6526 if (
degree (F) + 1 > smallFactorDeg)
6528 if (
l < smallFactorDeg)
6539 factorsFoundIndex, FLINTN, beenInThres,
info,
6544 factorsFoundIndex, NTLN, beenInThres,
info,
6550 if (
result.length() == nmod_mat_ncols (FLINTN))
6552 nmod_mat_clear (FLINTN);
6554 if (
result.length() == NTLN.NumCols())
6558 delete [] factorsFoundIndex;
6563 int i= sizeOfLiftPre - 1;
6565 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6569 if (
l < liftPre[
i-1] + 1)
6575 l= liftPre[
i-1] + 1;
6586 factorsFoundIndex, FLINTN, beenInThres,
info,
6591 factorsFoundIndex, NTLN, beenInThres,
info,
6597 if (
result.length() == nmod_mat_ncols (FLINTN))
6599 nmod_mat_clear (FLINTN);
6601 if (
result.length() == NTLN.NumCols())
6605 delete [] factorsFoundIndex;
6614 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6636 factorsFoundIndex, FLINTN, beenInThres,
info,
6641 factorsFoundIndex, NTLN, beenInThres,
info,
6647 if (
result.length() == nmod_mat_ncols (FLINTN))
6649 nmod_mat_clear (FLINTN);
6651 if (
result.length() == NTLN.NumCols())
6655 delete [] factorsFoundIndex;
6663 nmod_mat_clear (FLINTN);
6666 delete [] factorsFoundIndex;
6677 CFList bufUniFactors= uniFactors;
6679 int smallFactorDeg= d;
6681 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6682 int adaptedLiftBound;
6684 int * factorsFoundIndex=
new int [uniFactors.
length()];
6685 for (
int i= 0;
i < uniFactors.
length();
i++)
6686 factorsFoundIndex [
i]= 0;
6689 factorsFoundIndex, degs, success, smallFactorDeg,
eval);
6690 delete [] factorsFoundIndex;
6694 return earlyFactors;
6699 return earlyFactors;
6701 int sizeOldF=
size (
G);
6702 if (
size (F) < sizeOldF)
6706 return earlyFactors;
6710 uniFactors= bufUniFactors;
6723 CFList bufUniFactors= uniFactors;
6725 int smallFactorDeg= d;
6727 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6728 int adaptedLiftBound;
6730 int * factorsFoundIndex=
new int [uniFactors.
length()];
6731 for (
int i= 0;
i < uniFactors.
length();
i++)
6732 factorsFoundIndex [
i]= 0;
6737 delete [] factorsFoundIndex;
6741 return earlyFactors;
6746 return earlyFactors;
6749 int sizeOldF=
size (
G);
6750 if (
size (F) < sizeOldF)
6754 return earlyFactors;
6758 uniFactors= bufUniFactors;
6782 int minBound= bounds[0];
6783 for (
int i= 1;
i < d;
i++)
6786 minBound=
tmin (minBound, bounds[
i]);
6789 CFList bufUniFactors= uniFactors;
6797 bool success=
false;
6799 success, minBound + 1,
eval
6802 if (smallFactors.
length() > 0)
6804 if (smallFactors.
length() == 1)
6815 return smallFactors;
6842 return smallFactors;
6854 return smallFactors;
6858 minBound= bounds[0];
6859 for (
int i= 1;
i < d;
i++)
6862 minBound=
tmin (minBound, bounds[
i]);
6875 return smallFactors;
6897 zz_pE::init (NTLMipo);
6904 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
6905 nmod_mat_entry (FLINTN,
i,
i)= 1;
6907 ident (NTLN, bufUniFactors.
length() - 1);
6916 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
6917 nmod_mat_entry (FLINTN,
i,
i)= 1;
6920 ident (NTLN, bufUniFactors.
length() - 1);
6923 ident (NTLNe, bufUniFactors.
length() - 1);
6936 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
6938 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
6947 minBound, bufUniFactors, FLINTN,
6949 minBound, bufUniFactors, NTLN,
6956 bufUniFactors, NTLNe, diophant,
M, Pi, bufQ,
6967 minBound, bufUniFactors, FLINTN, diophant,
M,
6969 minBound, bufUniFactors, NTLN, diophant,
M,
6978 liftBound, minBound, bufUniFactors,
6980 FLINTN, diophant,
M, Pi, bufQ,
6982 NTLN, diophant,
M, Pi, bufQ,
6988 minBound, bufUniFactors, NTLNe, diophant,
6995 "time to compute a reduced lattice: ");
6997 if (oldL > liftBound)
7001 nmod_mat_clear (FLINTN);
7004 return Union (smallFactors,
7017 nmod_mat_clear (FLINTN);
7028 int * factorsFoundIndex;
7032 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7033 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7035 factorsFoundIndex=
new int [NTLN.NumCols()];
7036 for (
long i= 0;
i < NTLN.NumCols();
i++)
7038 factorsFoundIndex[
i]= 0;
7042 factorsFoundIndex=
new int [NTLNe.NumCols()];
7043 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7044 factorsFoundIndex[
i]= 0;
7046 int factorsFound= 0;
7051 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7053 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7058 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7063 if (
result.length() == nmod_mat_ncols (FLINTN))
7066 nmod_mat_clear (FLINTN);
7068 if (
result.length() == NTLN.NumCols())
7071 delete [] factorsFoundIndex;
7078 if (
result.length() == NTLNe.NumCols())
7080 delete [] factorsFoundIndex;
7085 delete [] factorsFoundIndex;
7089 int * factorsFoundIndex;
7093 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7094 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7096 factorsFoundIndex=
new int [NTLN.NumCols()];
7097 for (
long i= 0;
i < NTLN.NumCols();
i++)
7099 factorsFoundIndex[
i]= 0;
7103 factorsFoundIndex=
new int [NTLNe.NumCols()];
7104 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7105 factorsFoundIndex[
i]= 0;
7108 int factorsFound= 0;
7112 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7114 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7119 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7124 if (
result.length() == nmod_mat_ncols(FLINTN))
7126 nmod_mat_clear (FLINTN);
7128 if (
result.length() == NTLN.NumCols())
7131 delete [] factorsFoundIndex;
7138 if (
result.length() == NTLNe.NumCols())
7140 delete [] factorsFoundIndex;
7145 delete [] factorsFoundIndex;
7149 bool beenInThres=
false;
7156 if (nmod_mat_ncols (FLINTN) < bufUniFactors.
length())
7160 if (NTLN.NumCols() < bufUniFactors.
length())
7162 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7171 if (NTLNe.NumCols() < bufUniFactors.
length())
7173 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
7182 int factorsFound= 0;
7186 result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
7188 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7190 factorsFound, beenInThres, M, Pi,
7191 diophant, symmetric, eval
7195 if (result.length() == nmod_mat_ncols (FLINTN))
7197 nmod_mat_clear (FLINTN);
7199 if (result.length() == NTLN.NumCols())
7203 return Union (result, smallFactors);
7208 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
7209 factorsFound, beenInThres, M, Pi,
7210 diophant, symmetric, eval
7213 if (result.length() == NTLNe.NumCols())
7216 return Union (result, smallFactors);
7225 for (CFListIterator i= result; i.hasItem(); i++)
7228 tmp1= mod (i.getItem(), y-eval);
7230 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7232 tmp2= mod (j.getItem(), y);
7246 long numCols, numRows;
7247 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7250 numCols= nmod_mat_ncols (FLINTN);
7251 numRows= nmod_mat_nrows (FLINTN);
7252 zeroOne= extractZeroOneVecs (FLINTN);
7254 numCols= NTLN.NumCols();
7255 numRows= NTLN.NumRows();
7256 zeroOne= extractZeroOneVecs (NTLN);
7261 numCols= NTLNe.NumCols();
7262 numRows= NTLNe.NumRows();
7263 zeroOne= extractZeroOneVecs (NTLNe);
7265 CFList bufBufUniFactors= bufUniFactors;
7268 CFList factorsConsidered;
7270 for (
int i= 0;
i < numCols;
i++)
7272 if (zeroOne [
i] == 0)
7274 iter= bufUniFactors;
7276 factorsConsidered=
CFList();
7277 for (
int j= 0;
j < numRows;
j++,
iter++)
7282 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
7301 for (iter2=
result; iter2.hasItem(); iter2++)
7303 tmp=
mod (iter2.getItem(),
y-
eval);
7307 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
7312 bufUniFactors= bufBufUniFactors;
7323 oldNumCols= nmod_mat_ncols (FLINTN);
7325 oldNumCols= NTLN.NumCols();
7328 oldNumCols, oldL,
l,
eval
7336 oldNumCols= nmod_mat_ncols (FLINTN);
7338 oldNumCols= NTLN.NumCols();
7347 oldNumCols= NTLNe.NumCols();
7359 nmod_mat_clear (FLINTN);
7379 nmod_mat_clear (FLINTN);
7386 nmod_mat_clear (FLINTN);
7389 alpha, degs, symmetric,
7429 if (
result.length()== nmod_mat_ncols (FLINTN))
7431 nmod_mat_clear (FLINTN);
7433 if (
result.length()== NTLN.NumCols())
7443 if (
result.length()== NTLNe.NumCols())
7456 liftBound,d,bounds,FLINTN,
7458 liftBound, d, bounds, NTLN,
7460 diophant,
M, Pi, bufQ,
eval
7466 liftBound, d, bounds,
7468 FLINTN, diophant,
M,
7476 liftBound, d, bounds,
7485 if (
result.length() == nmod_mat_ncols (FLINTN))
7487 nmod_mat_clear (FLINTN);
7489 if (
result.length() == NTLN.NumCols())
7499 if (
result.length() == NTLNe.NumCols())
7509 DEBOUTLN (cerr,
"lattice recombination failed");
7519 nmod_mat_clear (FLINTN);
7528 minBound= bounds[0];
7529 for (
int i= 1;
i < d;
i++)
7532 minBound=
tmin (minBound, bounds[
i]);
7535 if (minBound > 16 ||
result.length() == 0)
7552 degs,symmetric,
eval
7597 imPrimElemAlpha=
map (primElemAlpha,
alpha, bufEvaluation, gamma);
7624 CFList bufUniFactors= uniFactors;
7644 int minBound= bounds[0];
7645 for (
int i= 1;
i < d;
i++)
7648 minBound=
tmin (minBound, bounds[
i]);
7660 bool success=
false;
7665 if (smallFactors.
length() > 0)
7667 if (smallFactors.
length() == 1)
7681 return smallFactors;
7708 return smallFactors;
7722 smallFactors.
append (tmp);
7723 return smallFactors;
7727 minBound= bounds[0];
7728 for (
int i= 1;
i < d;
i++)
7731 minBound=
tmin (minBound, bounds[
i]);
7747 smallFactors.
append (tmp);
7748 return smallFactors;
7757 nmod_mat_init (FLINTN, bufUniFactors.
length()-1, bufUniFactors.
length()-1,
7759 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7760 nmod_mat_entry (FLINTN,
i,
i)= 1;
7770 ident (NTLN, bufUniFactors.
length() - 1);
7782 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7787 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7796 minBound+1, bufUniFactors, FLINTN, diophant,
7802 minBound + 1, bufUniFactors, NTLN, diophant,
7809 "time to compute a reduced lattice: ");
7812 if (oldL > liftBound)
7815 nmod_mat_clear (FLINTN);
7830 nmod_mat_clear (FLINTN);
7844 int * factorsFoundIndex;
7847 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7848 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7850 factorsFoundIndex=
new int [NTLN.NumCols()];
7851 for (
long i= 0;
i < NTLN.NumCols();
i++)
7853 factorsFoundIndex[
i]= 0;
7855 int factorsFound= 0;
7860 factorsFound, factorsFoundIndex, FLINTN,
false,
info,
7864 if (
result.length() == nmod_mat_ncols (FLINTN))
7866 nmod_mat_clear (FLINTN);
7869 factorsFound, factorsFoundIndex, NTLN,
false,
info,
7873 if (
result.length() == NTLN.NumCols())
7876 delete [] factorsFoundIndex;
7881 delete [] factorsFoundIndex;
7885 int * factorsFoundIndex;
7887 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7888 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7890 factorsFoundIndex=
new int [NTLN.NumCols()];
7891 for (
long i= 0;
i < NTLN.NumCols();
i++)
7893 factorsFoundIndex[
i]= 0;
7895 int factorsFound= 0;
7899 factorsFound, factorsFoundIndex, FLINTN,
false,
7903 if (
result.length() == nmod_mat_ncols (FLINTN))
7905 nmod_mat_clear (FLINTN);
7908 factorsFound, factorsFoundIndex, NTLN,
false,
7912 if (
result.length() == NTLN.NumCols())
7915 delete [] factorsFoundIndex;
7919 delete [] factorsFoundIndex;
7923 bool beenInThres=
false;
7926 if (
l <= thres && bufUniFactors.
length() > nmod_mat_ncols (FLINTN))
7932 if (
l <= thres && bufUniFactors.
length() > NTLN.NumCols())
7943 int factorsFound= 0;
7947 factorsFound, beenInThres,
M, Pi,
7951 if (
result.length() == nmod_mat_ncols (FLINTN))
7953 nmod_mat_clear (FLINTN);
7956 factorsFound, beenInThres,
M, Pi,
7960 if (
result.length() == NTLN.NumCols())
7997 CFList bufBufUniFactors= bufUniFactors;
8000 CFList factorsConsidered;
8002 for (
int i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
8004 for (
int i= 0;
i < NTLN.NumCols();
i++)
8007 if (zeroOne [
i] == 0)
8009 iter= bufUniFactors;
8011 factorsConsidered=
CFList();
8013 for (
int j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
8015 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
8017 for (
int j= 0;
j < NTLN.NumRows();
j++,
iter++)
8033 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
8038 bufUniFactors= bufBufUniFactors;
8047 oldNumCols= nmod_mat_ncols (FLINTN);
8052 nmod_mat_clear (FLINTN);
8054 oldNumCols= NTLN.NumCols();
8090 if (
l/degMipo < liftBound)
8097 if (
result.length()== nmod_mat_ncols (FLINTN))
8099 nmod_mat_clear (FLINTN);
8105 if (
result.length()== NTLN.NumCols())
8117 liftBound, d,bounds,FLINTN,
8118 diophant,
M, Pi, bufQ,
8122 if (
result.length()== nmod_mat_ncols (FLINTN))
8124 nmod_mat_clear (FLINTN);
8127 liftBound, d, bounds, NTLN,
8128 diophant,
M, Pi, bufQ,
8132 if (
result.length()== NTLN.NumCols())
8143 nmod_mat_clear (FLINTN);
8146 DEBOUTLN (cerr,
"lattice recombination failed");
8160 smallFactors.
append (tmp);
8164 minBound= bounds[0];
8165 for (
int i= 1;
i < d;
i++)
8168 minBound=
tmin (minBound, bounds[
i]);
8171 if (minBound > 16 ||
result.length() == 0)
8215 if (
A.isUnivariate())
8217 if (extension ==
false)
8238 A=
A/(contentAx*contentAy);
8239 CFList contentAxFactors, contentAyFactors;
8249 if (
A.inCoeffDomain())
8251 append (factors, contentAxFactors);
8252 append (factors, contentAyFactors);
8256 else if (
A.isUnivariate())
8259 append (factors, contentAxFactors);
8260 append (factors, contentAyFactors);
8281 bool derivXZero=
false;
8288 gcdDerivX=
gcd (
A, derivX);
8289 if (
degree (gcdDerivX) > 0)
8294 append (factorsG, contentAxFactors);
8295 append (factorsG, contentAyFactors);
8302 bool derivYZero=
false;
8309 gcdDerivY=
gcd (
A, derivY);
8310 if (
degree (gcdDerivY) > 0)
8315 append (factorsG, contentAxFactors);
8316 append (factorsG, contentAyFactors);
8331 derivXZero= derivYZero;
8353 int minBound= bounds[0];
8354 for (
int i= 1;
i < boundsLength;
i++)
8357 minBound=
tmin (minBound, bounds[
i]);
8362 int minBound2= bounds2[0];
8363 for (
int i= 1;
i < boundsLength2;
i++)
8365 if (bounds2[
i] != 0)
8366 minBound2=
tmin (minBound2, bounds2[
i]);
8372 CFList uniFactors, list, bufUniFactors;
8377 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8378 CFList bufUniFactors2, list2, uniFactors2;
8389 bool symmetric=
false;
8392 for (
int i= 0;
i < factorNums;
i++)
8398 if (!derivXZero && !fail2 && !symmetric)
8409 "time to find eval point wrt y: ");
8412 if (fail && (
i == 0))
8414 if (!derivXZero && !fail2 && !symmetric)
8416 bufEvaluation= bufEvaluation2;
8417 int dummy= subCheck2;
8418 subCheck2= subCheck1;
8423 bufAeval= bufAeval2;
8432 if (fail && (
i == 0))
8445 if (fail && (
i != 0))
8452 "time for univariate factorization over Fq: ");
8453 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8454 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8456 if (!derivXZero && !fail2 && !symmetric)
8461 "time for univariate factorization in y over Fq: ");
8462 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8463 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8466 if (bufUniFactors.
length() == 1 ||
8467 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8487 if (
i == 0 && !extension)
8493 if (subCheck > 1 && (subCheck1%subCheck == 0))
8496 subst (bufA, bufA, subCheck,
x);
8509 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8513 if (subCheck > 1 && (subCheck2%subCheck == 0))
8516 subst (bufA, bufA, subCheck,
y);
8532 if (!derivXZero && !fail2 && !symmetric)
8539 uniFactors= bufUniFactors;
8541 if (!derivXZero && !fail2 && !symmetric)
8544 evaluation2= bufEvaluation2;
8545 uniFactors2= bufUniFactors2;
8552 if (!derivXZero && !fail2 && !symmetric)
8557 uniFactors2= bufUniFactors2;
8559 evaluation2= bufEvaluation2;
8564 uniFactors= bufUniFactors;
8569 list.
append (bufEvaluation);
8570 if (!derivXZero && !fail2 && !symmetric)
8571 list2.
append (bufEvaluation2);
8574 "total time for univariate factorizations: ");
8576 if (!derivXZero && !fail2 && !symmetric)
8578 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8583 uniFactors= uniFactors2;
8615 minBound= minBound2;
8621 "time to shift eval to zero: ");
8627 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8629 if ((GF && !extension) || (GF && extension &&
k != 1))
8631 bool earlySuccess=
false;
8635 (
A, earlySuccess, earlyFactors, degs, liftBound,
8638 "time for bivariate hensel lifting over Fq: ");
8639 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8651 "time for naive bivariate factor recombi over Fq: ");
8654 factors=
Union (earlyFactors, factors);
8655 else if (!earlySuccess && degs.
getLength() == 1)
8656 factors= earlyFactors;
8666 factors=
Union (lll, factors);
8672 factors=
Union (lll, factors);
8674 else if (!extension && (
alpha !=
x || GF))
8678 factors=
Union (lll, factors);
8681 "time to bivar lift and LLL recombi over Fq: ");
8682 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8686 bool earlySuccess=
false;
8690 (
A, earlySuccess, earlyFactors, degs, liftBound,
8693 "time for bivar hensel lifting over Fq: ");
8694 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8702 "time for small subset naive recombi over Fq: ");
8704 int oldUniFactorsLength= uniFactors.
length();
8725 "time to increase precision: ");
8726 factors=
Union (factors, tmp);
8728 && uniFactors.
length() != oldUniFactorsLength)
8776 int oldUniFactorsLength= uniFactors.
length();
8785 info2, source, dest, liftBound
8787 factors=
Union (factors, tmp);
8789 && uniFactors.
length() != oldUniFactorsLength)
8806 factors=
Union (earlyFactors, factors);
8807 else if (!earlySuccess && degs.
getLength() == 1)
8808 factors= earlyFactors;
8839 bool extension=
true;
8865 else if (!GF && (
alpha !=
x))
8883 bool primFail=
false;
8886 ASSERT (!primFail,
"failure in integer factorizer");
8903 bool primFail=
false;
8905 ASSERT (!primFail,
"failure in integer factorizer");
8927 bool extension=
true;
8931 if (
ipower (
p, extensionDeg) < (1<<16))
8957 if (
ipower (
p, 2*extensionDeg) < (1<<16))
8973 bool primFail=
false;
8976 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
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.
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
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
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.
generate random integers, random elements of finite fields
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
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
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
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
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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
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)
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())
int liftAndComputeLattice(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)
void deleteFactors(CFList &factors, int *factorsFoundIndex)
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
CFList extReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const ExtensionInfo &info, const CanonicalForm &evaluation)
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
void extReconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
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)
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)
int extLiftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
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)
long isReduced(const nmod_mat_t M)
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 ...
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 * extractZeroOneVecs(const nmod_mat_t M)
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo)
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
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 rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
void prune(Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
static BOOLEAN IsOne(number a, const coeffs r)
static BOOLEAN IsZero(number a, const coeffs r)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
INST_VAR CanonicalForm gf_mipo
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
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)