36#include <NTL/lzz_pEX.h>
52#if defined (HAVE_NTL) || defined(HAVE_FLINT)
54#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
64 zz_pE::init (NTLMipo);
71 if (
i.getItem().inCoeffDomain())
94#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
98 nmod_poly_t FLINTmipo;
108 fq_nmod_poly_t *
vec=
new fq_nmod_poly_t [factors.
length()];
114 if (
i.getItem().inCoeffDomain())
133 for (
int i= 0;
i < factors.
length();
i++,
k++)
156 ASSERT (
M.isUnivariate(),
"expected univariate poly");
158 CFList bufFactors= factors;
171 for (;
i.hasItem();
i++)
176 i.getItem()=
reduce (
i.getItem()*inv,
M);
178#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
179 bufFactors= productsFLINT (bufFactors,
M);
181 bufFactors= productsNTL (bufFactors,
M);
198 zz_pE::init (NTLMipo);
199 zz_pEX NTLbuf1, NTLbuf2, NTLbuf3, NTLS, NTLT;
202 tryNTLXGCD (NTLbuf3, NTLS, NTLT, NTLbuf1, NTLbuf2, fail);
216 for (;
i.hasItem();
i++)
220 tryNTLXGCD (NTLbuf3, NTLS, NTLT, NTLbuf3, NTLbuf1, fail);
227 tryExtgcd (buf3,
buf1,
M, buf3, S,
T, fail);
235 j.getItem()=
mod (
j.getItem(),
k.getItem());
256 if (
mod (
i.getItem(),
p) == 0)
308 i.getItem() /=
Lc (
i.getItem());
347 while (
i >= 0 &&
mod( leadingCoeffs,
p ) == 0)
353 ASSERT (
i >= 0,
"ran out of primes");
357 modMipo /=
lc (modMipo);
377 p, newResult, newQ );
392 if (
j.getItem() !=
k.getItem())
417 i.getItem() *=
Lc (
j.getItem())*denf;
424 i.getItem() *= denFirst;
464 m.getItem()=
j.getItem();
467 j.getItem()=
m.getItem();
479#if defined(HAVE_NTL) || defined(HAVE_FLINT)
488 recResult=
mapinto (recResult);
496 bufFactors[
k]=
i.getItem() (0);
498 bufFactors [
k]=
i.getItem();
504 for (
int l= 0;
l < factors.
length();
l++)
510 tmp=
mulNTL (tmp, bufFactors[
l]);
523 e=
b (e -
mulNTL (
i.getItem(),
j.getItem(),
b));
531 recResult=
mapinto (recResult);
537 for (
int i= 1;
i < d;
i++)
539 coeffE=
div (e, modulus);
550 for (;
j.hasItem();
j++,
k++,
l++, ii++)
553 g=
modNTL (coeffE, bufFactors[ii]);
557 k.getItem() +=
g.mapinto()*modulus;
558 e -=
mulNTL (
g.mapinto(), b2 (
l.getItem()), b2)*modulus;
583 bool mipoHasDen=
false;
597 modMipo /=
lc (modMipo);
609 if (bb.
getk() >
b.getk() )
b=bb;
616 recResult=
mapinto (recResult);
625 bufFactors[
k]=
i.getItem() (0);
627 bufFactors [
k]=
i.getItem();
634 for (
int l= 0;
l < factors.
length();
l++)
639 tmp=
mulNTL (tmp, bufFactors[
l]);
662 modMipo /=
lc (modMipo);
669 bufFactors [
k]= bufFactors[
k].mapinto();
676 for (;
j.hasItem();
j++)
682 j.getItem()=
b(
j.getItem()*
b.inverse(
lc(
j.getItem())));
690 e=
b (e -
mulNTL (
i.getItem(),
j.getItem(),
b));
711 recResult=
mapinto (recResult);
722 for (
int i= 1;
i < d;
i++)
724 coeffE=
div (e, modulus);
747 for (;
j.hasItem();
j++,
k++,
l++, ii++)
750 g=
modNTL (coeffE, bufFactors[ii]);
759 b2 (
l.getItem()), b2)*modulus;
767 b2 (
l.getItem()), b2)*modulus;
786#if defined(HAVE_NTL) || defined(HAVE_FLINT)
799 fq_poly_t FLINTS, FLINTT, FLINTbuf3, FLINTbuf1, FLINTbuf2;
806 bool mipoHasDen=
false;
820 modMipo /=
lc (modMipo);
835 if (bb.
getk() >
b.getk() )
b=bb;
860 CFList bufFactors= factors;
864 for (;
i.hasItem();
i++)
884 ZZ_pE::init (NTLmipo);
885 ZZ_pEX NTLS, NTLT, NTLbuf3;
888 XGCD (NTLbuf3, NTLS, NTLT, NTLbuf1, NTLbuf2);
895 fmpz_mod_poly_t FLINTmipo;
897#if __FLINT_RELEASE >= 20700
898 fmpz_mod_ctx_t bigpk_ctx;
899 fmpz_mod_ctx_init(bigpk_ctx, bigpk);
900 fq_ctx_init_modulus(fqctx, FLINTmipo, bigpk_ctx,
"Z");
901 fmpz_mod_ctx_clear(bigpk_ctx);
902 fmpz_mod_poly_clear(FLINTmipo, bigpk_ctx);
904 fq_ctx_init_modulus(fqctx, FLINTmipo,
"Z");
905 fmpz_mod_poly_clear(FLINTmipo);
908 fq_init(fcheck, fqctx);
909 fq_poly_init(FLINTS, fqctx);
910 fq_poly_init(FLINTT, fqctx);
911 fq_poly_init(FLINTbuf3, fqctx);
917 fq_poly_xgcd_euclidean_f(fcheck, FLINTbuf3, FLINTS, FLINTT,
918 FLINTbuf1, FLINTbuf2, fqctx);
919 if (!fq_is_one(fcheck, fqctx))
922 fq_clear(fcheck, fqctx);
923 fq_poly_clear(FLINTS, fqctx);
924 fq_poly_clear(FLINTT, fqctx);
925 fq_poly_clear(FLINTbuf3, fqctx);
926 fq_poly_clear(FLINTbuf1, fqctx);
927 fq_poly_clear(FLINTbuf2, fqctx);
940 for (;
i.hasItem();
i++)
951 fq_poly_clear(FLINTbuf1, fqctx);
955 fq_poly_xgcd_euclidean_f(fcheck, FLINTbuf2, FLINTS, FLINTT,
956 FLINTbuf3, FLINTbuf1, fqctx);
957 fq_poly_swap(FLINTbuf3, FLINTbuf2, fqctx);
959 if (!fq_is_one(fcheck, fqctx))
962 fq_clear(fcheck, fqctx);
963 fq_poly_clear(FLINTS, fqctx);
964 fq_poly_clear(FLINTT, fqctx);
965 fq_poly_clear(FLINTbuf3, fqctx);
966 fq_poly_clear(FLINTbuf1, fqctx);
967 fq_poly_clear(FLINTbuf2, fqctx);
981 j.getItem()=
modNTL (
j.getItem(),
k.getItem(),
b);
994 fq_clear(fcheck, fqctx);
995 fq_poly_clear(FLINTS, fqctx);
996 fq_poly_clear(FLINTT, fqctx);
997 fq_poly_clear(FLINTbuf3, fqctx);
998 fq_poly_clear(FLINTbuf1, fqctx);
999 fq_poly_clear(FLINTbuf2, fqctx);
1000 fq_ctx_clear(fqctx);
1007#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1044 for (;
i.hasItem();
i++)
1051 j.getItem()=
mulNTL (
j.getItem(), S);
1052 j.getItem()=
modNTL (
j.getItem(),
k.getItem());
1060#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1083 E= F[
j] - Pi [factors.
length() - 2] [
j];
1115 bufFactors[
k] += xToJ*
buf[
k];
1117 bufFactors[
k]=
b(bufFactors[
k]);
1121 int degBuf0=
degree (bufFactors[0],
x);
1122 int degBuf1=
degree (bufFactors[1],
x);
1123 if (degBuf0 > 0 && degBuf1 > 0)
1124 M (
j + 1, 1)=
mulNTL (bufFactors[0] [
j], bufFactors[1] [
j],
b);
1127 if (degBuf0 > 0 && degBuf1 > 0)
1128 uIZeroJ=
mulNTL ((bufFactors[0] [0] + bufFactors[0] [
j]),
1129 (bufFactors[1] [0] +
buf[1]),
b) -
M(1, 1) -
M(
j + 1, 1);
1130 else if (degBuf0 > 0)
1131 uIZeroJ=
mulNTL (bufFactors[0] [
j], bufFactors[1],
b);
1132 else if (degBuf1 > 0)
1137 uIZeroJ=
b (uIZeroJ);
1138 Pi [0] += xToJ*uIZeroJ;
1143 for (
k= 0;
k < factors.
length() - 1;
k++)
1146 one= bufFactors [0];
1147 two= bufFactors [1];
1148 if (degBuf0 > 0 && degBuf1 > 0)
1150 for (
k= 1;
k <= (
j+1)/2;
k++)
1157 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()), (bufFactors[1][
k]+
1158 two.
coeff()),
b) -
M (
k + 1, 1) -
M (
j -
k + 2, 1);
1164 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()), bufFactors[1][
k],
b)
1170 tmp[0] +=
mulNTL (bufFactors[0][
k], (bufFactors[1][
k]+two.
coeff()),
b)
1177 tmp[0] +=
M (
k + 1, 1);
1183 Pi [0] += tmp[0]*xToJ*F.
mvar();
1187 for (
int l= 1;
l < factors.
length() - 1;
l++)
1190 degBuf=
degree (bufFactors[
l + 1],
x);
1191 if (degPi > 0 && degBuf > 0)
1192 M (
j + 1,
l + 1)=
mulNTL (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j],
b);
1195 if (degPi > 0 && degBuf > 0)
1196 Pi [
l] += xToJ*(
mulNTL (Pi [
l - 1] [0] + Pi [
l - 1] [
j],
1197 bufFactors[
l + 1] [0] +
buf[
l + 1],
b) -
M (
j + 1,
l +1) -
1200 Pi [
l] += xToJ*(
mulNTL (Pi [
l - 1] [
j], bufFactors[
l + 1],
b));
1201 else if (degBuf > 0)
1206 if (degPi > 0 && degBuf > 0)
1208 uIZeroJ=
mulNTL (uIZeroJ, bufFactors [
l + 1] [0],
b);
1212 uIZeroJ=
mulNTL (uIZeroJ, bufFactors [
l + 1],
b);
1213 else if (degBuf > 0)
1215 uIZeroJ=
mulNTL (uIZeroJ, bufFactors [
l + 1] [0],
b);
1218 Pi[
l] += xToJ*uIZeroJ;
1220 one= bufFactors [
l + 1];
1224 if (degBuf > 0 && degPi > 0)
1235 if (degBuf > 0 && degPi > 0)
1237 for (
k= 1;
k <= (
j+1)/2;
k++)
1263 tmp[
l] +=
M (
k + 1,
l + 1);
1268 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
1272#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1290 bool hasAlgVar2=
false;
1301 DEBOUTLN (cerr,
"diophant= " << diophant);
1308 for (;
j.hasItem();
j++,
i++)
1311 M (1,
i + 1)= Pi [
i];
1318 bufFactors[
i]=
mod (
k.getItem(), F.
mvar());
1320 bufFactors[
i]=
k.getItem();
1322 for (
i= 1;
i <
l;
i++)
1327 k.getItem()= bufFactors[
i];
1332#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1353 bufFactors[
i]=
mod (
k.getItem(), xToStart);
1355 bufFactors[
i]=
k.getItem();
1357 for (
i= start;
i < end;
i++)
1362 k.getItem()= bufFactors [
i];
1367#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1382 i.getItem()=
mod (
i.getItem(),
y);
1393 bufFactors [
k]=
i.getItem();
1403 for (
int l= 0;
l < factors.
length();
l++)
1418 e -=
i.getItem()*
j.getItem();
1426 for (
int i= 1;
i < d;
i++)
1438 for (;
j.hasItem();
j++,
k++,
l++, ii++)
1440 g= coeffE*
j.getItem();
1441 if (
degree (bufFactors[ii],
y) <= 0)
1442 g=
mod (
g, bufFactors[ii]);
1444 g=
mod (
g, bufFactors[ii][0]);
1447 DEBOUTLN (cerr,
"mod (e, power (y, i + 1))= " <<
1483 bufFactors [
k]=
i.getItem();
1495 for (
int l= 0;
l < factors.
length();
l++)
1509 e -=
mulMod (
i.getItem(),
j.getItem(),
M);
1517 for (
int i= 1;
i < d;
i++)
1530 for (;
j.hasItem();
j++,
k++,
l++, ii++)
1533 if (
degree (bufFactors[ii],
y) <= 0)
1537 divrem (
g, bufFactors[ii][0], dummy,
g,
M);
1552 DEBOUTLN (cerr,
"test in multiRecDiophantine= " <<
test);
1572 for (
int i= 0;
i < factors.
length();
i++)
1581 test2=
mod (test2, MOD);
1582 DEBOUTLN (cerr,
"test in henselStep= " << test2);
1589 for (
int i= 0;
i < factors.
length();
i++)
1594 test *= bufFactors[
i];
1599 DEBOUTLN (cerr,
"test in henselStep= " << test2);
1603 E= F[
j] - Pi [factors.
length() - 2] [
j];
1618 divrem (
E, bufFactors[
k] [0], dummy, rest1, MOD);
1623 divrem (
E, bufFactors[
k], dummy, rest1, MOD);
1633 bufFactors[
k] += xToJ*
buf[
k];
1636 int degBuf0=
degree (bufFactors[0],
x);
1637 int degBuf1=
degree (bufFactors[1],
x);
1638 if (degBuf0 > 0 && degBuf1 > 0)
1639 M (
j + 1, 1)=
mulMod (bufFactors[0] [
j], bufFactors[1] [
j], MOD);
1642 if (degBuf0 > 0 && degBuf1 > 0)
1643 uIZeroJ=
mulMod ((bufFactors[0] [0] + bufFactors[0] [
j]),
1644 (bufFactors[1] [0] +
buf[1]), MOD) -
M(1, 1) -
M(
j + 1, 1);
1645 else if (degBuf0 > 0)
1646 uIZeroJ=
mulMod (bufFactors[0] [
j], bufFactors[1], MOD);
1647 else if (degBuf1 > 0)
1648 uIZeroJ=
mulMod (bufFactors[0],
buf[1], MOD);
1651 Pi [0] += xToJ*uIZeroJ;
1654 for (
k= 0;
k < factors.
length() - 1;
k++)
1657 one= bufFactors [0];
1658 two= bufFactors [1];
1659 if (degBuf0 > 0 && degBuf1 > 0)
1661 for (
k= 1;
k <= (
j+1)/2;
k++)
1669 (bufFactors[1] [
k] + two.
coeff()), MOD) -
M (
k + 1, 1) -
1677 bufFactors[1] [
k], MOD) -
M (
k + 1, 1);
1682 tmp[0] +=
mulMod (bufFactors[0] [
k], (bufFactors[1] [
k] +
1683 two.
coeff()), MOD) -
M (
k + 1, 1);
1689 tmp[0] +=
M (
k + 1, 1);
1693 Pi [0] += tmp[0]*xToJ*F.
mvar();
1697 for (
int l= 1;
l < factors.
length() - 1;
l++)
1700 degBuf=
degree (bufFactors[
l + 1],
x);
1701 if (degPi > 0 && degBuf > 0)
1702 M (
j + 1,
l + 1)=
mulMod (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j], MOD);
1705 if (degPi > 0 && degBuf > 0)
1706 Pi [
l] += xToJ*(
mulMod ((Pi [
l - 1] [0] + Pi [
l - 1] [
j]),
1707 (bufFactors[
l + 1] [0] +
buf[
l + 1]), MOD) -
M (
j + 1,
l +1)-
1710 Pi [
l] += xToJ*(
mulMod (Pi [
l - 1] [
j], bufFactors[
l + 1], MOD));
1711 else if (degBuf > 0)
1716 if (degPi > 0 && degBuf > 0)
1718 uIZeroJ=
mulMod (uIZeroJ, bufFactors [
l + 1] [0], MOD);
1719 uIZeroJ +=
mulMod (Pi [
l - 1] [0],
buf [
l + 1], MOD);
1722 uIZeroJ=
mulMod (uIZeroJ, bufFactors [
l + 1], MOD);
1723 else if (degBuf > 0)
1725 uIZeroJ=
mulMod (uIZeroJ, bufFactors [
l + 1] [0], MOD);
1728 Pi[
l] += xToJ*uIZeroJ;
1730 one= bufFactors [
l + 1];
1734 if (degBuf > 0 && degPi > 0)
1745 if (degBuf > 0 && degPi > 0)
1747 for (
k= 1;
k <= (
j+1)/2;
k++)
1755 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1) -
1756 M (
j -
k + 2,
l + 1);
1763 Pi[
l - 1] [
k], MOD) -
M (
k + 1,
l + 1);
1768 tmp[
l] +=
mulMod (bufFactors[
l + 1] [
k],
1769 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1);
1774 tmp[
l] +=
M (
k + 1,
l + 1);
1777 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
1783#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1790 int liftBoundBivar=
l[
k];
1799 buf.insert (
LC (
j.getItem(), 1));
1801 bufFactors[
k]=
i.getItem();
1811 for (;
i.hasItem();
i++,
k++)
1813 Pi [
k]=
mulMod (Pi [
k - 1],
i.getItem(), MOD);
1814 M (1,
k + 1)= Pi [
k];
1817 for (
int d= 1; d <
l[1]; d++)
1821 result.append (bufFactors[
k]);
1837 bufFactors[
i]=
mod (
k.getItem(), xToStart);
1839 bufFactors[
i]=
k.getItem();
1841 for (
i= start;
i < end;
i++)
1842 henselStep (F, factors, bufFactors, diophant,
M, Pi,
i, MOD);
1846 k.getItem()= bufFactors [
i];
1863 bufFactors[
k]=
i.getItem();
1873 Pi [0]=
mod (Pi[0], xToLOld);
1878 for (;
i.hasItem();
i++,
k++)
1880 Pi [
k]=
mod (Pi [
k], xToLOld);
1881 M (1,
k + 1)= Pi [
k];
1884 for (
int d= 1; d < lNew; d++)
1888 result.append (bufFactors[
k]);
1892#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1905 if (
eval.length() == 2)
1908 for (
int i= 0;
i < 2;
i++)
1916 for (
int i= 2;
i < lLength &&
j.hasItem();
i++,
j++)
1942 E= F[
j] - Pi [factors.
length() - 2] [
j];
1965 bufFactors[
k] += xToJ*
buf[
k];
1968 int degBuf0=
degree (bufFactors[0],
x);
1969 int degBuf1=
degree (bufFactors[1],
x);
1970 if (degBuf0 > 0 && degBuf1 > 0)
1972 M (
j + 1, 1)=
mulNTL (bufFactors[0] [
j], bufFactors[1] [
j]);
1973 if (
j + 2 <=
M.rows())
1974 M (
j + 2, 1)=
mulNTL (bufFactors[0] [
j + 1], bufFactors[1] [
j + 1]);
1980 if (degBuf0 > 0 && degBuf1 > 0)
1981 uIZeroJ=
mulNTL(bufFactors[0][0],
buf[1]) +
1983 else if (degBuf0 > 0)
1984 uIZeroJ=
mulNTL (
buf[0], bufFactors[1]) +
1986 else if (degBuf1 > 0)
1987 uIZeroJ=
mulNTL (bufFactors[0],
buf[1]) +
1990 uIZeroJ=
mulNTL (bufFactors[0],
buf[1]) +
1993 Pi [0] += xToJ*uIZeroJ;
1996 for (
k= 0;
k < factors.
length() - 1;
k++)
1999 one= bufFactors [0];
2000 two= bufFactors [1];
2001 if (degBuf0 > 0 && degBuf1 > 0)
2005 for (
k= 1;
k <= (
j+1)/2;
k++)
2012 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()),(bufFactors[1][
k] +
2013 two.
coeff())) -
M (
k + 1, 1) -
M (
j -
k + 2, 1);
2019 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()), bufFactors[1] [
k]) -
2025 tmp[0] +=
mulNTL (bufFactors[0][
k],(bufFactors[1][
k] + two.
coeff())) -
2031 tmp[0] +=
M (
k + 1, 1);
2035 if (degBuf0 >=
j + 1 && degBuf1 >=
j + 1)
2037 if (
j + 2 <=
M.rows())
2038 tmp [0] +=
mulNTL ((bufFactors [0] [
j + 1]+ bufFactors [0] [0]),
2039 (bufFactors [1] [
j + 1] + bufFactors [1] [0]))
2040 -
M(1,1) -
M (
j + 2,1);
2042 else if (degBuf0 >=
j + 1)
2045 tmp[0] +=
mulNTL (bufFactors [0] [
j+1], bufFactors [1] [0]);
2047 tmp[0] +=
mulNTL (bufFactors [0] [
j+1], bufFactors [1]);
2049 else if (degBuf1 >=
j + 1)
2052 tmp[0] +=
mulNTL (bufFactors [0] [0], bufFactors [1] [
j + 1]);
2054 tmp[0] +=
mulNTL (bufFactors [0], bufFactors [1] [
j + 1]);
2057 Pi [0] += tmp[0]*xToJ*F.
mvar();
2060 for (
int l= 1;
l < factors.
length() - 1;
l++)
2063 degBuf=
degree (bufFactors[
l + 1],
x);
2064 if (degPi > 0 && degBuf > 0)
2066 M (
j + 1,
l + 1)=
mulNTL (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j]);
2067 if (
j + 2 <=
M.rows())
2068 M (
j + 2,
l + 1)=
mulNTL (Pi [
l - 1][
j + 1], bufFactors[
l + 1] [
j + 1]);
2071 M (
j + 1,
l + 1)= 0;
2073 if (degPi > 0 && degBuf > 0)
2075 mulNTL (uIZeroJ, bufFactors[
l+1] [0]);
2077 uIZeroJ=
mulNTL (uIZeroJ, bufFactors[
l + 1]) +
2079 else if (degBuf > 0)
2080 uIZeroJ=
mulNTL (uIZeroJ, bufFactors[
l + 1][0]) +
2083 uIZeroJ=
mulNTL (uIZeroJ, bufFactors[
l + 1]) +
2086 Pi [
l] += xToJ*uIZeroJ;
2088 one= bufFactors [
l + 1];
2090 if (degBuf > 0 && degPi > 0)
2094 for (
k= 1;
k <= (
j+1)/2;
k++)
2102 (Pi[
l - 1] [
k] + two.
coeff())) -
M (
k + 1,
l + 1) -
2103 M (
j -
k + 2,
l + 1);
2110 Pi[
l - 1] [
k]) -
M (
k + 1,
l + 1);
2115 tmp[
l] +=
mulNTL (bufFactors[
l + 1] [
k],
2116 (Pi[
l - 1] [
k] + two.
coeff())) -
M (
k + 1,
l + 1);
2121 tmp[
l] +=
M (
k + 1,
l + 1);
2125 if (degPi >=
j + 1 && degBuf >=
j + 1)
2127 if (
j + 2 <=
M.rows())
2128 tmp [
l] +=
mulNTL ((Pi [
l - 1] [
j + 1]+ Pi [
l - 1] [0]),
2129 (bufFactors [
l + 1] [
j + 1] + bufFactors [
l + 1] [0])
2130 ) -
M(1,
l+1) -
M (
j + 2,
l+1);
2132 else if (degPi >=
j + 1)
2135 tmp[
l] +=
mulNTL (Pi [
l - 1] [
j+1], bufFactors [
l + 1] [0]);
2137 tmp[
l] +=
mulNTL (Pi [
l - 1] [
j+1], bufFactors [
l + 1]);
2139 else if (degBuf >=
j + 1)
2142 tmp[
l] +=
mulNTL (Pi [
l - 1] [0], bufFactors [
l + 1] [
j + 1]);
2144 tmp[
l] +=
mulNTL (Pi [
l - 1], bufFactors [
l + 1] [
j + 1]);
2147 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
2152#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2161 CFList bufFactors2= factors;
2164 DEBOUTLN (cerr,
"diophant= " << diophant);
2172 if (
degree (bufFactors[0],
x) > 0 &&
degree (bufFactors [1],
x) > 0)
2174 M (1, 1)=
mulNTL (bufFactors [0] [0], bufFactors[1] [0]);
2175 Pi [0]=
M (1, 1) + (
mulNTL (bufFactors [0] [1], bufFactors[1] [0]) +
2176 mulNTL (bufFactors [0] [0], bufFactors [1] [1]))*
x;
2178 else if (
degree (bufFactors[0],
x) > 0)
2180 M (1, 1)=
mulNTL (bufFactors [0] [0], bufFactors[1]);
2182 mulNTL (bufFactors [0] [1], bufFactors[1])*
x;
2184 else if (
degree (bufFactors[1],
x) > 0)
2186 M (1, 1)=
mulNTL (bufFactors [0], bufFactors[1] [0]);
2188 mulNTL (bufFactors [0], bufFactors[1] [1])*
x;
2192 M (1, 1)=
mulNTL (bufFactors [0], bufFactors[1]);
2196 for (
i= 1;
i < Pi.
size();
i++)
2200 M (1,
i+1)=
mulNTL (Pi[
i-1] [0], bufFactors[
i+1] [0]);
2201 Pi [
i]=
M (1,
i+1) + (
mulNTL (Pi[
i-1] [1], bufFactors[
i+1] [0]) +
2202 mulNTL (Pi[
i-1] [0], bufFactors [
i+1] [1]))*
x;
2206 M (1,
i+1)=
mulNTL (Pi[
i-1] [0], bufFactors [
i+1]);
2207 Pi [
i]=
M(1,
i+1) +
mulNTL (Pi[
i-1] [1], bufFactors[
i+1])*
x;
2209 else if (
degree (bufFactors[
i+1],
x) > 0)
2211 M (1,
i+1)=
mulNTL (Pi[
i-1], bufFactors [
i+1] [0]);
2212 Pi [
i]=
M (1,
i+1) +
mulNTL (Pi[
i-1], bufFactors[
i+1] [1])*
x;
2216 M (1,
i+1)=
mulNTL (Pi [
i-1], bufFactors [
i+1]);
2221 for (
i= 1;
i <
l;
i++)
2225 for (
i= 0;
i < bufFactors.
size();
i++)
2226 factors.
append (bufFactors[
i]);
2245 ASSERT (
E.isUnivariate() ||
E.inCoeffDomain(),
2246 "constant or univariate poly expected");
2247 ASSERT (
i.getItem().isUnivariate() ||
i.getItem().inCoeffDomain(),
2248 "constant or univariate poly expected");
2249 ASSERT (
j.getItem().isUnivariate() ||
j.getItem().inCoeffDomain(),
2250 "constant or univariate poly expected");
2258 CFList bufFactors= factors;
2260 i.getItem()=
mod (
i.getItem(),
y);
2261 CFList bufProducts= products;
2263 i.getItem()=
mod (
i.getItem(),
y);
2276 e -=
j.getItem()*
i.getItem();
2281 for (
int i= 1;
i < d;
i++)
2290 recDiophantine=
diophantine (recResult, bufFactors, bufProducts,
buf,
2295 for (
j= recDiophantine;
j.hasItem();
j++,
k++,
l++)
2297 k.getItem() +=
j.getItem()*
power (
y,
i);
2298 e -=
l.getItem()*(
j.getItem()*
power (
y,
i));
2312#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2317 const CFList& MOD,
bool& noOneToOne)
2326 for (
int i= 0;
i < factors.
length();
i++)
2331 test *= bufFactors[
i];
2336 DEBOUTLN (cerr,
"test in nonMonicHenselStep= " << test2);
2340 E= F[
j] - Pi [factors.
length() - 2] [
j];
2357 buf[
k]=
i.getItem();
2358 bufFactors[
k] += xToJ*
i.getItem();
2364 int degBuf0=
degree (bufFactors[0],
x);
2365 int degBuf1=
degree (bufFactors[1],
x);
2366 if (degBuf0 > 0 && degBuf1 > 0)
2368 M (
j + 1, 1)=
mulMod (bufFactors[0] [
j], bufFactors[1] [
j], MOD);
2369 if (
j + 2 <=
M.rows())
2370 M (
j + 2, 1)=
mulMod (bufFactors[0] [
j + 1], bufFactors[1] [
j + 1], MOD);
2376 if (degBuf0 > 0 && degBuf1 > 0)
2377 uIZeroJ=
mulMod (bufFactors[0] [0],
buf[1], MOD) +
2378 mulMod (bufFactors[1] [0],
buf[0], MOD);
2379 else if (degBuf0 > 0)
2380 uIZeroJ=
mulMod (
buf[0], bufFactors[1], MOD) +
2382 else if (degBuf1 > 0)
2383 uIZeroJ=
mulMod (bufFactors[0],
buf[1], MOD) +
2386 uIZeroJ=
mulMod (bufFactors[0],
buf[1], MOD) +
2388 Pi [0] += xToJ*uIZeroJ;
2391 for (
k= 0;
k < factors.
length() - 1;
k++)
2394 one= bufFactors [0];
2395 two= bufFactors [1];
2396 if (degBuf0 > 0 && degBuf1 > 0)
2400 for (
k= 1;
k <= (
j+1)/2;
k++)
2408 (bufFactors[1] [
k] + two.
coeff()), MOD) -
M (
k + 1, 1) -
2416 bufFactors[1] [
k], MOD) -
M (
k + 1, 1);
2421 tmp[0] +=
mulMod (bufFactors[0] [
k], (bufFactors[1] [
k] +
2422 two.
coeff()), MOD) -
M (
k + 1, 1);
2428 tmp[0] +=
M (
k + 1, 1);
2433 if (degBuf0 >=
j + 1 && degBuf1 >=
j + 1)
2435 if (
j + 2 <=
M.rows())
2436 tmp [0] +=
mulMod ((bufFactors [0] [
j + 1]+ bufFactors [0] [0]),
2437 (bufFactors [1] [
j + 1] + bufFactors [1] [0]), MOD)
2438 -
M(1,1) -
M (
j + 2,1);
2440 else if (degBuf0 >=
j + 1)
2443 tmp[0] +=
mulMod (bufFactors [0] [
j+1], bufFactors [1] [0], MOD);
2445 tmp[0] +=
mulMod (bufFactors [0] [
j+1], bufFactors [1], MOD);
2447 else if (degBuf1 >=
j + 1)
2450 tmp[0] +=
mulMod (bufFactors [0] [0], bufFactors [1] [
j + 1], MOD);
2452 tmp[0] +=
mulMod (bufFactors [0], bufFactors [1] [
j + 1], MOD);
2454 Pi [0] += tmp[0]*xToJ*F.
mvar();
2458 for (
int l= 1;
l < factors.
length() - 1;
l++)
2461 degBuf=
degree (bufFactors[
l + 1],
x);
2462 if (degPi > 0 && degBuf > 0)
2464 M (
j + 1,
l + 1)=
mulMod (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j], MOD);
2465 if (
j + 2 <=
M.rows())
2466 M (
j + 2,
l + 1)=
mulMod (Pi [
l - 1] [
j + 1], bufFactors[
l + 1] [
j + 1],
2470 M (
j + 1,
l + 1)= 0;
2472 if (degPi > 0 && degBuf > 0)
2473 uIZeroJ=
mulMod (Pi[
l - 1] [0],
buf[
l + 1], MOD) +
2474 mulMod (uIZeroJ, bufFactors[
l + 1] [0], MOD);
2476 uIZeroJ=
mulMod (uIZeroJ, bufFactors[
l + 1], MOD) +
2478 else if (degBuf > 0)
2480 mulMod (uIZeroJ, bufFactors[
l + 1][0], MOD);
2483 mulMod (uIZeroJ, bufFactors[
l + 1], MOD);
2485 Pi [
l] += xToJ*uIZeroJ;
2487 one= bufFactors [
l + 1];
2489 if (degBuf > 0 && degPi > 0)
2493 for (
k= 1;
k <= (
j+1)/2;
k++)
2501 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1) -
2502 M (
j -
k + 2,
l + 1);
2509 Pi[
l - 1] [
k], MOD) -
M (
k + 1,
l + 1);
2514 tmp[
l] +=
mulMod (bufFactors[
l + 1] [
k],
2515 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1);
2520 tmp[
l] +=
M (
k + 1,
l + 1);
2524 if (degPi >=
j + 1 && degBuf >=
j + 1)
2526 if (
j + 2 <=
M.rows())
2527 tmp [
l] +=
mulMod ((Pi [
l - 1] [
j + 1]+ Pi [
l - 1] [0]),
2528 (bufFactors [
l + 1] [
j + 1] + bufFactors [
l + 1] [0])
2529 , MOD) -
M(1,
l+1) -
M (
j + 2,
l+1);
2531 else if (degPi >=
j + 1)
2534 tmp[
l] +=
mulMod (Pi [
l - 1] [
j+1], bufFactors [
l + 1] [0], MOD);
2536 tmp[
l] +=
mulMod (Pi [
l - 1] [
j+1], bufFactors [
l + 1], MOD);
2538 else if (degBuf >=
j + 1)
2541 tmp[
l] +=
mulMod (Pi [
l - 1] [0], bufFactors [
l + 1] [
j + 1], MOD);
2543 tmp[
l] +=
mulMod (Pi [
l - 1], bufFactors [
l + 1] [
j + 1], MOD);
2546 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
2567#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2575 int liftBoundBivar=
l[
k];
2598 Pi[0]=
mod (Pi[0],
power (
v, liftBoundBivar));
2600 if (
degree (bufFactors[0],
y) > 0 &&
degree (bufFactors [1],
y) > 0)
2601 Pi [0] += (
mulMod (bufFactors [0] [1], bufFactors[1] [0], MOD) +
2602 mulMod (bufFactors [0] [0], bufFactors [1] [1], MOD))*
y;
2603 else if (
degree (bufFactors[0],
y) > 0)
2604 Pi [0] +=
mulMod (bufFactors [0] [1], bufFactors[1], MOD)*
y;
2605 else if (
degree (bufFactors[1],
y) > 0)
2606 Pi [0] +=
mulMod (bufFactors [0], bufFactors[1] [1], MOD)*
y;
2609 for (
int i= 0;
i < bufFactors.
size();
i++)
2612 products.
append (
eval.getFirst()/bufFactors[
i] [0]);
2617 for (
int d= 1; d <
l[1]; d++)
2626 result.append (bufFactors[
k]);
2631#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2646 Pi [0]=
mod (Pi[0], xToLOld);
2649 if (
degree (bufFactors[0],
y) > 0 &&
degree (bufFactors [1],
y) > 0)
2650 Pi [0] += (
mulMod (bufFactors [0] [1], bufFactors[1] [0], MOD) +
2651 mulMod (bufFactors [0] [0], bufFactors [1] [1], MOD))*
y;
2652 else if (
degree (bufFactors[0],
y) > 0)
2653 Pi [0] +=
mulMod (bufFactors [0] [1], bufFactors[1], MOD)*
y;
2654 else if (
degree (bufFactors[1],
y) > 0)
2655 Pi [0] +=
mulMod (bufFactors [0], bufFactors[1] [1], MOD)*
y;
2659 for (
int i= 0;
i < bufFactors.
size();
i++)
2681 for (
int d= 1; d < lNew; d++)
2691 result.append (bufFactors[
k]);
2696#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2702 CFList bufDiophant= diophant;
2713 if (
eval.length() == 2)
2716 for (
int i= 0;
i < 2;
i++)
2731 for (
int i= 2;
i < lLength &&
j.hasItem();
i++,
j++, jj++, jjj++)
2738 l[
i - 1],
l[
i], bufLCs1, bufLCs2,
bad);
2750#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2754 int bivarLiftBound,
bool&
bad)
2756 CFList bufFactors2= factors;
2760 i.getItem()=
mod (
i.getItem(),
y);
2763 bufF=
mod (bufF,
y);
2783 if (
degree (bufFactors[0],
v) > 0 &&
degree (bufFactors [1],
v) > 0)
2785 M (1, 1)=
mulMod2 (bufFactors [0] [0], bufFactors[1] [0], yToL);
2786 Pi [0]=
M (1,1) + (
mulMod2 (bufFactors [0] [1], bufFactors[1] [0], yToL) +
2787 mulMod2 (bufFactors [0] [0], bufFactors [1] [1], yToL))*
v;
2789 else if (
degree (bufFactors[0],
v) > 0)
2791 M (1,1)=
mulMod2 (bufFactors [0] [0], bufFactors [1], yToL);
2792 Pi [0]=
M(1,1) +
mulMod2 (bufFactors [0] [1], bufFactors[1], yToL)*
v;
2794 else if (
degree (bufFactors[1],
v) > 0)
2796 M (1,1)=
mulMod2 (bufFactors [0], bufFactors [1] [0], yToL);
2797 Pi [0]=
M (1,1) +
mulMod2 (bufFactors [0], bufFactors[1] [1], yToL)*
v;
2801 M (1,1)=
mulMod2 (bufFactors [0], bufFactors [1], yToL);
2805 for (
i= 1;
i < Pi.
size();
i++)
2809 M (1,
i+1)=
mulMod2 (Pi[
i-1] [0], bufFactors[
i+1] [0], yToL);
2810 Pi [
i]=
M (1,
i+1) + (
mulMod2 (Pi[
i-1] [1], bufFactors[
i+1] [0], yToL) +
2811 mulMod2 (Pi[
i-1] [0], bufFactors [
i+1] [1], yToL))*
v;
2815 M (1,
i+1)=
mulMod2 (Pi[
i-1] [0], bufFactors [
i+1], yToL);
2816 Pi [
i]=
M(1,
i+1) +
mulMod2 (Pi[
i-1] [1], bufFactors[
i+1], yToL)*
v;
2818 else if (
degree (bufFactors[
i+1],
v) > 0)
2820 M (1,
i+1)=
mulMod2 (Pi[
i-1], bufFactors [
i+1] [0], yToL);
2821 Pi [
i]=
M (1,
i+1) +
mulMod2 (Pi[
i-1], bufFactors[
i+1] [1], yToL)*
v;
2825 M (1,
i+1)=
mulMod2 (Pi [
i-1], bufFactors [
i+1], yToL);
2834 products.
append (bufF/
k.getItem());
2839 for (
int d= 1; d < liftBound; d++)
2849 result.append (bufFactors[
i]);
2854#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2858 int& lNew,
const CFList& MOD,
bool& noOneToOne
2872 Pi [0]=
mod (Pi[0], xToLOld);
2875 if (
degree (bufFactors[0],
y) > 0 &&
degree (bufFactors [1],
y) > 0)
2876 Pi [0] += (
mulMod (bufFactors [0] [1], bufFactors[1] [0], MOD) +
2877 mulMod (bufFactors [0] [0], bufFactors [1] [1], MOD))*
y;
2878 else if (
degree (bufFactors[0],
y) > 0)
2879 Pi [0] +=
mulMod (bufFactors [0] [1], bufFactors[1], MOD)*
y;
2880 else if (
degree (bufFactors[1],
y) > 0)
2881 Pi [0] +=
mulMod (bufFactors [0], bufFactors[1] [1], MOD)*
y;
2883 for (
int i= 1;
i < Pi.
size();
i++)
2885 Pi [
i]=
mod (Pi [
i], xToLOld);
2886 M (1,
i + 1)= Pi [
i];
2889 Pi [
i] += (
mulMod (Pi[
i-1] [1], bufFactors[
i+1] [0], MOD) +
2890 mulMod (Pi[
i-1] [0], bufFactors [
i+1] [1], MOD))*
y;
2892 Pi [
i] +=
mulMod (Pi[
i-1] [1], bufFactors[
i+1], MOD)*
y;
2893 else if (
degree (bufFactors[
i+1],
y) > 0)
2894 Pi [
i] +=
mulMod (Pi[
i-1], bufFactors[
i+1] [1], MOD)*
y;
2901 for (
int i= 0;
i < bufFactors.
size();
i++)
2905 if (!
fdivides (bufFactors[
i] [0], bufF, quot))
2914 if (!
fdivides (bufFactors[
i], bufF, quot))
2924 for (
int d= 1; d < lNew; d++)
2927 products, d, MOD, noOneToOne);
2934 result.append (bufFactors[
k]);
2939#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2943 int* liftBound,
int length,
bool& noOneToOne
2946 CFList bufDiophant= diophant;
2955 liftBound[1], liftBound[0], noOneToOne);
2961 if (
eval.length() == 1)
2966 for (
int i= 0;
i < 2;
i++)
2974 for (
int i= 2;
i <=
length &&
j.hasItem();
i++,
j++,
k++)
2980 liftBound[
i-1], liftBound[
i], MOD, noOneToOne);
CanonicalForm convertFq_poly_t2FacCF(const fq_poly_t p, const Variable &x, const Variable &alpha, const fq_ctx_t ctx)
conversion of a FLINT poly over Fq (for non-word size p) to a CanonicalForm with alg....
CanonicalForm convertFq_nmod_poly_t2FacCF(const fq_nmod_poly_t p, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t ctx)
conversion of a FLINT poly over Fq to a CanonicalForm with alg. variable alpha and polynomial variabl...
void convertFacCF2Fq_nmod_t(fq_nmod_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory element of F_q to a FLINT fq_nmod_t, does not do any memory allocation for po...
void convertFacCF2Fmpz_mod_poly_t(fmpz_mod_poly_t result, const CanonicalForm &f, const fmpz_t p)
conversion of a factory univariate poly over Z to a FLINT poly over Z/p (for non word size p)
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
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
void convertFacCF2Fq_poly_t(fq_poly_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory univariate poly over F_q (for non-word size p) to a FLINT fq_poly_t
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Conversion to and from NTL.
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
void tryNTLXGCD(zz_pEX &d, zz_pEX &s, zz_pEX &t, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the extended GCD d=s*a+t*b, fail is set to true if a zero divisor is encountered
This file defines functions for univariate GCD and extended GCD over Z/p[t]/(f)[x] for reducible f.
static void sort(int **points, int sizePoints)
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
#define ASSERT(expression, message)
static const int SW_RATIONAL
set to 1 for computations over Q
static CanonicalForm bound(const CFMatrix &M)
int cf_getBigPrime(int i)
class to iterate through CanonicalForm's
CF_NO_INLINE int exp() const
get the current exponent
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
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 s
const CanonicalForm int const CFList const Variable & y
REvaluation E(1, terms.length(), IntRandom(25))
int hasAlgVar(const CanonicalForm &f, const Variable &v)
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
bivariate factorization over Q(a)
const Variable & v
< [in] a sqrfree bivariate poly
CFList diophantineHenselQa(const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b, const Variable &alpha)
solve mod over by p-adic lifting
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
CFList biDiophantine(const CanonicalForm &F, const CFList &factors, int d)
static int mod(const CFList &L, const CanonicalForm &p)
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
CFList nonMonicHenselLift23(const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad)
fq_nmod_ctx_clear(fq_con)
static CFList Farey(const CFList &L, const CanonicalForm &q)
static void chineseRemainder(const CFList &x1, const CanonicalForm &q1, const CFList &x2, const CanonicalForm &q2, CFList &xnew, CanonicalForm &qnew)
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.
CFList modularDiophant(const CanonicalForm &f, const CFList &factors, const CanonicalForm &M)
fq_nmod_poly_init(prod, fq_con)
CFList nonMonicHenselLift2(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &LCs1, const CFList &LCs2, bool &bad)
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
CanonicalForm replaceLC(const CanonicalForm &F, const CanonicalForm &c)
CFList diophantine(const CanonicalForm &F, const CFList &factors)
static CFList replacevar(const CFList &L, const Variable &a, const Variable &b)
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
CFList diophantineQa(const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b, const Variable &alpha)
solve mod over by first computing mod and if no zero divisor occurred compute it mod
void nonMonicHenselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, const CFList &products, int j, const CFList &MOD, bool &noOneToOne)
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)...
CFList nonMonicHenselLift232(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M, const CFList &LCs1, const CFList &LCs2, bool &bad)
static CFList mapinto(const CFList &L)
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
CFList multiRecDiophantine(const CanonicalForm &F, const CFList &factors, const CFList &recResult, const CFList &M, int d)
nmod_poly_clear(FLINTmipo)
static void henselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFList &MOD)
static void tryDiophantine(CFList &result, const CanonicalForm &F, const CFList &factors, const CanonicalForm &M, bool &fail)
void nonMonicHenselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &)
void henselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const modpk &b)
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
CFList diophantineHensel(const CanonicalForm &F, const CFList &factors, const modpk &b)
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),...
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
CanonicalForm divNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z,...
CanonicalForm modNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a),...
This file defines functions for fast multiplication and division with remainder.
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
operations mod p^k and some other useful functions for factorization
void setReduce(const Variable &alpha, bool reduce)
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)
static number Farey(number, number, const coeffs)
static BOOLEAN length(leftv result, leftv arg)
int status int void size_t count
int status int void * buf
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)