35#include <NTL/lzz_pEX.h>
41#include "flint/fq_nmod_vec.h"
42#if __FLINT_RELEASE >= 20503
43#include "flint/mpn_extras.h"
44#include "flint/fmpz_mod.h"
49#if defined(HAVE_NTL) || defined(HAVE_FLINT)
55 fmpz_poly_init2 (
result, d*(degAy + 1));
56 _fmpz_poly_set_length (
result, d*(degAy + 1));
60 if (
i.coeff().inBaseDomain())
63 for (
j=
i.coeff();
j.hasTerms();
j++)
67 _fmpz_poly_normalise(
result);
77 int degf= fmpz_poly_degree (F);
90 repLength= degfSubK + 1;
92 fmpq_poly_init2 (
buf, repLength);
93 _fmpq_poly_set_length (
buf, repLength);
94 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k, repLength);
95 _fmpq_poly_normalise (
buf);
99 fmpq_poly_clear (
buf);
103 fmpq_poly_clear (
mipo);
122 int d= degAa + 1 + degBa;
124 fmpz_poly_t FLINTA,FLINTB;
128 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
133 fmpz_poly_clear (FLINTA);
134 fmpz_poly_clear (FLINTB);
149 fmpz_poly_t FLINTA,FLINTB;
152 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
156 fmpz_poly_clear (FLINTA);
157 fmpz_poly_clear (FLINTB);
185 fmpq_poly_t FLINTA,FLINTB;
189 fmpq_poly_div (FLINTA, FLINTA, FLINTB);
192 fmpq_poly_clear (FLINTA);
193 fmpq_poly_clear (FLINTB);
203 fmpq_poly_t FLINTA,FLINTB;
207 fmpq_poly_rem (FLINTA, FLINTA, FLINTB);
210 fmpq_poly_clear (FLINTA);
211 fmpq_poly_clear (FLINTB);
230 int d= degAa + 1 + degBa;
232 fmpz_poly_t FLINTA,FLINTB;
237 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB,
k);
241 fmpz_poly_clear (FLINTA);
242 fmpz_poly_clear (FLINTB);
253 if (
G.inCoeffDomain())
267 fmpz_poly_t FLINTA,FLINTB;
270 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB,
m);
274 fmpz_poly_clear (FLINTA);
275 fmpz_poly_clear (FLINTB);
288 while (d -
i.exp() < 0)
291 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
308 ASSERT (F.
mvar() ==
x,
"main variable of F and x differ");
309 ASSERT (!
g.isZero(),
"expected a unit");
322 for (
int i= 1;
i <=
l;
i++)
355 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
388 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
436#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
438 fmpz_mod_poly_t FLINTmipo;
440 fq_poly_t FLINTF, FLINTG;
448 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
449 fmpz_mod_ctx_t fmpz_ctx;
450 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
451 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
453 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
459 fq_poly_mul (FLINTF, FLINTF, FLINTG,
fq_con);
465 fq_poly_clear (FLINTF,
fq_con);
466 fq_poly_clear (FLINTG,
fq_con);
468 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
469 fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
470 fmpz_mod_ctx_clear(fmpz_ctx);
472 fmpz_mod_poly_clear(FLINTmipo);
479 ZZ_pE::init (NTLmipo);
482 mul (NTLf, NTLf, NTLg);
502 fmpz_mod_poly_t FLINTF, FLINTG;
505 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
506 fmpz_mod_ctx_t fmpz_ctx;
507 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
508 fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG, fmpz_ctx);
510 fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
513 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
514 fmpz_mod_poly_clear (FLINTG,fmpz_ctx);
515 fmpz_mod_poly_clear (FLINTF,fmpz_ctx);
516 fmpz_mod_ctx_clear(fmpz_ctx);
518 fmpz_mod_poly_clear (FLINTG);
519 fmpz_mod_poly_clear (FLINTF);
521 fmpz_clear (FLINTpk);
532 ZZ_pX NTLf= to_ZZ_pX (ZZf);
533 ZZ_pX NTLg= to_ZZ_pX (ZZg);
534 mul (NTLf, NTLf, NTLg);
546#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
548 fmpz_mod_poly_t FLINTmipo;
562 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
563 fmpz_mod_ctx_t fmpz_ctx;
564 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
565 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
567 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
579 fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF,
fq_con);
582 fmpz_poly_clear (FLINTF);
583 fq_poly_clear (FLINTG,
fq_con);
593 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG,
fq_con);
596 fmpz_poly_clear (FLINTG);
597 fq_poly_clear (FLINTF,
fq_con);
606 fq_mul (FLINTF, FLINTF, FLINTG,
fq_con);
609 fq_clear (FLINTF,
fq_con);
610 fq_clear (FLINTG,
fq_con);
614 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
615 fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
616 fmpz_mod_ctx_clear(fmpz_ctx);
618 fmpz_mod_poly_clear (FLINTmipo);
627 ZZ_pE::init (NTLmipo);
633 mul (NTLg, to_ZZ_pE (NTLf), NTLg);
640 mul (NTLf, NTLf, to_ZZ_pE (NTLg));
648 mul (
result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
661 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
663#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
682#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
683 nmod_poly_t FLINTmipo;
691 fq_nmod_poly_t FLINTF, FLINTG;
695 fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG,
fq_con);
704#elif defined(AHVE_NTL)
706 zz_pE::init (NTLMipo);
709 mul (NTLF, NTLF, NTLG);
717 nmod_poly_t FLINTF, FLINTG;
720 nmod_poly_mul (FLINTF, FLINTF, FLINTG);
729 mul (NTLF, NTLF, NTLG);
771 fmpz_mod_poly_t FLINTF, FLINTG;
774 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
775 fmpz_mod_ctx_t fmpz_ctx;
776 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
777 fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG, fmpz_ctx);
779 fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
782 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
783 fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
784 fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
785 fmpz_mod_ctx_clear(fmpz_ctx);
787 fmpz_mod_poly_clear (FLINTG);
788 fmpz_mod_poly_clear (FLINTF);
790 fmpz_clear (FLINTpk);
800 ZZ_pX NTLf= to_ZZ_pX (ZZf);
801 ZZ_pX NTLg= to_ZZ_pX (ZZg);
802 rem (NTLf, NTLf, NTLg);
812#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
814 fmpz_mod_poly_t FLINTmipo;
816 fq_poly_t FLINTF, FLINTG;
830 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
831 fmpz_mod_ctx_t fmpz_ctx;
832 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
833 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
835 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
841 fq_poly_rem (FLINTF, FLINTF, FLINTG,
fq_con);
847 fq_poly_clear (FLINTF,
fq_con);
848 fq_poly_clear (FLINTG,
fq_con);
850 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
851 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
852 fmpz_mod_ctx_clear(fmpz_ctx);
854 fmpz_mod_poly_clear (FLINTmipo);
861 ZZ_pE::init (NTLmipo);
864 rem (NTLf, NTLf, NTLg);
879 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
880#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
891#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
892 nmod_poly_t FLINTmipo;
900 fq_nmod_poly_t FLINTF, FLINTG;
904 fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG,
fq_con);
914 zz_pE::init (NTLMipo);
917 rem (NTLF, NTLF, NTLG);
924 nmod_poly_t FLINTF, FLINTG;
927 nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
934 rem (NTLF, NTLF, NTLG);
959#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
961 fmpz_mod_poly_t FLINTmipo;
970 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
971 fmpz_mod_ctx_t fmpz_ctx;
972 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
973 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
975 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
981 fq_inv (FLINTG, FLINTG,
fq_con);
982 fq_mul (FLINTF, FLINTF, FLINTG,
fq_con);
987 fq_clear (FLINTF,
fq_con);
988 fq_clear (FLINTG,
fq_con);
990 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
991 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
992 fmpz_mod_ctx_clear(fmpz_ctx);
994 fmpz_mod_poly_clear (FLINTmipo);
1000 ZZ_pE::init (NTLmipo);
1004 div (
result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
1008 return b(
div (F,
G));
1016 if (!
G.inBaseDomain())
1020#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1022 fmpz_mod_poly_t FLINTmipo;
1032 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1033 fmpz_mod_ctx_t fmpz_ctx;
1034 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1035 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
1037 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
1043 fq_inv (FLINTG, FLINTG,
fq_con);
1044 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG,
fq_con);
1049 fmpz_clear (FLINTp);
1050 fq_poly_clear (FLINTF,
fq_con);
1051 fq_clear (FLINTG,
fq_con);
1053 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1054 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1055 fmpz_mod_ctx_clear(fmpz_ctx);
1057 fmpz_mod_poly_clear (FLINTmipo);
1063 ZZ_pE::init (NTLmipo);
1066 div (NTLf, NTLf, to_ZZ_pE (NTLg));
1070 return b(
div (F,
G));
1085 fmpz_init (FLINTpk);
1087 fmpz_mod_poly_t FLINTF, FLINTG;
1090 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1091 fmpz_mod_ctx_t fmpz_ctx;
1092 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
1093 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fmpz_ctx);
1095 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
1098 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1099 fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
1100 fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
1101 fmpz_mod_ctx_clear(fmpz_ctx);
1103 fmpz_mod_poly_clear (FLINTG);
1104 fmpz_mod_poly_clear (FLINTF);
1106 fmpz_clear (FLINTpk);
1116 ZZ_pX NTLf= to_ZZ_pX (ZZf);
1117 ZZ_pX NTLg= to_ZZ_pX (ZZg);
1118 div (NTLf, NTLf, NTLg);
1128#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1130 fmpz_mod_poly_t FLINTmipo;
1132 fq_poly_t FLINTF, FLINTG;
1139 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1140 fmpz_mod_ctx_t fmpz_ctx;
1141 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1142 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
1144 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
1150 fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG,
fq_con);
1155 fmpz_clear (FLINTp);
1156 fq_poly_clear (FLINTF,
fq_con);
1157 fq_poly_clear (FLINTG,
fq_con);
1159 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1160 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1161 fmpz_mod_ctx_clear(fmpz_ctx);
1163 fmpz_mod_poly_clear (FLINTmipo);
1169 ZZ_pE::init (NTLmipo);
1172 div (NTLf, NTLf, NTLg);
1187 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
1188#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
1199#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1200 nmod_poly_t FLINTmipo;
1208 fq_nmod_poly_t FLINTF, FLINTG;
1212 fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG,
fq_con);
1222 zz_pE::init (NTLMipo);
1225 div (NTLF, NTLF, NTLG);
1232 nmod_poly_t FLINTF, FLINTG;
1235 nmod_poly_div (FLINTF, FLINTF, FLINTG);
1242 div (NTLF, NTLF, NTLG);
1258 result->length= d*(degAy + 1);
1259 flint_mpn_zero (
result->coeffs, d*(degAy+1));
1268 flint_mpn_copyi (
result->coeffs+
k,
buf->coeffs, nmod_poly_length(
buf));
1272 _nmod_poly_normalise (
result);
1275#if ( __FLINT_RELEASE >= 20400)
1278 const fq_nmod_ctx_t
fq_con)
1282 _fq_nmod_poly_set_length (
result, d*(degAy + 1),
fq_con);
1283 _fq_nmod_vec_zero (
result->coeffs, d*(degAy + 1),
fq_con);
1285 fq_nmod_poly_t
buf1;
1293 if (
i.coeff().inCoeffDomain())
1362 fmpz_poly_init2 (
result, d1*(degAy + 1));
1363 _fmpz_poly_set_length (
result, d1*(degAy + 1));
1371 if (
i.coeff().inCoeffDomain())
1375 _fmpz_vec_set (
result->coeffs +
k,
buf->coeffs,
buf->length);
1376 fmpz_poly_clear (
buf);
1380 for (
j=
i.coeff();
j.hasTerms();
j++)
1385 _fmpz_vec_set (
result->coeffs +
k,
buf->coeffs,
buf->length);
1386 fmpz_poly_clear (
buf);
1390 _fmpz_poly_normalise (
result);
1404 int k, kk,
j, bufRepLength;
1410 kk= (degAy -
i.exp())*d;
1411 bufRepLength= (int) nmod_poly_length (
buf);
1412 for (
j= 0;
j < bufRepLength;
j++)
1414 nmod_poly_set_coeff_ui (subA1,
j +
k,
1415 n_addmod (nmod_poly_get_coeff_ui (subA1,
j+
k),
1416 nmod_poly_get_coeff_ui (
buf,
j),
1420 nmod_poly_set_coeff_ui (subA2,
j + kk,
1421 n_addmod (nmod_poly_get_coeff_ui (subA2,
j + kk),
1422 nmod_poly_get_coeff_ui (
buf,
j),
1429 _nmod_poly_normalise (subA1);
1430 _nmod_poly_normalise (subA2);
1433#if ( __FLINT_RELEASE >= 20400)
1439 fq_nmod_poly_init2 (subA1, d*(degAy + 2),
fq_con);
1440 fq_nmod_poly_init2 (subA2, d*(degAy + 2),
fq_con);
1442 _fq_nmod_poly_set_length (subA1, d*(degAy + 2),
fq_con);
1443 _fq_nmod_vec_zero (subA1->coeffs, d*(degAy + 2),
fq_con);
1445 _fq_nmod_poly_set_length (subA2, d*(degAy + 2),
fq_con);
1446 _fq_nmod_vec_zero (subA2->coeffs, d*(degAy + 2),
fq_con);
1448 fq_nmod_poly_t
buf1;
1455 if (
i.coeff().inCoeffDomain())
1466 kk= (degAy -
i.exp())*d;
1467 _fq_nmod_vec_add (subA1->coeffs+
k, subA1->coeffs+
k,
buf1->coeffs,
1469 _fq_nmod_vec_add (subA2->coeffs+kk, subA2->coeffs+kk,
buf1->coeffs,
1474 _fq_nmod_poly_normalise (subA1,
fq_con);
1475 _fq_nmod_poly_normalise (subA2,
fq_con);
1484 fmpz_poly_init2 (subA1, d*(degAy + 2));
1485 fmpz_poly_init2 (subA2, d*(degAy + 2));
1495 kk= (degAy -
i.exp())*d;
1496 _fmpz_vec_add (subA1->coeffs+
k, subA1->coeffs +
k,
buf->coeffs,
buf->length);
1497 _fmpz_vec_add (subA2->coeffs+kk, subA2->coeffs + kk,
buf->coeffs,
buf->length);
1498 fmpz_poly_clear (
buf);
1501 _fmpz_poly_normalise (subA1);
1502 _fmpz_poly_normalise (subA2);
1513 int degf= fmpz_poly_degree(F);
1515 int degfSubK, repLength;
1522 repLength= degfSubK + 1;
1524 fmpz_poly_init2 (
buf, repLength);
1525 _fmpz_poly_set_length (
buf, repLength);
1526 _fmpz_vec_set (
buf->coeffs, F->coeffs+
k, repLength);
1527 _fmpz_poly_normalise (
buf);
1532 fmpz_poly_clear (
buf);
1612 const fmpq_poly_t
mipo)
1620 int degf= fmpz_poly_degree(F);
1630 repLength= degfSubK + 1;
1634 while (
j*d2 < repLength)
1636 fmpq_poly_init2 (
buf, d2);
1637 _fmpq_poly_set_length (
buf, d2);
1638 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k +
j*d2, d2);
1639 _fmpq_poly_normalise (
buf);
1643 fmpq_poly_clear (
buf);
1645 if (repLength -
j*d2 != 0 &&
j*d2 - repLength < d2)
1649 fmpq_poly_init2 (
buf, repLength);
1650 _fmpq_poly_set_length (
buf, repLength);
1652 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k +
j*d2, repLength);
1653 _fmpq_poly_normalise (
buf);
1656 fmpq_poly_clear (
buf);
1677 nmod_poly_set (
f, F);
1678 nmod_poly_set (
g,
G);
1679 int degf= nmod_poly_degree(
f);
1680 int degg= nmod_poly_degree(
g);
1685 if (nmod_poly_length (
f) < (
long) d*(
k+1))
1686 nmod_poly_fit_length (
f,(
long)d*(
k+1));
1692 int degfSubLf= degf;
1693 int deggSubLg=
degg-lg;
1694 int repLengthBuf2, repLengthBuf1, ind, tmp;
1695 while (degf >= lf || lg >= 0)
1699 else if (degfSubLf < 0)
1702 repLengthBuf1= degfSubLf + 1;
1705 for (ind= 0; ind < repLengthBuf1; ind++)
1706 nmod_poly_set_coeff_ui (
buf1, ind, nmod_poly_get_coeff_ui (
f, ind+lf));
1707 _nmod_poly_normalise (
buf1);
1709 repLengthBuf1= nmod_poly_length (
buf1);
1711 if (deggSubLg >= d - 1)
1712 repLengthBuf2= d - 1;
1713 else if (deggSubLg < 0)
1716 repLengthBuf2= deggSubLg + 1;
1719 for (ind= 0; ind < repLengthBuf2; ind++)
1720 nmod_poly_set_coeff_ui (
buf2, ind, nmod_poly_get_coeff_ui (
g, ind + lg));
1722 _nmod_poly_normalise (
buf2);
1723 repLengthBuf2= nmod_poly_length (
buf2);
1726 for (ind= 0; ind < repLengthBuf1; ind++)
1727 nmod_poly_set_coeff_ui (buf3, ind, nmod_poly_get_coeff_ui (
buf1, ind));
1728 for (ind= repLengthBuf1; ind < d; ind++)
1729 nmod_poly_set_coeff_ui (buf3, ind, 0);
1730 for (ind= 0; ind < repLengthBuf2; ind++)
1731 nmod_poly_set_coeff_ui (buf3, ind+d, nmod_poly_get_coeff_ui (
buf2, ind));
1732 _nmod_poly_normalise (buf3);
1739 degfSubLf= degf - lf;
1742 deggSubLg=
degg - lg;
1744 if (lg >= 0 && deggSubLg > 0)
1746 if (repLengthBuf2 > degfSubLf + 1)
1747 degfSubLf= repLengthBuf2 - 1;
1748 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1749 for (ind= 0; ind < tmp; ind++)
1750 nmod_poly_set_coeff_ui (
g, ind + lg,
1751 n_submod (nmod_poly_get_coeff_ui (
g, ind + lg),
1752 nmod_poly_get_coeff_ui (
buf1, ind),
1766 for (ind= 0; ind < repLengthBuf2; ind++)
1767 nmod_poly_set_coeff_ui (
f, ind + lf,
1768 n_submod (nmod_poly_get_coeff_ui (
f, ind + lf),
1769 nmod_poly_get_coeff_ui (
buf2, ind),
1785#if ( __FLINT_RELEASE >= 20400)
1793 fq_nmod_poly_t
f,
g;
1794 int degf= fq_nmod_poly_degree(F,
fq_con);
1801 fq_nmod_poly_set (
f, F,
fq_con);
1803 if (fq_nmod_poly_length (
f,
fq_con) < (
long) d*(
k + 1))
1804 fq_nmod_poly_fit_length (
f, (
long) d*(
k + 1),
fq_con);
1810 int degfSubLf= degf;
1811 int deggSubLg=
degg-lg;
1812 int repLengthBuf2, repLengthBuf1, tmp;
1813 while (degf >= lf || lg >= 0)
1817 else if (degfSubLf < 0)
1820 repLengthBuf1= degfSubLf + 1;
1821 fq_nmod_poly_init2 (
buf1, repLengthBuf1,
fq_con);
1822 _fq_nmod_poly_set_length (
buf1, repLengthBuf1,
fq_con);
1824 _fq_nmod_vec_set (
buf1->coeffs,
f->coeffs + lf, repLengthBuf1,
fq_con);
1827 repLengthBuf1= fq_nmod_poly_length (
buf1,
fq_con);
1829 if (deggSubLg >= d - 1)
1830 repLengthBuf2= d - 1;
1831 else if (deggSubLg < 0)
1834 repLengthBuf2= deggSubLg + 1;
1836 fq_nmod_poly_init2 (
buf2, repLengthBuf2,
fq_con);
1837 _fq_nmod_poly_set_length (
buf2, repLengthBuf2,
fq_con);
1838 _fq_nmod_vec_set (
buf2->coeffs,
g->coeffs + lg, repLengthBuf2,
fq_con);
1841 repLengthBuf2= fq_nmod_poly_length (
buf2,
fq_con);
1843 fq_nmod_poly_init2 (buf3, repLengthBuf2 + d,
fq_con);
1844 _fq_nmod_poly_set_length (buf3, repLengthBuf2 + d,
fq_con);
1845 _fq_nmod_vec_set (buf3->coeffs,
buf1->coeffs, repLengthBuf1,
fq_con);
1846 _fq_nmod_vec_set (buf3->coeffs + d,
buf2->coeffs, repLengthBuf2,
fq_con);
1848 _fq_nmod_poly_normalise (buf3,
fq_con);
1855 degfSubLf= degf - lf;
1858 deggSubLg=
degg - lg;
1860 if (lg >= 0 && deggSubLg > 0)
1862 if (repLengthBuf2 > degfSubLf + 1)
1863 degfSubLf= repLengthBuf2 - 1;
1864 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1865 _fq_nmod_vec_sub (
g->coeffs + lg,
g->coeffs + lg,
buf1->
coeffs,
1876 _fq_nmod_vec_sub (
f->coeffs + lf,
f->coeffs + lf,
buf2->coeffs,
1899 fmpz_poly_set (
f, F);
1900 fmpz_poly_set (
g,
G);
1901 int degf= fmpz_poly_degree(
f);
1902 int degg= fmpz_poly_degree(
g);
1906 if (fmpz_poly_length (
f) < (
long) d*(
k+1))
1907 fmpz_poly_fit_length (
f,(
long)d*(
k+1));
1913 int degfSubLf= degf;
1914 int deggSubLg=
degg-lg;
1915 int repLengthBuf2, repLengthBuf1, ind, tmp;
1917 while (degf >= lf || lg >= 0)
1921 else if (degfSubLf < 0)
1924 repLengthBuf1= degfSubLf + 1;
1926 fmpz_poly_init2 (
buf1, repLengthBuf1);
1928 for (ind= 0; ind < repLengthBuf1; ind++)
1930 fmpz_poly_get_coeff_fmpz (
tmp1,
f, ind + lf);
1931 fmpz_poly_set_coeff_fmpz (
buf1, ind,
tmp1);
1933 _fmpz_poly_normalise (
buf1);
1935 repLengthBuf1= fmpz_poly_length (
buf1);
1937 if (deggSubLg >= d - 1)
1938 repLengthBuf2= d - 1;
1939 else if (deggSubLg < 0)
1942 repLengthBuf2= deggSubLg + 1;
1944 fmpz_poly_init2 (
buf2, repLengthBuf2);
1946 for (ind= 0; ind < repLengthBuf2; ind++)
1948 fmpz_poly_get_coeff_fmpz (
tmp1,
g, ind + lg);
1949 fmpz_poly_set_coeff_fmpz (
buf2, ind,
tmp1);
1952 _fmpz_poly_normalise (
buf2);
1953 repLengthBuf2= fmpz_poly_length (
buf2);
1955 fmpz_poly_init2 (buf3, repLengthBuf2 + d);
1956 for (ind= 0; ind < repLengthBuf1; ind++)
1958 fmpz_poly_get_coeff_fmpz (
tmp1,
buf1, ind);
1959 fmpz_poly_set_coeff_fmpz (buf3, ind,
tmp1);
1961 for (ind= repLengthBuf1; ind < d; ind++)
1962 fmpz_poly_set_coeff_ui (buf3, ind, 0);
1963 for (ind= 0; ind < repLengthBuf2; ind++)
1965 fmpz_poly_get_coeff_fmpz (
tmp1,
buf2, ind);
1966 fmpz_poly_set_coeff_fmpz (buf3, ind + d,
tmp1);
1968 _fmpz_poly_normalise (buf3);
1975 degfSubLf= degf - lf;
1978 deggSubLg=
degg - lg;
1980 if (lg >= 0 && deggSubLg > 0)
1982 if (repLengthBuf2 > degfSubLf + 1)
1983 degfSubLf= repLengthBuf2 - 1;
1984 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1985 for (ind= 0; ind < tmp; ind++)
1987 fmpz_poly_get_coeff_fmpz (
tmp1,
g, ind + lg);
1988 fmpz_poly_get_coeff_fmpz (
tmp2,
buf1, ind);
1990 fmpz_poly_set_coeff_fmpz (
g, ind + lg,
tmp1);
1995 fmpz_poly_clear (
buf1);
1996 fmpz_poly_clear (
buf2);
1997 fmpz_poly_clear (buf3);
2002 for (ind= 0; ind < repLengthBuf2; ind++)
2004 fmpz_poly_get_coeff_fmpz (
tmp1,
f, ind + lf);
2005 fmpz_poly_get_coeff_fmpz (
tmp2,
buf2, ind);
2007 fmpz_poly_set_coeff_fmpz (
f, ind + lf,
tmp1);
2010 fmpz_poly_clear (
buf1);
2011 fmpz_poly_clear (
buf2);
2012 fmpz_poly_clear (buf3);
2015 fmpz_poly_clear (
f);
2016 fmpz_poly_clear (
g);
2023#if ( __FLINT_RELEASE >= 20400)
2026 const fq_nmod_ctx_t
fq_con)
2034 int degf= fq_nmod_poly_degree(F,
fq_con);
2036 int degfSubK, repLength;
2043 repLength= degfSubK + 1;
2045 fq_nmod_poly_init2 (
buf, repLength,
fq_con);
2046 _fq_nmod_poly_set_length (
buf, repLength,
fq_con);
2047 _fq_nmod_vec_set (
buf->coeffs, F->coeffs+
k, repLength,
fq_con);
2070 int degf= nmod_poly_degree(F);
2072 int degfSubK, repLength,
j;
2079 repLength= degfSubK + 1;
2082 for (
j= 0;
j < repLength;
j++)
2083 nmod_poly_set_coeff_ui (
buf,
j, nmod_poly_get_coeff_ui (F,
j +
k));
2084 _nmod_poly_normalise (
buf);
2110 nmod_poly_mullow (
F1,
F1, G1, (
long)
k);
2117 int b= nmod_poly_degree (
F2) + nmod_poly_degree (G2) -
k - degtailF - degtailG
2118 + d1*(2+taildegF + taildegG);
2119 nmod_poly_mulhigh (
F2,
F2, G2,
b);
2120 nmod_poly_shift_right (
F2,
F2,
b);
2121 int d2=
tmax (nmod_poly_degree (
F2)/d1, nmod_poly_degree (
F1)/d1);
2144 int d1= degAx + 1 + degBx;
2145 int d2=
tmax (degAy, degBy);
2147 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2150 nmod_poly_t FLINTA, FLINTB;
2155 nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k);
2164#if ( __FLINT_RELEASE >= 20400)
2168 const fq_nmod_ctx_t
fq_con)
2174 fq_nmod_poly_t
F1,
F2;
2177 fq_nmod_poly_t G1, G2;
2181 fq_nmod_poly_mullow (
F1,
F1, G1, (
long)
k,
fq_con);
2188 int b=
k + degtailF + degtailG - d1*(2+taildegF + taildegG);
2191 fq_nmod_poly_reverse (G2, G2, fq_nmod_poly_length (G2,
fq_con),
fq_con);
2196 fq_nmod_poly_degree (
F1,
fq_con)/d1);
2210 const fq_nmod_ctx_t
fq_con)
2219 int d1= degAx + 1 + degBx;
2220 int d2=
tmax (degAy, degBy);
2222 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2225 fq_nmod_poly_t FLINTA, FLINTB;
2230 fq_nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k,
fq_con);
2255 fmpz_poly_mullow (
F1,
F1, G1, (
long)
k);
2262 int b= fmpz_poly_degree (
F2) + fmpz_poly_degree (G2) -
k - degtailF - degtailG
2263 + d1*(2+taildegF + taildegG);
2264 fmpz_poly_mulhigh_n (
F2,
F2, G2,
b);
2265 fmpz_poly_shift_right (
F2,
F2,
b);
2266 int d2=
tmax (fmpz_poly_degree (
F2)/d1, fmpz_poly_degree (
F1)/d1);
2270 fmpz_poly_clear (
F1);
2271 fmpz_poly_clear (
F2);
2272 fmpz_poly_clear (G1);
2273 fmpz_poly_clear (G2);
2286 int d1= degAx + 1 + degBx;
2293 fmpz_poly_t FLINTA, FLINTB;
2298 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k);
2300 fmpz_poly_clear (FLINTA);
2301 fmpz_poly_clear (FLINTB);
2346 int degFx=
degree (F, 1);
2347 int degFa=
degree (F, a);
2351 int d2= degFa+degGa+1;
2352 int d1= degFx + 1 + degGx;
2360 fmpz_poly_t FLINTF, FLINTG;
2364 fmpz_poly_mullow (FLINTF, FLINTF, FLINTG, d1*
degree (
M));
2369 fmpz_poly_clear (FLINTF);
2370 fmpz_poly_clear (FLINTG);
2381 result.rep.SetLength (d*(degAy + 1));
2384 resultp=
result.rep.elts();
2387 int j,
k, bufRepLength;
2391 if (
i.coeff().inCoeffDomain())
2397 bufp=
buf.rep.elts();
2398 bufRepLength= (int)
buf.rep.length();
2399 for (
j= 0;
j < bufRepLength;
j++)
2400 resultp [
j +
k]= bufp [
j];
2408#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2413 result.rep.SetLength (d*(degAy + 1));
2417 resultp=
result.rep.elts();
2422 int j,
k, buf1RepLength;
2426 if (
i.coeff().inCoeffDomain())
2435 buf1p=
buf1.rep.elts();
2436 buf1RepLength= (int)
buf1.rep.length();
2437 for (
j= 0;
j < buf1RepLength;
j++)
2438 resultp [
j +
k]= buf1p [
j];
2450 subA1.rep.SetLength ((
long) d*(degAy + 2));
2451 subA2.rep.SetLength ((
long) d*(degAy + 2));
2456 subA1p= subA1.rep.elts();
2457 subA2p= subA2.rep.elts();
2462 int j,
k, kk, bufRepLength;
2466 if (
i.coeff().inCoeffDomain())
2469 buf= to_zz_pEX (to_zz_pE (
buf2));
2475 kk= (degAy -
i.exp())*d;
2476 bufp=
buf.rep.elts();
2477 bufRepLength= (int)
buf.rep.length();
2478 for (
j= 0;
j < bufRepLength;
j++)
2480 subA1p [
j +
k] += bufp [
j];
2481 subA2p [
j + kk] += bufp [
j];
2494 subA1.rep.SetLength ((
long) d*(degAy + 2));
2495 subA2.rep.SetLength ((
long) d*(degAy + 2));
2499 subA1p= subA1.rep.elts();
2500 subA2p= subA2.rep.elts();
2503 int j,
k, kk, bufRepLength;
2510 kk= (degAy -
i.exp())*d;
2511 bufp=
buf.rep.elts();
2512 bufRepLength= (int)
buf.rep.length();
2513 for (
j= 0;
j < bufRepLength;
j++)
2515 subA1p [
j +
k] += bufp [
j];
2516 subA2p [
j + kk] += bufp [
j];
2524#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2544 if (
f.rep.length() < (
long) d*(
k+1))
2545 f.rep.SetLength ((
long)d*(
k+1));
2547 zz_pE *
gp=
g.rep.elts();
2548 zz_pE *
fp=
f.rep.elts();
2553 int degfSubLf= degf;
2554 int deggSubLg=
degg-lg;
2555 int repLengthBuf2, repLengthBuf1, ind, tmp;
2556 zz_pE zzpEZero= zz_pE();
2558 while (degf >= lf || lg >= 0)
2562 else if (degfSubLf < 0)
2565 repLengthBuf1= degfSubLf + 1;
2566 buf1.rep.SetLength((
long) repLengthBuf1);
2568 buf1p=
buf1.rep.elts();
2569 for (ind= 0; ind < repLengthBuf1; ind++)
2570 buf1p [ind]=
fp [ind + lf];
2573 repLengthBuf1=
buf1.rep.length();
2575 if (deggSubLg >= d - 1)
2576 repLengthBuf2= d - 1;
2577 else if (deggSubLg < 0)
2580 repLengthBuf2= deggSubLg + 1;
2582 buf2.rep.SetLength ((
long) repLengthBuf2);
2583 buf2p=
buf2.rep.elts();
2584 for (ind= 0; ind < repLengthBuf2; ind++)
2585 buf2p [ind]=
gp [ind + lg];
2588 repLengthBuf2=
buf2.rep.length();
2590 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2591 buf3p= buf3.rep.elts();
2592 buf2p=
buf2.rep.elts();
2593 buf1p=
buf1.rep.elts();
2594 for (ind= 0; ind < repLengthBuf1; ind++)
2595 buf3p [ind]= buf1p [ind];
2596 for (ind= repLengthBuf1; ind < d; ind++)
2597 buf3p [ind]= zzpEZero;
2598 for (ind= 0; ind < repLengthBuf2; ind++)
2599 buf3p [ind + d]= buf2p [ind];
2607 degfSubLf= degf - lf;
2610 deggSubLg=
degg - lg;
2612 buf1p=
buf1.rep.elts();
2614 if (lg >= 0 && deggSubLg > 0)
2616 if (repLengthBuf2 > degfSubLf + 1)
2617 degfSubLf= repLengthBuf2 - 1;
2618 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2619 for (ind= 0; ind < tmp; ind++)
2620 gp [ind + lg] -= buf1p [ind];
2626 buf2p=
buf2.rep.elts();
2629 for (ind= 0; ind < repLengthBuf2; ind++)
2630 fp [ind + lf] -= buf2p [ind];
2658 if (
f.rep.length() < (
long) d*(
k+1))
2659 f.rep.SetLength ((
long)d*(
k+1));
2661 zz_p *
gp=
g.rep.elts();
2662 zz_p *
fp=
f.rep.elts();
2667 int degfSubLf= degf;
2668 int deggSubLg=
degg-lg;
2669 int repLengthBuf2, repLengthBuf1, ind, tmp;
2670 zz_p zzpZero= zz_p();
2671 while (degf >= lf || lg >= 0)
2675 else if (degfSubLf < 0)
2678 repLengthBuf1= degfSubLf + 1;
2679 buf1.rep.SetLength((
long) repLengthBuf1);
2681 buf1p=
buf1.rep.elts();
2682 for (ind= 0; ind < repLengthBuf1; ind++)
2683 buf1p [ind]=
fp [ind + lf];
2686 repLengthBuf1=
buf1.rep.length();
2688 if (deggSubLg >= d - 1)
2689 repLengthBuf2= d - 1;
2690 else if (deggSubLg < 0)
2693 repLengthBuf2= deggSubLg + 1;
2695 buf2.rep.SetLength ((
long) repLengthBuf2);
2696 buf2p=
buf2.rep.elts();
2697 for (ind= 0; ind < repLengthBuf2; ind++)
2698 buf2p [ind]=
gp [ind + lg];
2702 repLengthBuf2=
buf2.rep.length();
2705 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2706 buf3p= buf3.rep.elts();
2707 buf2p=
buf2.rep.elts();
2708 buf1p=
buf1.rep.elts();
2709 for (ind= 0; ind < repLengthBuf1; ind++)
2710 buf3p [ind]= buf1p [ind];
2711 for (ind= repLengthBuf1; ind < d; ind++)
2712 buf3p [ind]= zzpZero;
2713 for (ind= 0; ind < repLengthBuf2; ind++)
2714 buf3p [ind + d]= buf2p [ind];
2722 degfSubLf= degf - lf;
2725 deggSubLg=
degg - lg;
2727 buf1p=
buf1.rep.elts();
2729 if (lg >= 0 && deggSubLg > 0)
2731 if (repLengthBuf2 > degfSubLf + 1)
2732 degfSubLf= repLengthBuf2 - 1;
2733 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2734 for (ind= 0; ind < tmp; ind++)
2735 gp [ind + lg] -= buf1p [ind];
2740 buf2p=
buf2.rep.elts();
2743 for (ind= 0; ind < repLengthBuf2; ind++)
2744 fp [ind + lf] -= buf2p [ind];
2752#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2759 zz_pE *
fp=
f.rep.elts();
2767 int degfSubK, repLength,
j;
2774 repLength= degfSubK + 1;
2776 buf.rep.SetLength ((
long) repLength);
2777 bufp=
buf.rep.elts();
2778 for (
j= 0;
j < repLength;
j++)
2779 bufp [
j]=
fp [
j +
k];
2798 zz_p *
fp=
f.rep.elts();
2806 int degfSubK, repLength,
j;
2813 repLength= degfSubK + 1;
2815 buf.rep.SetLength ((
long) repLength);
2816 bufp=
buf.rep.elts();
2817 for (
j= 0;
j < repLength;
j++)
2818 bufp [
j]=
fp [
j +
k];
2844 MulTrunc (
F1,
F1, G1, (
long)
k);
2850 int b=
k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2854 MulTrunc (
F2,
F2, G2,
b + 1);
2857 int d2=
tmax (deg (
F2)/d1, deg (
F1)/d1);
2873 int d1= degAx + 1 + degBx;
2874 int d2=
tmax (degAy, degBy);
2876 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2877 return mulMod2NTLFpReci (
A,
B,
M);
2883 MulTrunc (NTLA, NTLA, NTLB, (
long)
k);
2891#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2907 MulTrunc (
F1,
F1, G1, (
long)
k);
2913 int b=
k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2917 MulTrunc (
F2,
F2, G2,
b + 1);
2920 int d2=
tmax (deg (
F2)/d1, deg (
F1)/d1);
2941#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
2942 nmod_poly_t FLINTmipo;
2956 int d1= degAx + degBx + 1;
2957 int d2=
tmax (degAy, degBy);
2964 zz_pE::init (NTLMipo);
2967 if ((d1 > 128/degMipo) && (d2 > 160/degMipo) && (degAy == degBy) &&
2969 return mulMod2NTLFqReci (
A,
B,
M,
alpha);
2976 MulTrunc (NTLA, NTLA, NTLB, (
long)
k);
2986 A= mulMod2NTLFp (
A,
B,
M);
2995 if (
A.isZero() ||
B.isZero())
2998 ASSERT (
M.isUnivariate(),
"M must be univariate");
3004 if (
G.inCoeffDomain())
3011 if ((degF < 1 && degG < 1) && (F.
isUnivariate() &&
G.isUnivariate()) &&
3012 (F.
level() ==
G.level()))
3017 else if (degF <= 1 && degG <= 1)
3023 int sizeF=
size (F);
3024 int sizeG=
size (
G);
3026 int fallBackToNaive= 50;
3027 if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
3030 return mod (
G*F,
M);
3032 return mod (F*
G,
M);
3041 (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
3044 int m= (int) ceil (
degree (
M)/2.0);
3045 if (degF >=
m || degG >=
m)
3056 return F0G0 + MLo*(F0G1 + F1G0);
3060 m= (int) ceil (
tmax (degF, degG)/2.0);
3069 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3071 DEBOUTLN (cerr,
"fatal end in mulMod2");
3089 if (
A.isZero() ||
B.isZero())
3100 if (
G.inCoeffDomain())
3103 int sizeF=
size (F);
3104 int sizeG=
size (
G);
3106 if (sizeF / MOD.
length() < 100 || sizeG / MOD.
length() < 100)
3109 return mod (
G*F, MOD);
3111 return mod (F*
G, MOD);
3118 if ((degF <= 1 && F.
level() <=
M.level()) &&
3119 (degG <= 1 &&
G.level() <=
M.level()))
3123 if (degF == 1 && degG == 1)
3134 return H11*
y*
y + (H01 - H00 - H11)*
y + H00;
3146 else if (degF == 1 && degG == 0)
3148 else if (degF == 0 && degG == 1)
3153 int m= (int) ceil (
degree (
M)/2.0);
3154 if (degF >=
m || degG >=
m)
3168 return F0G0 + MLo*(F0G1 + F1G0);
3172 m= (
tmax(degF, degG)+1)/2;
3181 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3183 DEBOUTLN (cerr,
"fatal end in mulMod");
3203 for (
int j= 1;
j <=
l;
j++,
i++)
3204 tmp1.append (
i.getItem());
3217 else if (L.
length() == 1)
3219 else if (L.
length() == 2)
3227 for (
int j= 1;
j <=
l;
j++,
i++)
3228 tmp1.append (
i.getItem());
3252 while (d -
i.exp() < 0)
3255 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
3270 ASSERT (!
g.isZero(),
"expected a unit");
3286 for (
int i= 1;
i <=
l;
i++)
3355#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3356 nmod_poly_t FLINTmipo;
3365 fq_nmod_poly_t FLINTA, FLINTB;
3369 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB,
fq_con);
3378 bool zz_pEbak= zz_pE::initialized();
3386 div (NTLA, NTLA, NTLB);
3438#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3439 nmod_poly_t FLINTmipo;
3447 fq_nmod_poly_t FLINTA, FLINTB;
3451 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB,
fq_con);
3466 DivRem (NTLQ, NTLR, NTLA, NTLB);
3482 else if (
x.level() !=
A.level())
3488 int j= (int) floor ((
double)
degree (
A)/
m);
3493 while (
i.hasTerms() &&
i.exp() -
j*
m >= 0)
3536 int m= (int) ceil ((
double) (degB + 1)/2.0) + 1;
3537 ASSERT (4*
m >= degA,
"expected degree (F, 1) < 2*degree (G, 1)");
3539 if (splitA.
length() == 3)
3541 if (splitA.
length() == 2)
3546 if (splitA.
length() == 1)
3568 if (splitR.
length() == 1)
3607 int m= (int) ceil ((
double) (degB + 1)/ 2.0);
3608 ASSERT (3*
m > degA,
"expected degree (F, 1) < 3*degree (G, 1)");
3612 if (splitA.
length() == 2)
3616 if (splitA.
length() == 1)
3646 Q +=
LC (
R,
x)*xToM;
3661 if (
B.inCoeffDomain())
3666 if (
A.inCoeffDomain() && !
B.inCoeffDomain())
3673 if (
B.level() <
A.level())
3678 if (
A.level() >
B.level())
3684 if (
B.level() == 1 &&
B.isUnivariate())
3705 H=
i.getItem()*xToDegB;
3715 H=
R*xToDegB +
i.getItem();
3749 H=
i.getItem()*xToDegB;
3757 H=
R*xToDegB +
i.getItem();
3774 if (
A.inCoeffDomain() ||
B.inCoeffDomain())
3776 if (
A.inCoeffDomain())
3783#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
3793#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3794 nmod_poly_t FLINTmipo;
3802 fq_nmod_poly_t FLINTA, FLINTB;
3805 int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA,
fq_con);
3813 zz_pE::init (NTLMipo);
3816 return divide (NTLB, NTLA);
3820 nmod_poly_t FLINTA, FLINTB;
3823 nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3824 bool result= nmod_poly_is_zero (FLINTA);
3831 return divide (NTLB, NTLA);
3841 fmpq_poly_t FLINTA,FLINTB;
3844 fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3845 bool result= fmpq_poly_is_zero (FLINTA);
3846 fmpq_poly_clear (FLINTA);
3847 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.
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
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)