34#include <NTL/lzz_pEX.h>
43#if defined(HAVE_NTL) || defined(HAVE_FLINT)
49 fmpz_poly_init2 (
result, d*(degAy + 1));
50 _fmpz_poly_set_length (
result, d*(degAy + 1));
54 if (
i.coeff().inBaseDomain())
57 for (
j=
i.coeff();
j.hasTerms();
j++)
61 _fmpz_poly_normalise(
result);
71 int degf= fmpz_poly_degree (F);
84 repLength= degfSubK + 1;
86 fmpq_poly_init2 (
buf, repLength);
87 _fmpq_poly_set_length (
buf, repLength);
88 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k, repLength);
89 _fmpq_poly_normalise (
buf);
93 fmpq_poly_clear (
buf);
97 fmpq_poly_clear (
mipo);
116 int d= degAa + 1 + degBa;
118 fmpz_poly_t FLINTA,FLINTB;
122 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
127 fmpz_poly_clear (FLINTA);
128 fmpz_poly_clear (FLINTB);
143 fmpz_poly_t FLINTA,FLINTB;
146 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
150 fmpz_poly_clear (FLINTA);
151 fmpz_poly_clear (FLINTB);
179 fmpq_poly_t FLINTA,FLINTB;
183 fmpq_poly_div (FLINTA, FLINTA, FLINTB);
186 fmpq_poly_clear (FLINTA);
187 fmpq_poly_clear (FLINTB);
197 fmpq_poly_t FLINTA,FLINTB;
201 fmpq_poly_rem (FLINTA, FLINTA, FLINTB);
204 fmpq_poly_clear (FLINTA);
205 fmpq_poly_clear (FLINTB);
224 int d= degAa + 1 + degBa;
226 fmpz_poly_t FLINTA,FLINTB;
231 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB,
k);
235 fmpz_poly_clear (FLINTA);
236 fmpz_poly_clear (FLINTB);
247 if (
G.inCoeffDomain())
261 fmpz_poly_t FLINTA,FLINTB;
264 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB,
m);
268 fmpz_poly_clear (FLINTA);
269 fmpz_poly_clear (FLINTB);
282 while (d -
i.exp() < 0)
285 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
302 ASSERT (F.
mvar() ==
x,
"main variable of F and x differ");
303 ASSERT (!
g.isZero(),
"expected a unit");
316 for (
int i= 1;
i <=
l;
i++)
349 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
382 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
430#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
432 fmpz_mod_poly_t FLINTmipo;
434 fq_poly_t FLINTF, FLINTG;
442 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
443 fmpz_mod_ctx_t fmpz_ctx;
444 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
445 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
447 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
453 fq_poly_mul (FLINTF, FLINTF, FLINTG,
fq_con);
459 fq_poly_clear (FLINTF,
fq_con);
460 fq_poly_clear (FLINTG,
fq_con);
462 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
463 fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
464 fmpz_mod_ctx_clear(fmpz_ctx);
466 fmpz_mod_poly_clear(FLINTmipo);
473 ZZ_pE::init (NTLmipo);
476 mul (NTLf, NTLf, NTLg);
496 fmpz_mod_poly_t FLINTF, FLINTG;
499 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
500 fmpz_mod_ctx_t fmpz_ctx;
501 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
502 fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG, fmpz_ctx);
504 fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
507 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
508 fmpz_mod_poly_clear (FLINTG,fmpz_ctx);
509 fmpz_mod_poly_clear (FLINTF,fmpz_ctx);
510 fmpz_mod_ctx_clear(fmpz_ctx);
512 fmpz_mod_poly_clear (FLINTG);
513 fmpz_mod_poly_clear (FLINTF);
515 fmpz_clear (FLINTpk);
526 ZZ_pX NTLf= to_ZZ_pX (ZZf);
527 ZZ_pX NTLg= to_ZZ_pX (ZZg);
528 mul (NTLf, NTLf, NTLg);
540#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
542 fmpz_mod_poly_t FLINTmipo;
556 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
557 fmpz_mod_ctx_t fmpz_ctx;
558 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
559 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
561 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
573 fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF,
fq_con);
576 fmpz_poly_clear (FLINTF);
577 fq_poly_clear (FLINTG,
fq_con);
587 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG,
fq_con);
590 fmpz_poly_clear (FLINTG);
591 fq_poly_clear (FLINTF,
fq_con);
600 fq_mul (FLINTF, FLINTF, FLINTG,
fq_con);
603 fq_clear (FLINTF,
fq_con);
604 fq_clear (FLINTG,
fq_con);
608 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
609 fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
610 fmpz_mod_ctx_clear(fmpz_ctx);
612 fmpz_mod_poly_clear (FLINTmipo);
621 ZZ_pE::init (NTLmipo);
627 mul (NTLg, to_ZZ_pE (NTLf), NTLg);
634 mul (NTLf, NTLf, to_ZZ_pE (NTLg));
642 mul (
result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
655 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
657#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
676#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
677 nmod_poly_t FLINTmipo;
685 fq_nmod_poly_t FLINTF, FLINTG;
689 fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG,
fq_con);
698#elif defined(AHVE_NTL)
700 zz_pE::init (NTLMipo);
703 mul (NTLF, NTLF, NTLG);
711 nmod_poly_t FLINTF, FLINTG;
714 nmod_poly_mul (FLINTF, FLINTF, FLINTG);
723 mul (NTLF, NTLF, NTLG);
765 fmpz_mod_poly_t FLINTF, FLINTG;
768 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
769 fmpz_mod_ctx_t fmpz_ctx;
770 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
771 fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG, fmpz_ctx);
773 fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
776 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
777 fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
778 fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
779 fmpz_mod_ctx_clear(fmpz_ctx);
781 fmpz_mod_poly_clear (FLINTG);
782 fmpz_mod_poly_clear (FLINTF);
784 fmpz_clear (FLINTpk);
794 ZZ_pX NTLf= to_ZZ_pX (ZZf);
795 ZZ_pX NTLg= to_ZZ_pX (ZZg);
796 rem (NTLf, NTLf, NTLg);
806#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
808 fmpz_mod_poly_t FLINTmipo;
810 fq_poly_t FLINTF, FLINTG;
824 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
825 fmpz_mod_ctx_t fmpz_ctx;
826 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
827 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
829 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
835 fq_poly_rem (FLINTF, FLINTF, FLINTG,
fq_con);
841 fq_poly_clear (FLINTF,
fq_con);
842 fq_poly_clear (FLINTG,
fq_con);
844 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
845 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
846 fmpz_mod_ctx_clear(fmpz_ctx);
848 fmpz_mod_poly_clear (FLINTmipo);
855 ZZ_pE::init (NTLmipo);
858 rem (NTLf, NTLf, NTLg);
873 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
874#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
885#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
886 nmod_poly_t FLINTmipo;
894 fq_nmod_poly_t FLINTF, FLINTG;
898 fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG,
fq_con);
908 zz_pE::init (NTLMipo);
911 rem (NTLF, NTLF, NTLG);
918 nmod_poly_t FLINTF, FLINTG;
921 nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
928 rem (NTLF, NTLF, NTLG);
953#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
955 fmpz_mod_poly_t FLINTmipo;
964 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
965 fmpz_mod_ctx_t fmpz_ctx;
966 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
967 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
969 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
975 fq_inv (FLINTG, FLINTG,
fq_con);
976 fq_mul (FLINTF, FLINTF, FLINTG,
fq_con);
981 fq_clear (FLINTF,
fq_con);
982 fq_clear (FLINTG,
fq_con);
984 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
985 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
986 fmpz_mod_ctx_clear(fmpz_ctx);
988 fmpz_mod_poly_clear (FLINTmipo);
994 ZZ_pE::init (NTLmipo);
998 div (
result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
1002 return b(
div (F,
G));
1010 if (!
G.inBaseDomain())
1014#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1016 fmpz_mod_poly_t FLINTmipo;
1026 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1027 fmpz_mod_ctx_t fmpz_ctx;
1028 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1029 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
1031 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
1037 fq_inv (FLINTG, FLINTG,
fq_con);
1038 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG,
fq_con);
1043 fmpz_clear (FLINTp);
1044 fq_poly_clear (FLINTF,
fq_con);
1045 fq_clear (FLINTG,
fq_con);
1047 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1048 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1049 fmpz_mod_ctx_clear(fmpz_ctx);
1051 fmpz_mod_poly_clear (FLINTmipo);
1057 ZZ_pE::init (NTLmipo);
1060 div (NTLf, NTLf, to_ZZ_pE (NTLg));
1064 return b(
div (F,
G));
1079 fmpz_init (FLINTpk);
1081 fmpz_mod_poly_t FLINTF, FLINTG;
1084 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1085 fmpz_mod_ctx_t fmpz_ctx;
1086 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
1087 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fmpz_ctx);
1089 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
1092 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1093 fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
1094 fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
1095 fmpz_mod_ctx_clear(fmpz_ctx);
1097 fmpz_mod_poly_clear (FLINTG);
1098 fmpz_mod_poly_clear (FLINTF);
1100 fmpz_clear (FLINTpk);
1110 ZZ_pX NTLf= to_ZZ_pX (ZZf);
1111 ZZ_pX NTLg= to_ZZ_pX (ZZg);
1112 div (NTLf, NTLf, NTLg);
1122#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1124 fmpz_mod_poly_t FLINTmipo;
1126 fq_poly_t FLINTF, FLINTG;
1133 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1134 fmpz_mod_ctx_t fmpz_ctx;
1135 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1136 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
1138 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
1144 fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG,
fq_con);
1149 fmpz_clear (FLINTp);
1150 fq_poly_clear (FLINTF,
fq_con);
1151 fq_poly_clear (FLINTG,
fq_con);
1153 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1154 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1155 fmpz_mod_ctx_clear(fmpz_ctx);
1157 fmpz_mod_poly_clear (FLINTmipo);
1163 ZZ_pE::init (NTLmipo);
1166 div (NTLf, NTLf, NTLg);
1181 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
1182#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
1193#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1194 nmod_poly_t FLINTmipo;
1202 fq_nmod_poly_t FLINTF, FLINTG;
1206 fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG,
fq_con);
1216 zz_pE::init (NTLMipo);
1219 div (NTLF, NTLF, NTLG);
1226 nmod_poly_t FLINTF, FLINTG;
1229 nmod_poly_div (FLINTF, FLINTF, FLINTG);
1236 div (NTLF, NTLF, NTLG);
1252 result->length= d*(degAy + 1);
1253 flint_mpn_zero (
result->coeffs, d*(degAy+1));
1262 flint_mpn_copyi (
result->coeffs+
k,
buf->coeffs, nmod_poly_length(
buf));
1266 _nmod_poly_normalise (
result);
1269#if ( __FLINT_RELEASE >= 20400)
1272 const fq_nmod_ctx_t
fq_con)
1276 _fq_nmod_poly_set_length (
result, d*(degAy + 1),
fq_con);
1277 _fq_nmod_vec_zero (
result->coeffs, d*(degAy + 1),
fq_con);
1279 fq_nmod_poly_t
buf1;
1287 if (
i.coeff().inCoeffDomain())
1356 fmpz_poly_init2 (
result, d1*(degAy + 1));
1357 _fmpz_poly_set_length (
result, d1*(degAy + 1));
1365 if (
i.coeff().inCoeffDomain())
1369 _fmpz_vec_set (
result->coeffs +
k,
buf->coeffs,
buf->length);
1370 fmpz_poly_clear (
buf);
1374 for (
j=
i.coeff();
j.hasTerms();
j++)
1379 _fmpz_vec_set (
result->coeffs +
k,
buf->coeffs,
buf->length);
1380 fmpz_poly_clear (
buf);
1384 _fmpz_poly_normalise (
result);
1398 int k, kk,
j, bufRepLength;
1404 kk= (degAy -
i.exp())*d;
1405 bufRepLength= (int) nmod_poly_length (
buf);
1406 for (
j= 0;
j < bufRepLength;
j++)
1408 nmod_poly_set_coeff_ui (subA1,
j +
k,
1409 n_addmod (nmod_poly_get_coeff_ui (subA1,
j+
k),
1410 nmod_poly_get_coeff_ui (
buf,
j),
1414 nmod_poly_set_coeff_ui (subA2,
j + kk,
1415 n_addmod (nmod_poly_get_coeff_ui (subA2,
j + kk),
1416 nmod_poly_get_coeff_ui (
buf,
j),
1423 _nmod_poly_normalise (subA1);
1424 _nmod_poly_normalise (subA2);
1427#if ( __FLINT_RELEASE >= 20400)
1433 fq_nmod_poly_init2 (subA1, d*(degAy + 2),
fq_con);
1434 fq_nmod_poly_init2 (subA2, d*(degAy + 2),
fq_con);
1436 _fq_nmod_poly_set_length (subA1, d*(degAy + 2),
fq_con);
1437 _fq_nmod_vec_zero (subA1->coeffs, d*(degAy + 2),
fq_con);
1439 _fq_nmod_poly_set_length (subA2, d*(degAy + 2),
fq_con);
1440 _fq_nmod_vec_zero (subA2->coeffs, d*(degAy + 2),
fq_con);
1442 fq_nmod_poly_t
buf1;
1449 if (
i.coeff().inCoeffDomain())
1460 kk= (degAy -
i.exp())*d;
1461 _fq_nmod_vec_add (subA1->coeffs+
k, subA1->coeffs+
k,
buf1->coeffs,
1463 _fq_nmod_vec_add (subA2->coeffs+kk, subA2->coeffs+kk,
buf1->coeffs,
1468 _fq_nmod_poly_normalise (subA1,
fq_con);
1469 _fq_nmod_poly_normalise (subA2,
fq_con);
1478 fmpz_poly_init2 (subA1, d*(degAy + 2));
1479 fmpz_poly_init2 (subA2, d*(degAy + 2));
1489 kk= (degAy -
i.exp())*d;
1490 _fmpz_vec_add (subA1->coeffs+
k, subA1->coeffs +
k,
buf->coeffs,
buf->length);
1491 _fmpz_vec_add (subA2->coeffs+kk, subA2->coeffs + kk,
buf->coeffs,
buf->length);
1492 fmpz_poly_clear (
buf);
1495 _fmpz_poly_normalise (subA1);
1496 _fmpz_poly_normalise (subA2);
1507 int degf= fmpz_poly_degree(F);
1509 int degfSubK, repLength;
1516 repLength= degfSubK + 1;
1518 fmpz_poly_init2 (
buf, repLength);
1519 _fmpz_poly_set_length (
buf, repLength);
1520 _fmpz_vec_set (
buf->coeffs, F->coeffs+
k, repLength);
1521 _fmpz_poly_normalise (
buf);
1526 fmpz_poly_clear (
buf);
1606 const fmpq_poly_t
mipo)
1614 int degf= fmpz_poly_degree(F);
1624 repLength= degfSubK + 1;
1628 while (
j*d2 < repLength)
1630 fmpq_poly_init2 (
buf, d2);
1631 _fmpq_poly_set_length (
buf, d2);
1632 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k +
j*d2, d2);
1633 _fmpq_poly_normalise (
buf);
1637 fmpq_poly_clear (
buf);
1639 if (repLength -
j*d2 != 0 &&
j*d2 - repLength < d2)
1643 fmpq_poly_init2 (
buf, repLength);
1644 _fmpq_poly_set_length (
buf, repLength);
1646 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k +
j*d2, repLength);
1647 _fmpq_poly_normalise (
buf);
1650 fmpq_poly_clear (
buf);
1671 nmod_poly_set (
f, F);
1672 nmod_poly_set (
g,
G);
1673 int degf= nmod_poly_degree(
f);
1674 int degg= nmod_poly_degree(
g);
1679 if (nmod_poly_length (
f) < (
long) d*(
k+1))
1680 nmod_poly_fit_length (
f,(
long)d*(
k+1));
1686 int degfSubLf= degf;
1687 int deggSubLg=
degg-lg;
1688 int repLengthBuf2, repLengthBuf1, ind, tmp;
1689 while (degf >= lf || lg >= 0)
1693 else if (degfSubLf < 0)
1696 repLengthBuf1= degfSubLf + 1;
1699 for (ind= 0; ind < repLengthBuf1; ind++)
1700 nmod_poly_set_coeff_ui (
buf1, ind, nmod_poly_get_coeff_ui (
f, ind+lf));
1701 _nmod_poly_normalise (
buf1);
1703 repLengthBuf1= nmod_poly_length (
buf1);
1705 if (deggSubLg >= d - 1)
1706 repLengthBuf2= d - 1;
1707 else if (deggSubLg < 0)
1710 repLengthBuf2= deggSubLg + 1;
1713 for (ind= 0; ind < repLengthBuf2; ind++)
1714 nmod_poly_set_coeff_ui (
buf2, ind, nmod_poly_get_coeff_ui (
g, ind + lg));
1716 _nmod_poly_normalise (
buf2);
1717 repLengthBuf2= nmod_poly_length (
buf2);
1720 for (ind= 0; ind < repLengthBuf1; ind++)
1721 nmod_poly_set_coeff_ui (buf3, ind, nmod_poly_get_coeff_ui (
buf1, ind));
1722 for (ind= repLengthBuf1; ind < d; ind++)
1723 nmod_poly_set_coeff_ui (buf3, ind, 0);
1724 for (ind= 0; ind < repLengthBuf2; ind++)
1725 nmod_poly_set_coeff_ui (buf3, ind+d, nmod_poly_get_coeff_ui (
buf2, ind));
1726 _nmod_poly_normalise (buf3);
1733 degfSubLf= degf - lf;
1736 deggSubLg=
degg - lg;
1738 if (lg >= 0 && deggSubLg > 0)
1740 if (repLengthBuf2 > degfSubLf + 1)
1741 degfSubLf= repLengthBuf2 - 1;
1742 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1743 for (ind= 0; ind < tmp; ind++)
1744 nmod_poly_set_coeff_ui (
g, ind + lg,
1745 n_submod (nmod_poly_get_coeff_ui (
g, ind + lg),
1746 nmod_poly_get_coeff_ui (
buf1, ind),
1760 for (ind= 0; ind < repLengthBuf2; ind++)
1761 nmod_poly_set_coeff_ui (
f, ind + lf,
1762 n_submod (nmod_poly_get_coeff_ui (
f, ind + lf),
1763 nmod_poly_get_coeff_ui (
buf2, ind),
1779#if ( __FLINT_RELEASE >= 20400)
1787 fq_nmod_poly_t
f,
g;
1788 int degf= fq_nmod_poly_degree(F,
fq_con);
1795 fq_nmod_poly_set (
f, F,
fq_con);
1797 if (fq_nmod_poly_length (
f,
fq_con) < (
long) d*(
k + 1))
1798 fq_nmod_poly_fit_length (
f, (
long) d*(
k + 1),
fq_con);
1804 int degfSubLf= degf;
1805 int deggSubLg=
degg-lg;
1806 int repLengthBuf2, repLengthBuf1, tmp;
1807 while (degf >= lf || lg >= 0)
1811 else if (degfSubLf < 0)
1814 repLengthBuf1= degfSubLf + 1;
1815 fq_nmod_poly_init2 (
buf1, repLengthBuf1,
fq_con);
1816 _fq_nmod_poly_set_length (
buf1, repLengthBuf1,
fq_con);
1818 _fq_nmod_vec_set (
buf1->coeffs,
f->coeffs + lf, repLengthBuf1,
fq_con);
1821 repLengthBuf1= fq_nmod_poly_length (
buf1,
fq_con);
1823 if (deggSubLg >= d - 1)
1824 repLengthBuf2= d - 1;
1825 else if (deggSubLg < 0)
1828 repLengthBuf2= deggSubLg + 1;
1830 fq_nmod_poly_init2 (
buf2, repLengthBuf2,
fq_con);
1831 _fq_nmod_poly_set_length (
buf2, repLengthBuf2,
fq_con);
1832 _fq_nmod_vec_set (
buf2->coeffs,
g->coeffs + lg, repLengthBuf2,
fq_con);
1835 repLengthBuf2= fq_nmod_poly_length (
buf2,
fq_con);
1837 fq_nmod_poly_init2 (buf3, repLengthBuf2 + d,
fq_con);
1838 _fq_nmod_poly_set_length (buf3, repLengthBuf2 + d,
fq_con);
1839 _fq_nmod_vec_set (buf3->coeffs,
buf1->coeffs, repLengthBuf1,
fq_con);
1840 _fq_nmod_vec_set (buf3->coeffs + d,
buf2->coeffs, repLengthBuf2,
fq_con);
1842 _fq_nmod_poly_normalise (buf3,
fq_con);
1849 degfSubLf= degf - lf;
1852 deggSubLg=
degg - lg;
1854 if (lg >= 0 && deggSubLg > 0)
1856 if (repLengthBuf2 > degfSubLf + 1)
1857 degfSubLf= repLengthBuf2 - 1;
1858 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1859 _fq_nmod_vec_sub (
g->coeffs + lg,
g->coeffs + lg,
buf1->
coeffs,
1870 _fq_nmod_vec_sub (
f->coeffs + lf,
f->coeffs + lf,
buf2->coeffs,
1893 fmpz_poly_set (
f, F);
1894 fmpz_poly_set (
g,
G);
1895 int degf= fmpz_poly_degree(
f);
1896 int degg= fmpz_poly_degree(
g);
1900 if (fmpz_poly_length (
f) < (
long) d*(
k+1))
1901 fmpz_poly_fit_length (
f,(
long)d*(
k+1));
1907 int degfSubLf= degf;
1908 int deggSubLg=
degg-lg;
1909 int repLengthBuf2, repLengthBuf1, ind, tmp;
1911 while (degf >= lf || lg >= 0)
1915 else if (degfSubLf < 0)
1918 repLengthBuf1= degfSubLf + 1;
1920 fmpz_poly_init2 (
buf1, repLengthBuf1);
1922 for (ind= 0; ind < repLengthBuf1; ind++)
1924 fmpz_poly_get_coeff_fmpz (
tmp1,
f, ind + lf);
1925 fmpz_poly_set_coeff_fmpz (
buf1, ind,
tmp1);
1927 _fmpz_poly_normalise (
buf1);
1929 repLengthBuf1= fmpz_poly_length (
buf1);
1931 if (deggSubLg >= d - 1)
1932 repLengthBuf2= d - 1;
1933 else if (deggSubLg < 0)
1936 repLengthBuf2= deggSubLg + 1;
1938 fmpz_poly_init2 (
buf2, repLengthBuf2);
1940 for (ind= 0; ind < repLengthBuf2; ind++)
1942 fmpz_poly_get_coeff_fmpz (
tmp1,
g, ind + lg);
1943 fmpz_poly_set_coeff_fmpz (
buf2, ind,
tmp1);
1946 _fmpz_poly_normalise (
buf2);
1947 repLengthBuf2= fmpz_poly_length (
buf2);
1949 fmpz_poly_init2 (buf3, repLengthBuf2 + d);
1950 for (ind= 0; ind < repLengthBuf1; ind++)
1952 fmpz_poly_get_coeff_fmpz (
tmp1,
buf1, ind);
1953 fmpz_poly_set_coeff_fmpz (buf3, ind,
tmp1);
1955 for (ind= repLengthBuf1; ind < d; ind++)
1956 fmpz_poly_set_coeff_ui (buf3, ind, 0);
1957 for (ind= 0; ind < repLengthBuf2; ind++)
1959 fmpz_poly_get_coeff_fmpz (
tmp1,
buf2, ind);
1960 fmpz_poly_set_coeff_fmpz (buf3, ind + d,
tmp1);
1962 _fmpz_poly_normalise (buf3);
1969 degfSubLf= degf - lf;
1972 deggSubLg=
degg - lg;
1974 if (lg >= 0 && deggSubLg > 0)
1976 if (repLengthBuf2 > degfSubLf + 1)
1977 degfSubLf= repLengthBuf2 - 1;
1978 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1979 for (ind= 0; ind < tmp; ind++)
1981 fmpz_poly_get_coeff_fmpz (
tmp1,
g, ind + lg);
1982 fmpz_poly_get_coeff_fmpz (
tmp2,
buf1, ind);
1984 fmpz_poly_set_coeff_fmpz (
g, ind + lg,
tmp1);
1989 fmpz_poly_clear (
buf1);
1990 fmpz_poly_clear (
buf2);
1991 fmpz_poly_clear (buf3);
1996 for (ind= 0; ind < repLengthBuf2; ind++)
1998 fmpz_poly_get_coeff_fmpz (
tmp1,
f, ind + lf);
1999 fmpz_poly_get_coeff_fmpz (
tmp2,
buf2, ind);
2001 fmpz_poly_set_coeff_fmpz (
f, ind + lf,
tmp1);
2004 fmpz_poly_clear (
buf1);
2005 fmpz_poly_clear (
buf2);
2006 fmpz_poly_clear (buf3);
2009 fmpz_poly_clear (
f);
2010 fmpz_poly_clear (
g);
2017#if ( __FLINT_RELEASE >= 20400)
2020 const fq_nmod_ctx_t
fq_con)
2028 int degf= fq_nmod_poly_degree(F,
fq_con);
2030 int degfSubK, repLength;
2037 repLength= degfSubK + 1;
2039 fq_nmod_poly_init2 (
buf, repLength,
fq_con);
2040 _fq_nmod_poly_set_length (
buf, repLength,
fq_con);
2041 _fq_nmod_vec_set (
buf->coeffs, F->coeffs+
k, repLength,
fq_con);
2064 int degf= nmod_poly_degree(F);
2066 int degfSubK, repLength,
j;
2073 repLength= degfSubK + 1;
2076 for (
j= 0;
j < repLength;
j++)
2077 nmod_poly_set_coeff_ui (
buf,
j, nmod_poly_get_coeff_ui (F,
j +
k));
2078 _nmod_poly_normalise (
buf);
2104 nmod_poly_mullow (
F1,
F1, G1, (
long)
k);
2111 int b= nmod_poly_degree (
F2) + nmod_poly_degree (G2) -
k - degtailF - degtailG
2112 + d1*(2+taildegF + taildegG);
2113 nmod_poly_mulhigh (
F2,
F2, G2,
b);
2114 nmod_poly_shift_right (
F2,
F2,
b);
2115 int d2=
tmax (nmod_poly_degree (
F2)/d1, nmod_poly_degree (
F1)/d1);
2138 int d1= degAx + 1 + degBx;
2139 int d2=
tmax (degAy, degBy);
2141 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2144 nmod_poly_t FLINTA, FLINTB;
2149 nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k);
2158#if ( __FLINT_RELEASE >= 20400)
2162 const fq_nmod_ctx_t
fq_con)
2168 fq_nmod_poly_t
F1,
F2;
2171 fq_nmod_poly_t G1, G2;
2175 fq_nmod_poly_mullow (
F1,
F1, G1, (
long)
k,
fq_con);
2182 int b=
k + degtailF + degtailG - d1*(2+taildegF + taildegG);
2185 fq_nmod_poly_reverse (G2, G2, fq_nmod_poly_length (G2,
fq_con),
fq_con);
2190 fq_nmod_poly_degree (
F1,
fq_con)/d1);
2204 const fq_nmod_ctx_t
fq_con)
2213 int d1= degAx + 1 + degBx;
2214 int d2=
tmax (degAy, degBy);
2216 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2219 fq_nmod_poly_t FLINTA, FLINTB;
2224 fq_nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k,
fq_con);
2249 fmpz_poly_mullow (
F1,
F1, G1, (
long)
k);
2256 int b= fmpz_poly_degree (
F2) + fmpz_poly_degree (G2) -
k - degtailF - degtailG
2257 + d1*(2+taildegF + taildegG);
2258 fmpz_poly_mulhigh_n (
F2,
F2, G2,
b);
2259 fmpz_poly_shift_right (
F2,
F2,
b);
2260 int d2=
tmax (fmpz_poly_degree (
F2)/d1, fmpz_poly_degree (
F1)/d1);
2264 fmpz_poly_clear (
F1);
2265 fmpz_poly_clear (
F2);
2266 fmpz_poly_clear (G1);
2267 fmpz_poly_clear (G2);
2280 int d1= degAx + 1 + degBx;
2287 fmpz_poly_t FLINTA, FLINTB;
2292 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k);
2294 fmpz_poly_clear (FLINTA);
2295 fmpz_poly_clear (FLINTB);
2340 int degFx=
degree (F, 1);
2341 int degFa=
degree (F, a);
2345 int d2= degFa+degGa+1;
2346 int d1= degFx + 1 + degGx;
2354 fmpz_poly_t FLINTF, FLINTG;
2358 fmpz_poly_mullow (FLINTF, FLINTF, FLINTG, d1*
degree (
M));
2363 fmpz_poly_clear (FLINTF);
2364 fmpz_poly_clear (FLINTG);
2375 result.rep.SetLength (d*(degAy + 1));
2378 resultp=
result.rep.elts();
2381 int j,
k, bufRepLength;
2385 if (
i.coeff().inCoeffDomain())
2391 bufp=
buf.rep.elts();
2392 bufRepLength= (int)
buf.rep.length();
2393 for (
j= 0;
j < bufRepLength;
j++)
2394 resultp [
j +
k]= bufp [
j];
2402#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2407 result.rep.SetLength (d*(degAy + 1));
2411 resultp=
result.rep.elts();
2416 int j,
k, buf1RepLength;
2420 if (
i.coeff().inCoeffDomain())
2429 buf1p=
buf1.rep.elts();
2430 buf1RepLength= (int)
buf1.rep.length();
2431 for (
j= 0;
j < buf1RepLength;
j++)
2432 resultp [
j +
k]= buf1p [
j];
2444 subA1.rep.SetLength ((
long) d*(degAy + 2));
2445 subA2.rep.SetLength ((
long) d*(degAy + 2));
2450 subA1p= subA1.rep.elts();
2451 subA2p= subA2.rep.elts();
2456 int j,
k, kk, bufRepLength;
2460 if (
i.coeff().inCoeffDomain())
2463 buf= to_zz_pEX (to_zz_pE (
buf2));
2469 kk= (degAy -
i.exp())*d;
2470 bufp=
buf.rep.elts();
2471 bufRepLength= (int)
buf.rep.length();
2472 for (
j= 0;
j < bufRepLength;
j++)
2474 subA1p [
j +
k] += bufp [
j];
2475 subA2p [
j + kk] += bufp [
j];
2488 subA1.rep.SetLength ((
long) d*(degAy + 2));
2489 subA2.rep.SetLength ((
long) d*(degAy + 2));
2493 subA1p= subA1.rep.elts();
2494 subA2p= subA2.rep.elts();
2497 int j,
k, kk, bufRepLength;
2504 kk= (degAy -
i.exp())*d;
2505 bufp=
buf.rep.elts();
2506 bufRepLength= (int)
buf.rep.length();
2507 for (
j= 0;
j < bufRepLength;
j++)
2509 subA1p [
j +
k] += bufp [
j];
2510 subA2p [
j + kk] += bufp [
j];
2518#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2538 if (
f.rep.length() < (
long) d*(
k+1))
2539 f.rep.SetLength ((
long)d*(
k+1));
2541 zz_pE *
gp=
g.rep.elts();
2542 zz_pE *
fp=
f.rep.elts();
2547 int degfSubLf= degf;
2548 int deggSubLg=
degg-lg;
2549 int repLengthBuf2, repLengthBuf1, ind, tmp;
2550 zz_pE zzpEZero= zz_pE();
2552 while (degf >= lf || lg >= 0)
2556 else if (degfSubLf < 0)
2559 repLengthBuf1= degfSubLf + 1;
2560 buf1.rep.SetLength((
long) repLengthBuf1);
2562 buf1p=
buf1.rep.elts();
2563 for (ind= 0; ind < repLengthBuf1; ind++)
2564 buf1p [ind]=
fp [ind + lf];
2567 repLengthBuf1=
buf1.rep.length();
2569 if (deggSubLg >= d - 1)
2570 repLengthBuf2= d - 1;
2571 else if (deggSubLg < 0)
2574 repLengthBuf2= deggSubLg + 1;
2576 buf2.rep.SetLength ((
long) repLengthBuf2);
2577 buf2p=
buf2.rep.elts();
2578 for (ind= 0; ind < repLengthBuf2; ind++)
2579 buf2p [ind]= gp [ind + lg];
2582 repLengthBuf2=
buf2.rep.length();
2584 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2585 buf3p= buf3.rep.elts();
2586 buf2p=
buf2.rep.elts();
2587 buf1p=
buf1.rep.elts();
2588 for (ind= 0; ind < repLengthBuf1; ind++)
2589 buf3p [ind]= buf1p [ind];
2590 for (ind= repLengthBuf1; ind < d; ind++)
2591 buf3p [ind]= zzpEZero;
2592 for (ind= 0; ind < repLengthBuf2; ind++)
2593 buf3p [ind + d]= buf2p [ind];
2601 degfSubLf= degf - lf;
2604 deggSubLg=
degg - lg;
2606 buf1p=
buf1.rep.elts();
2608 if (lg >= 0 && deggSubLg > 0)
2610 if (repLengthBuf2 > degfSubLf + 1)
2611 degfSubLf= repLengthBuf2 - 1;
2612 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2613 for (ind= 0; ind < tmp; ind++)
2614 gp [ind + lg] -= buf1p [ind];
2620 buf2p=
buf2.rep.elts();
2623 for (ind= 0; ind < repLengthBuf2; ind++)
2624 fp [ind + lf] -= buf2p [ind];
2652 if (
f.rep.length() < (
long) d*(
k+1))
2653 f.rep.SetLength ((
long)d*(
k+1));
2655 zz_p *
gp=
g.rep.elts();
2656 zz_p *
fp=
f.rep.elts();
2661 int degfSubLf= degf;
2662 int deggSubLg=
degg-lg;
2663 int repLengthBuf2, repLengthBuf1, ind, tmp;
2664 zz_p zzpZero= zz_p();
2665 while (degf >= lf || lg >= 0)
2669 else if (degfSubLf < 0)
2672 repLengthBuf1= degfSubLf + 1;
2673 buf1.rep.SetLength((
long) repLengthBuf1);
2675 buf1p=
buf1.rep.elts();
2676 for (ind= 0; ind < repLengthBuf1; ind++)
2677 buf1p [ind]=
fp [ind + lf];
2680 repLengthBuf1=
buf1.rep.length();
2682 if (deggSubLg >= d - 1)
2683 repLengthBuf2= d - 1;
2684 else if (deggSubLg < 0)
2687 repLengthBuf2= deggSubLg + 1;
2689 buf2.rep.SetLength ((
long) repLengthBuf2);
2690 buf2p=
buf2.rep.elts();
2691 for (ind= 0; ind < repLengthBuf2; ind++)
2692 buf2p [ind]= gp [ind + lg];
2696 repLengthBuf2=
buf2.rep.length();
2699 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2700 buf3p= buf3.rep.elts();
2701 buf2p=
buf2.rep.elts();
2702 buf1p=
buf1.rep.elts();
2703 for (ind= 0; ind < repLengthBuf1; ind++)
2704 buf3p [ind]= buf1p [ind];
2705 for (ind= repLengthBuf1; ind < d; ind++)
2706 buf3p [ind]= zzpZero;
2707 for (ind= 0; ind < repLengthBuf2; ind++)
2708 buf3p [ind + d]= buf2p [ind];
2716 degfSubLf= degf - lf;
2719 deggSubLg=
degg - lg;
2721 buf1p=
buf1.rep.elts();
2723 if (lg >= 0 && deggSubLg > 0)
2725 if (repLengthBuf2 > degfSubLf + 1)
2726 degfSubLf= repLengthBuf2 - 1;
2727 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2728 for (ind= 0; ind < tmp; ind++)
2729 gp [ind + lg] -= buf1p [ind];
2734 buf2p=
buf2.rep.elts();
2737 for (ind= 0; ind < repLengthBuf2; ind++)
2738 fp [ind + lf] -= buf2p [ind];
2746#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2753 zz_pE *
fp=
f.rep.elts();
2761 int degfSubK, repLength,
j;
2768 repLength= degfSubK + 1;
2770 buf.rep.SetLength ((
long) repLength);
2771 bufp=
buf.rep.elts();
2772 for (
j= 0;
j < repLength;
j++)
2773 bufp [
j]=
fp [
j +
k];
2792 zz_p *
fp=
f.rep.elts();
2800 int degfSubK, repLength,
j;
2807 repLength= degfSubK + 1;
2809 buf.rep.SetLength ((
long) repLength);
2810 bufp=
buf.rep.elts();
2811 for (
j= 0;
j < repLength;
j++)
2812 bufp [
j]=
fp [
j +
k];
2838 MulTrunc (
F1,
F1, G1, (
long)
k);
2844 int b=
k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2848 MulTrunc (
F2,
F2, G2,
b + 1);
2851 int d2=
tmax (deg (
F2)/d1, deg (
F1)/d1);
2867 int d1= degAx + 1 + degBx;
2868 int d2=
tmax (degAy, degBy);
2870 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2871 return mulMod2NTLFpReci (
A,
B,
M);
2877 MulTrunc (NTLA, NTLA, NTLB, (
long)
k);
2885#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2901 MulTrunc (
F1,
F1, G1, (
long)
k);
2907 int b=
k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2911 MulTrunc (
F2,
F2, G2,
b + 1);
2914 int d2=
tmax (deg (
F2)/d1, deg (
F1)/d1);
2935#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
2936 nmod_poly_t FLINTmipo;
2950 int d1= degAx + degBx + 1;
2951 int d2=
tmax (degAy, degBy);
2958 zz_pE::init (NTLMipo);
2961 if ((d1 > 128/degMipo) && (d2 > 160/degMipo) && (degAy == degBy) &&
2963 return mulMod2NTLFqReci (
A,
B,
M,
alpha);
2970 MulTrunc (NTLA, NTLA, NTLB, (
long)
k);
2980 A= mulMod2NTLFp (
A,
B,
M);
2992 ASSERT (
M.isUnivariate(),
"M must be univariate");
2998 if (
G.inCoeffDomain())
3005 if ((degF < 1 && degG < 1) && (F.
isUnivariate() &&
G.isUnivariate()) &&
3006 (F.
level() ==
G.level()))
3011 else if (degF <= 1 && degG <= 1)
3017 int sizeF=
size (F);
3018 int sizeG=
size (
G);
3020 int fallBackToNaive= 50;
3021 if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
3024 return mod (
G*F,
M);
3026 return mod (F*
G,
M);
3035 (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
3038 int m= (int) ceil (
degree (
M)/2.0);
3039 if (degF >=
m || degG >=
m)
3050 return F0G0 + MLo*(F0G1 + F1G0);
3054 m= (int) ceil (
tmax (degF, degG)/2.0);
3063 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3065 DEBOUTLN (cerr,
"fatal end in mulMod2");
3094 if (
G.inCoeffDomain())
3097 int sizeF=
size (F);
3098 int sizeG=
size (
G);
3100 if (sizeF / MOD.
length() < 100 || sizeG / MOD.
length() < 100)
3103 return mod (
G*F, MOD);
3105 return mod (F*
G, MOD);
3112 if ((degF <= 1 && F.
level() <=
M.level()) &&
3113 (degG <= 1 &&
G.level() <=
M.level()))
3117 if (degF == 1 && degG == 1)
3128 return H11*
y*
y + (H01 - H00 - H11)*
y + H00;
3140 else if (degF == 1 && degG == 0)
3142 else if (degF == 0 && degG == 1)
3147 int m= (int) ceil (
degree (
M)/2.0);
3148 if (degF >=
m || degG >=
m)
3162 return F0G0 + MLo*(F0G1 + F1G0);
3166 m= (
tmax(degF, degG)+1)/2;
3175 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3177 DEBOUTLN (cerr,
"fatal end in mulMod");
3197 for (
int j= 1;
j <=
l;
j++,
i++)
3211 else if (L.
length() == 1)
3213 else if (L.
length() == 2)
3221 for (
int j= 1;
j <=
l;
j++,
i++)
3246 while (d -
i.exp() < 0)
3249 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
3264 ASSERT (!
g.isZero(),
"expected a unit");
3280 for (
int i= 1;
i <=
l;
i++)
3349#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3350 nmod_poly_t FLINTmipo;
3359 fq_nmod_poly_t FLINTA, FLINTB;
3363 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB,
fq_con);
3372 bool zz_pEbak= zz_pE::initialized();
3380 div (NTLA, NTLA, NTLB);
3432#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3433 nmod_poly_t FLINTmipo;
3441 fq_nmod_poly_t FLINTA, FLINTB;
3445 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB,
fq_con);
3460 DivRem (NTLQ, NTLR, NTLA, NTLB);
3476 else if (
x.
level() !=
A.level())
3482 int j= (int) floor ((
double)
degree (
A)/
m);
3487 while (
i.hasTerms() &&
i.exp() -
j*
m >= 0)
3530 int m= (int) ceil ((
double) (degB + 1)/2.0) + 1;
3531 ASSERT (4*
m >= degA,
"expected degree (F, 1) < 2*degree (G, 1)");
3533 if (splitA.
length() == 3)
3535 if (splitA.
length() == 2)
3540 if (splitA.
length() == 1)
3562 if (splitR.
length() == 1)
3601 int m= (int) ceil ((
double) (degB + 1)/ 2.0);
3602 ASSERT (3*
m > degA,
"expected degree (F, 1) < 3*degree (G, 1)");
3606 if (splitA.
length() == 2)
3610 if (splitA.
length() == 1)
3640 Q +=
LC (
R,
x)*xToM;
3699 H=
i.getItem()*xToDegB;
3709 H=
R*xToDegB +
i.getItem();
3743 H=
i.getItem()*xToDegB;
3751 H=
R*xToDegB +
i.getItem();
3770 if (
A.inCoeffDomain())
3777#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
3787#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3788 nmod_poly_t FLINTmipo;
3796 fq_nmod_poly_t FLINTA, FLINTB;
3799 int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA,
fq_con);
3807 zz_pE::init (NTLMipo);
3810 return divide (NTLB, NTLA);
3814 nmod_poly_t FLINTA, FLINTB;
3817 nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3818 bool result= nmod_poly_is_zero (FLINTA);
3825 return divide (NTLB, NTLA);
3835 fmpq_poly_t FLINTA,FLINTB;
3838 fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3839 bool result= fmpq_poly_is_zero (FLINTA);
3840 fmpq_poly_clear (FLINTA);
3841 fmpq_poly_clear (FLINTB);
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....
void convertFacCF2Fq_t(fq_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory element of F_q (for non-word size p) to a FLINT fq_t
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...
CanonicalForm convertFq_t2FacCF(const fq_t poly, const Variable &alpha)
conversion of a FLINT element of F_q with non-word size p to a CanonicalForm with alg....
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
CanonicalForm convertFmpz_mod_poly_t2FacCF(const fmpz_mod_poly_t poly, const Variable &x, const modpk &b)
conversion of a FLINT poly over Z/p (for non word size p) to a CanonicalForm over Z
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
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
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_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 convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Conversion to and from NTL.
CanonicalForm cd(bCommonDen(FF))
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 )
declarations of higher level algorithms.
#define ASSERT(expression, message)
static const int SW_RATIONAL
set to 1 for computations over Q
#define GaloisFieldDomain
Iterators for CanonicalForm's.
class to iterate through CanonicalForm's
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 const Variable & y
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
const Variable & v
< [in] a sqrfree bivariate poly
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_init(prod, fq_con)
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion,...
void kronSubFq(fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
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),...
void divrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &MOD)
division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel,...
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
CanonicalForm divFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
CanonicalForm reverseSubstFp(const nmod_poly_t F, int d)
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
static void divrem32(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
CanonicalForm mulMod2FLINTQ(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm reverse(const CanonicalForm &F, int d)
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
CanonicalForm mulMod2FLINTFqReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm mulFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
CanonicalForm mulMod2FLINTFpReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm mulMod2FLINTFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm reverseSubstReciproFq(const fq_nmod_poly_t F, const fq_nmod_poly_t G, int d, int k, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm modFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
void kronSubReciproQ(fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm &A, int d)
void kronSubReciproFq(fq_nmod_poly_t subA1, fq_nmod_poly_t subA2, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
CanonicalForm reverseSubstQ(const fmpz_poly_t F, int d)
CanonicalForm mulMod2FLINTQReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm reverseSubstFq(const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
CanonicalForm mulFLINTQa(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
CanonicalForm reverseSubstReciproQ(const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
void divrem2(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel,...
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
void kronSubReciproFp(nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm &A, int d)
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 mulFLINTQaTrunc(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, int m)
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),...
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
CanonicalForm reverseSubstReciproFp(const nmod_poly_t F, const nmod_poly_t G, int d, int k)
void kronSubFp(nmod_poly_t result, const CanonicalForm &A, int d)
CanonicalForm mulMod2FLINTFp(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm mulMod2NTLFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm mulMod2FLINTQa(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
This file defines functions for fast multiplication and division with remainder.
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
gmp_float exp(const gmp_float &a)
The main handler for Singular numbers which are suitable for Singular polynomials.
int status int void * buf
int F1(int a1, int &r1)
F1.
void F2(int a2, int &r2)
F2.
bool getReduce(const Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)