34#include <NTL/lzz_pEX.h>
40#include "flint/fq_nmod_vec.h"
41#if __FLINT_RELEASE >= 20503
42#include "flint/fmpz_mod.h"
47#if defined(HAVE_NTL) || defined(HAVE_FLINT)
53 fmpz_poly_init2 (
result, d*(degAy + 1));
54 _fmpz_poly_set_length (
result, d*(degAy + 1));
58 if (
i.coeff().inBaseDomain())
61 for (
j=
i.coeff();
j.hasTerms();
j++)
65 _fmpz_poly_normalise(
result);
75 int degf= fmpz_poly_degree (F);
88 repLength= degfSubK + 1;
90 fmpq_poly_init2 (
buf, repLength);
91 _fmpq_poly_set_length (
buf, repLength);
92 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k, repLength);
93 _fmpq_poly_normalise (
buf);
97 fmpq_poly_clear (
buf);
101 fmpq_poly_clear (
mipo);
120 int d= degAa + 1 + degBa;
122 fmpz_poly_t FLINTA,FLINTB;
126 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
131 fmpz_poly_clear (FLINTA);
132 fmpz_poly_clear (FLINTB);
147 fmpz_poly_t FLINTA,FLINTB;
150 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
154 fmpz_poly_clear (FLINTA);
155 fmpz_poly_clear (FLINTB);
183 fmpq_poly_t FLINTA,FLINTB;
187 fmpq_poly_div (FLINTA, FLINTA, FLINTB);
190 fmpq_poly_clear (FLINTA);
191 fmpq_poly_clear (FLINTB);
201 fmpq_poly_t FLINTA,FLINTB;
205 fmpq_poly_rem (FLINTA, FLINTA, FLINTB);
208 fmpq_poly_clear (FLINTA);
209 fmpq_poly_clear (FLINTB);
228 int d= degAa + 1 + degBa;
230 fmpz_poly_t FLINTA,FLINTB;
235 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB,
k);
239 fmpz_poly_clear (FLINTA);
240 fmpz_poly_clear (FLINTB);
251 if (
G.inCoeffDomain())
265 fmpz_poly_t FLINTA,FLINTB;
268 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB,
m);
272 fmpz_poly_clear (FLINTA);
273 fmpz_poly_clear (FLINTB);
286 while (d -
i.exp() < 0)
289 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
306 ASSERT (F.
mvar() ==
x,
"main variable of F and x differ");
307 ASSERT (!
g.isZero(),
"expected a unit");
320 for (
int i= 1;
i <=
l;
i++)
353 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
386 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
434#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
436 fmpz_mod_poly_t FLINTmipo;
438 fq_poly_t FLINTF, FLINTG;
446 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
447 fmpz_mod_ctx_t fmpz_ctx;
448 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
449 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
451 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
457 fq_poly_mul (FLINTF, FLINTF, FLINTG,
fq_con);
463 fq_poly_clear (FLINTF,
fq_con);
464 fq_poly_clear (FLINTG,
fq_con);
466 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
467 fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
468 fmpz_mod_ctx_clear(fmpz_ctx);
470 fmpz_mod_poly_clear(FLINTmipo);
480 mul (NTLf, NTLf, NTLg);
500 fmpz_mod_poly_t FLINTF, FLINTG;
503 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
504 fmpz_mod_ctx_t fmpz_ctx;
505 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
506 fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG, fmpz_ctx);
508 fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
511 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
512 fmpz_mod_poly_clear (FLINTG,fmpz_ctx);
513 fmpz_mod_poly_clear (FLINTF,fmpz_ctx);
514 fmpz_mod_ctx_clear(fmpz_ctx);
516 fmpz_mod_poly_clear (FLINTG);
517 fmpz_mod_poly_clear (FLINTF);
519 fmpz_clear (FLINTpk);
530 ZZ_pX NTLf= to_ZZ_pX (ZZf);
531 ZZ_pX NTLg= to_ZZ_pX (ZZg);
532 mul (NTLf, NTLf, NTLg);
544#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
546 fmpz_mod_poly_t FLINTmipo;
560 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
561 fmpz_mod_ctx_t fmpz_ctx;
562 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
563 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
565 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
577 fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF,
fq_con);
580 fmpz_poly_clear (FLINTF);
581 fq_poly_clear (FLINTG,
fq_con);
591 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG,
fq_con);
594 fmpz_poly_clear (FLINTG);
595 fq_poly_clear (FLINTF,
fq_con);
604 fq_mul (FLINTF, FLINTF, FLINTG,
fq_con);
607 fq_clear (FLINTF,
fq_con);
608 fq_clear (FLINTG,
fq_con);
612 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
613 fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
614 fmpz_mod_ctx_clear(fmpz_ctx);
616 fmpz_mod_poly_clear (FLINTmipo);
631 mul (NTLg, to_ZZ_pE (NTLf), NTLg);
638 mul (NTLf, NTLf, to_ZZ_pE (NTLg));
646 mul (
result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
659 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
661#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
680#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
681 nmod_poly_t FLINTmipo;
689 fq_nmod_poly_t FLINTF, FLINTG;
693 fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG,
fq_con);
702#elif defined(AHVE_NTL)
707 mul (NTLF, NTLF, NTLG);
715 nmod_poly_t FLINTF, FLINTG;
718 nmod_poly_mul (FLINTF, FLINTF, FLINTG);
727 mul (NTLF, NTLF, NTLG);
769 fmpz_mod_poly_t FLINTF, FLINTG;
772 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
773 fmpz_mod_ctx_t fmpz_ctx;
774 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
775 fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG, fmpz_ctx);
777 fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
780 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
781 fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
782 fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
783 fmpz_mod_ctx_clear(fmpz_ctx);
785 fmpz_mod_poly_clear (FLINTG);
786 fmpz_mod_poly_clear (FLINTF);
788 fmpz_clear (FLINTpk);
798 ZZ_pX NTLf= to_ZZ_pX (ZZf);
799 ZZ_pX NTLg= to_ZZ_pX (ZZg);
800 rem (NTLf, NTLf, NTLg);
810#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
812 fmpz_mod_poly_t FLINTmipo;
814 fq_poly_t FLINTF, FLINTG;
828 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
829 fmpz_mod_ctx_t fmpz_ctx;
830 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
831 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
833 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
839 fq_poly_rem (FLINTF, FLINTF, FLINTG,
fq_con);
845 fq_poly_clear (FLINTF,
fq_con);
846 fq_poly_clear (FLINTG,
fq_con);
848 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
849 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
850 fmpz_mod_ctx_clear(fmpz_ctx);
852 fmpz_mod_poly_clear (FLINTmipo);
862 rem (NTLf, NTLf, NTLg);
877 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
878#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
889#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
890 nmod_poly_t FLINTmipo;
898 fq_nmod_poly_t FLINTF, FLINTG;
902 fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG,
fq_con);
915 rem (NTLF, NTLF, NTLG);
922 nmod_poly_t FLINTF, FLINTG;
925 nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
932 rem (NTLF, NTLF, NTLG);
957#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
959 fmpz_mod_poly_t FLINTmipo;
968 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
969 fmpz_mod_ctx_t fmpz_ctx;
970 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
971 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
973 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
979 fq_inv (FLINTG, FLINTG,
fq_con);
980 fq_mul (FLINTF, FLINTF, FLINTG,
fq_con);
985 fq_clear (FLINTF,
fq_con);
986 fq_clear (FLINTG,
fq_con);
988 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
989 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
990 fmpz_mod_ctx_clear(fmpz_ctx);
992 fmpz_mod_poly_clear (FLINTmipo);
1002 div (
result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
1006 return b(
div (F,
G));
1014 if (!
G.inBaseDomain())
1018#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1020 fmpz_mod_poly_t FLINTmipo;
1030 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1031 fmpz_mod_ctx_t fmpz_ctx;
1032 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1033 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
1035 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
1041 fq_inv (FLINTG, FLINTG,
fq_con);
1042 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG,
fq_con);
1047 fmpz_clear (FLINTp);
1048 fq_poly_clear (FLINTF,
fq_con);
1049 fq_clear (FLINTG,
fq_con);
1051 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1052 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1053 fmpz_mod_ctx_clear(fmpz_ctx);
1055 fmpz_mod_poly_clear (FLINTmipo);
1064 div (NTLf, NTLf, to_ZZ_pE (NTLg));
1068 return b(
div (F,
G));
1083 fmpz_init (FLINTpk);
1085 fmpz_mod_poly_t FLINTF, FLINTG;
1088 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1089 fmpz_mod_ctx_t fmpz_ctx;
1090 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
1091 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fmpz_ctx);
1093 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
1096 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1097 fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
1098 fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
1099 fmpz_mod_ctx_clear(fmpz_ctx);
1101 fmpz_mod_poly_clear (FLINTG);
1102 fmpz_mod_poly_clear (FLINTF);
1104 fmpz_clear (FLINTpk);
1114 ZZ_pX NTLf= to_ZZ_pX (ZZf);
1115 ZZ_pX NTLg= to_ZZ_pX (ZZg);
1116 div (NTLf, NTLf, NTLg);
1126#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1128 fmpz_mod_poly_t FLINTmipo;
1130 fq_poly_t FLINTF, FLINTG;
1137 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1138 fmpz_mod_ctx_t fmpz_ctx;
1139 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1140 fq_ctx_init_modulus (
fq_con, FLINTmipo, fmpz_ctx,
"Z");
1142 fq_ctx_init_modulus (
fq_con, FLINTmipo,
"Z");
1148 fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG,
fq_con);
1153 fmpz_clear (FLINTp);
1154 fq_poly_clear (FLINTF,
fq_con);
1155 fq_poly_clear (FLINTG,
fq_con);
1157 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1158 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1159 fmpz_mod_ctx_clear(fmpz_ctx);
1161 fmpz_mod_poly_clear (FLINTmipo);
1170 div (NTLf, NTLf, NTLg);
1185 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
1186#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
1197#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1198 nmod_poly_t FLINTmipo;
1206 fq_nmod_poly_t FLINTF, FLINTG;
1210 fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG,
fq_con);
1223 div (NTLF, NTLF, NTLG);
1230 nmod_poly_t FLINTF, FLINTG;
1233 nmod_poly_div (FLINTF, FLINTF, FLINTG);
1240 div (NTLF, NTLF, NTLG);
1256 result->length= d*(degAy + 1);
1257 flint_mpn_zero (
result->coeffs, d*(degAy+1));
1266 flint_mpn_copyi (
result->coeffs+
k,
buf->coeffs, nmod_poly_length(
buf));
1270 _nmod_poly_normalise (
result);
1273#if ( __FLINT_RELEASE >= 20400)
1276 const fq_nmod_ctx_t
fq_con)
1280 _fq_nmod_poly_set_length (
result, d*(degAy + 1),
fq_con);
1281 _fq_nmod_vec_zero (
result->coeffs, d*(degAy + 1),
fq_con);
1283 fq_nmod_poly_t
buf1;
1291 if (
i.coeff().inCoeffDomain())
1360 fmpz_poly_init2 (
result, d1*(degAy + 1));
1361 _fmpz_poly_set_length (
result, d1*(degAy + 1));
1369 if (
i.coeff().inCoeffDomain())
1373 _fmpz_vec_set (
result->coeffs +
k,
buf->coeffs,
buf->length);
1374 fmpz_poly_clear (
buf);
1378 for (
j=
i.coeff();
j.hasTerms();
j++)
1383 _fmpz_vec_set (
result->coeffs +
k,
buf->coeffs,
buf->length);
1384 fmpz_poly_clear (
buf);
1388 _fmpz_poly_normalise (
result);
1402 int k, kk,
j, bufRepLength;
1408 kk= (degAy -
i.exp())*d;
1409 bufRepLength= (int) nmod_poly_length (
buf);
1410 for (
j= 0;
j < bufRepLength;
j++)
1412 nmod_poly_set_coeff_ui (subA1,
j +
k,
1413 n_addmod (nmod_poly_get_coeff_ui (subA1,
j+
k),
1414 nmod_poly_get_coeff_ui (
buf,
j),
1418 nmod_poly_set_coeff_ui (subA2,
j + kk,
1419 n_addmod (nmod_poly_get_coeff_ui (subA2,
j + kk),
1420 nmod_poly_get_coeff_ui (
buf,
j),
1427 _nmod_poly_normalise (subA1);
1428 _nmod_poly_normalise (subA2);
1431#if ( __FLINT_RELEASE >= 20400)
1437 fq_nmod_poly_init2 (subA1, d*(degAy + 2),
fq_con);
1438 fq_nmod_poly_init2 (subA2, d*(degAy + 2),
fq_con);
1440 _fq_nmod_poly_set_length (subA1, d*(degAy + 2),
fq_con);
1441 _fq_nmod_vec_zero (subA1->coeffs, d*(degAy + 2),
fq_con);
1443 _fq_nmod_poly_set_length (subA2, d*(degAy + 2),
fq_con);
1444 _fq_nmod_vec_zero (subA2->coeffs, d*(degAy + 2),
fq_con);
1446 fq_nmod_poly_t
buf1;
1453 if (
i.coeff().inCoeffDomain())
1464 kk= (degAy -
i.exp())*d;
1465 _fq_nmod_vec_add (subA1->coeffs+
k, subA1->coeffs+
k,
buf1->coeffs,
1467 _fq_nmod_vec_add (subA2->coeffs+kk, subA2->coeffs+kk,
buf1->coeffs,
1472 _fq_nmod_poly_normalise (subA1,
fq_con);
1473 _fq_nmod_poly_normalise (subA2,
fq_con);
1482 fmpz_poly_init2 (subA1, d*(degAy + 2));
1483 fmpz_poly_init2 (subA2, d*(degAy + 2));
1493 kk= (degAy -
i.exp())*d;
1494 _fmpz_vec_add (subA1->coeffs+
k, subA1->coeffs +
k,
buf->coeffs,
buf->length);
1495 _fmpz_vec_add (subA2->coeffs+kk, subA2->coeffs + kk,
buf->coeffs,
buf->length);
1496 fmpz_poly_clear (
buf);
1499 _fmpz_poly_normalise (subA1);
1500 _fmpz_poly_normalise (subA2);
1511 int degf= fmpz_poly_degree(F);
1513 int degfSubK, repLength;
1520 repLength= degfSubK + 1;
1522 fmpz_poly_init2 (
buf, repLength);
1523 _fmpz_poly_set_length (
buf, repLength);
1524 _fmpz_vec_set (
buf->coeffs, F->coeffs+
k, repLength);
1525 _fmpz_poly_normalise (
buf);
1530 fmpz_poly_clear (
buf);
1610 const fmpq_poly_t
mipo)
1618 int degf= fmpz_poly_degree(F);
1628 repLength= degfSubK + 1;
1632 while (
j*d2 < repLength)
1634 fmpq_poly_init2 (
buf, d2);
1635 _fmpq_poly_set_length (
buf, d2);
1636 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k +
j*d2, d2);
1637 _fmpq_poly_normalise (
buf);
1641 fmpq_poly_clear (
buf);
1643 if (repLength -
j*d2 != 0 &&
j*d2 - repLength < d2)
1647 fmpq_poly_init2 (
buf, repLength);
1648 _fmpq_poly_set_length (
buf, repLength);
1650 _fmpz_vec_set (
buf->coeffs, F->coeffs +
k +
j*d2, repLength);
1651 _fmpq_poly_normalise (
buf);
1654 fmpq_poly_clear (
buf);
1675 nmod_poly_set (
f, F);
1676 nmod_poly_set (
g,
G);
1677 int degf= nmod_poly_degree(
f);
1678 int degg= nmod_poly_degree(
g);
1683 if (nmod_poly_length (
f) < (
long) d*(
k+1))
1684 nmod_poly_fit_length (
f,(
long)d*(
k+1));
1690 int degfSubLf= degf;
1691 int deggSubLg=
degg-lg;
1692 int repLengthBuf2, repLengthBuf1, ind, tmp;
1693 while (degf >= lf || lg >= 0)
1697 else if (degfSubLf < 0)
1700 repLengthBuf1= degfSubLf + 1;
1703 for (ind= 0; ind < repLengthBuf1; ind++)
1704 nmod_poly_set_coeff_ui (
buf1, ind, nmod_poly_get_coeff_ui (
f, ind+lf));
1705 _nmod_poly_normalise (
buf1);
1707 repLengthBuf1= nmod_poly_length (
buf1);
1709 if (deggSubLg >= d - 1)
1710 repLengthBuf2= d - 1;
1711 else if (deggSubLg < 0)
1714 repLengthBuf2= deggSubLg + 1;
1717 for (ind= 0; ind < repLengthBuf2; ind++)
1718 nmod_poly_set_coeff_ui (
buf2, ind, nmod_poly_get_coeff_ui (
g, ind + lg));
1720 _nmod_poly_normalise (
buf2);
1721 repLengthBuf2= nmod_poly_length (
buf2);
1724 for (ind= 0; ind < repLengthBuf1; ind++)
1725 nmod_poly_set_coeff_ui (buf3, ind, nmod_poly_get_coeff_ui (
buf1, ind));
1726 for (ind= repLengthBuf1; ind < d; ind++)
1727 nmod_poly_set_coeff_ui (buf3, ind, 0);
1728 for (ind= 0; ind < repLengthBuf2; ind++)
1729 nmod_poly_set_coeff_ui (buf3, ind+d, nmod_poly_get_coeff_ui (
buf2, ind));
1730 _nmod_poly_normalise (buf3);
1737 degfSubLf= degf - lf;
1740 deggSubLg=
degg - lg;
1742 if (lg >= 0 && deggSubLg > 0)
1744 if (repLengthBuf2 > degfSubLf + 1)
1745 degfSubLf= repLengthBuf2 - 1;
1746 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1747 for (ind= 0; ind < tmp; ind++)
1748 nmod_poly_set_coeff_ui (
g, ind + lg,
1749 n_submod (nmod_poly_get_coeff_ui (
g, ind + lg),
1750 nmod_poly_get_coeff_ui (
buf1, ind),
1764 for (ind= 0; ind < repLengthBuf2; ind++)
1765 nmod_poly_set_coeff_ui (
f, ind + lf,
1766 n_submod (nmod_poly_get_coeff_ui (
f, ind + lf),
1767 nmod_poly_get_coeff_ui (
buf2, ind),
1783#if ( __FLINT_RELEASE >= 20400)
1791 fq_nmod_poly_t
f,
g;
1792 int degf= fq_nmod_poly_degree(F,
fq_con);
1799 fq_nmod_poly_set (
f, F,
fq_con);
1801 if (fq_nmod_poly_length (
f,
fq_con) < (
long) d*(
k + 1))
1802 fq_nmod_poly_fit_length (
f, (
long) d*(
k + 1),
fq_con);
1808 int degfSubLf= degf;
1809 int deggSubLg=
degg-lg;
1810 int repLengthBuf2, repLengthBuf1, tmp;
1811 while (degf >= lf || lg >= 0)
1815 else if (degfSubLf < 0)
1818 repLengthBuf1= degfSubLf + 1;
1819 fq_nmod_poly_init2 (
buf1, repLengthBuf1,
fq_con);
1820 _fq_nmod_poly_set_length (
buf1, repLengthBuf1,
fq_con);
1822 _fq_nmod_vec_set (
buf1->coeffs,
f->coeffs + lf, repLengthBuf1,
fq_con);
1825 repLengthBuf1= fq_nmod_poly_length (
buf1,
fq_con);
1827 if (deggSubLg >= d - 1)
1828 repLengthBuf2= d - 1;
1829 else if (deggSubLg < 0)
1832 repLengthBuf2= deggSubLg + 1;
1834 fq_nmod_poly_init2 (
buf2, repLengthBuf2,
fq_con);
1835 _fq_nmod_poly_set_length (
buf2, repLengthBuf2,
fq_con);
1836 _fq_nmod_vec_set (
buf2->coeffs,
g->coeffs + lg, repLengthBuf2,
fq_con);
1839 repLengthBuf2= fq_nmod_poly_length (
buf2,
fq_con);
1841 fq_nmod_poly_init2 (buf3, repLengthBuf2 + d,
fq_con);
1842 _fq_nmod_poly_set_length (buf3, repLengthBuf2 + d,
fq_con);
1843 _fq_nmod_vec_set (buf3->coeffs,
buf1->coeffs, repLengthBuf1,
fq_con);
1844 _fq_nmod_vec_set (buf3->coeffs + d,
buf2->coeffs, repLengthBuf2,
fq_con);
1846 _fq_nmod_poly_normalise (buf3,
fq_con);
1853 degfSubLf= degf - lf;
1856 deggSubLg=
degg - lg;
1858 if (lg >= 0 && deggSubLg > 0)
1860 if (repLengthBuf2 > degfSubLf + 1)
1861 degfSubLf= repLengthBuf2 - 1;
1862 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1863 _fq_nmod_vec_sub (
g->coeffs + lg,
g->coeffs + lg,
buf1->
coeffs,
1874 _fq_nmod_vec_sub (
f->coeffs + lf,
f->coeffs + lf,
buf2->coeffs,
1897 fmpz_poly_set (
f, F);
1898 fmpz_poly_set (
g,
G);
1899 int degf= fmpz_poly_degree(
f);
1900 int degg= fmpz_poly_degree(
g);
1904 if (fmpz_poly_length (
f) < (
long) d*(
k+1))
1905 fmpz_poly_fit_length (
f,(
long)d*(
k+1));
1911 int degfSubLf= degf;
1912 int deggSubLg=
degg-lg;
1913 int repLengthBuf2, repLengthBuf1, ind, tmp;
1915 while (degf >= lf || lg >= 0)
1919 else if (degfSubLf < 0)
1922 repLengthBuf1= degfSubLf + 1;
1924 fmpz_poly_init2 (
buf1, repLengthBuf1);
1926 for (ind= 0; ind < repLengthBuf1; ind++)
1928 fmpz_poly_get_coeff_fmpz (
tmp1,
f, ind + lf);
1929 fmpz_poly_set_coeff_fmpz (
buf1, ind,
tmp1);
1931 _fmpz_poly_normalise (
buf1);
1933 repLengthBuf1= fmpz_poly_length (
buf1);
1935 if (deggSubLg >= d - 1)
1936 repLengthBuf2= d - 1;
1937 else if (deggSubLg < 0)
1940 repLengthBuf2= deggSubLg + 1;
1942 fmpz_poly_init2 (
buf2, repLengthBuf2);
1944 for (ind= 0; ind < repLengthBuf2; ind++)
1946 fmpz_poly_get_coeff_fmpz (
tmp1,
g, ind + lg);
1947 fmpz_poly_set_coeff_fmpz (
buf2, ind,
tmp1);
1950 _fmpz_poly_normalise (
buf2);
1951 repLengthBuf2= fmpz_poly_length (
buf2);
1953 fmpz_poly_init2 (buf3, repLengthBuf2 + d);
1954 for (ind= 0; ind < repLengthBuf1; ind++)
1956 fmpz_poly_get_coeff_fmpz (
tmp1,
buf1, ind);
1957 fmpz_poly_set_coeff_fmpz (buf3, ind,
tmp1);
1959 for (ind= repLengthBuf1; ind < d; ind++)
1960 fmpz_poly_set_coeff_ui (buf3, ind, 0);
1961 for (ind= 0; ind < repLengthBuf2; ind++)
1963 fmpz_poly_get_coeff_fmpz (
tmp1,
buf2, ind);
1964 fmpz_poly_set_coeff_fmpz (buf3, ind + d,
tmp1);
1966 _fmpz_poly_normalise (buf3);
1973 degfSubLf= degf - lf;
1976 deggSubLg=
degg - lg;
1978 if (lg >= 0 && deggSubLg > 0)
1980 if (repLengthBuf2 > degfSubLf + 1)
1981 degfSubLf= repLengthBuf2 - 1;
1982 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1983 for (ind= 0; ind < tmp; ind++)
1985 fmpz_poly_get_coeff_fmpz (
tmp1,
g, ind + lg);
1986 fmpz_poly_get_coeff_fmpz (
tmp2,
buf1, ind);
1988 fmpz_poly_set_coeff_fmpz (
g, ind + lg,
tmp1);
1993 fmpz_poly_clear (
buf1);
1994 fmpz_poly_clear (
buf2);
1995 fmpz_poly_clear (buf3);
2000 for (ind= 0; ind < repLengthBuf2; ind++)
2002 fmpz_poly_get_coeff_fmpz (
tmp1,
f, ind + lf);
2003 fmpz_poly_get_coeff_fmpz (
tmp2,
buf2, ind);
2005 fmpz_poly_set_coeff_fmpz (
f, ind + lf,
tmp1);
2008 fmpz_poly_clear (
buf1);
2009 fmpz_poly_clear (
buf2);
2010 fmpz_poly_clear (buf3);
2013 fmpz_poly_clear (
f);
2014 fmpz_poly_clear (
g);
2021#if ( __FLINT_RELEASE >= 20400)
2024 const fq_nmod_ctx_t
fq_con)
2032 int degf= fq_nmod_poly_degree(F,
fq_con);
2034 int degfSubK, repLength;
2041 repLength= degfSubK + 1;
2043 fq_nmod_poly_init2 (
buf, repLength,
fq_con);
2044 _fq_nmod_poly_set_length (
buf, repLength,
fq_con);
2045 _fq_nmod_vec_set (
buf->coeffs, F->coeffs+
k, repLength,
fq_con);
2068 int degf= nmod_poly_degree(F);
2070 int degfSubK, repLength,
j;
2077 repLength= degfSubK + 1;
2080 for (
j= 0;
j < repLength;
j++)
2081 nmod_poly_set_coeff_ui (
buf,
j, nmod_poly_get_coeff_ui (F,
j +
k));
2082 _nmod_poly_normalise (
buf);
2108 nmod_poly_mullow (F1, F1, G1, (
long)
k);
2115 int b= nmod_poly_degree (F2) + nmod_poly_degree (G2) -
k - degtailF - degtailG
2116 + d1*(2+taildegF + taildegG);
2117 nmod_poly_mulhigh (F2, F2, G2,
b);
2118 nmod_poly_shift_right (F2, F2,
b);
2119 int d2=
tmax (nmod_poly_degree (F2)/d1, nmod_poly_degree (F1)/d1);
2142 int d1= degAx + 1 + degBx;
2143 int d2=
tmax (degAy, degBy);
2145 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2148 nmod_poly_t FLINTA, FLINTB;
2153 nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k);
2162#if ( __FLINT_RELEASE >= 20400)
2166 const fq_nmod_ctx_t
fq_con)
2172 fq_nmod_poly_t F1, F2;
2175 fq_nmod_poly_t G1, G2;
2179 fq_nmod_poly_mullow (F1, F1, G1, (
long)
k,
fq_con);
2186 int b=
k + degtailF + degtailG - d1*(2+taildegF + taildegG);
2188 fq_nmod_poly_reverse (F2, F2, fq_nmod_poly_length (F2,
fq_con),
fq_con);
2189 fq_nmod_poly_reverse (G2, G2, fq_nmod_poly_length (G2,
fq_con),
fq_con);
2190 fq_nmod_poly_mullow (F2, F2, G2,
b+1,
fq_con);
2191 fq_nmod_poly_reverse (F2, F2,
b+1,
fq_con);
2193 int d2=
tmax (fq_nmod_poly_degree (F2,
fq_con)/d1,
2194 fq_nmod_poly_degree (F1,
fq_con)/d1);
2208 const fq_nmod_ctx_t
fq_con)
2217 int d1= degAx + 1 + degBx;
2218 int d2=
tmax (degAy, degBy);
2220 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2223 fq_nmod_poly_t FLINTA, FLINTB;
2228 fq_nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k,
fq_con);
2253 fmpz_poly_mullow (F1, F1, G1, (
long)
k);
2260 int b= fmpz_poly_degree (F2) + fmpz_poly_degree (G2) -
k - degtailF - degtailG
2261 + d1*(2+taildegF + taildegG);
2262 fmpz_poly_mulhigh_n (F2, F2, G2,
b);
2263 fmpz_poly_shift_right (F2, F2,
b);
2264 int d2=
tmax (fmpz_poly_degree (F2)/d1, fmpz_poly_degree (F1)/d1);
2268 fmpz_poly_clear (F1);
2269 fmpz_poly_clear (F2);
2270 fmpz_poly_clear (G1);
2271 fmpz_poly_clear (G2);
2284 int d1= degAx + 1 + degBx;
2291 fmpz_poly_t FLINTA, FLINTB;
2296 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, (
long)
k);
2298 fmpz_poly_clear (FLINTA);
2299 fmpz_poly_clear (FLINTB);
2344 int degFx=
degree (F, 1);
2345 int degFa=
degree (F, a);
2349 int d2= degFa+degGa+1;
2350 int d1= degFx + 1 + degGx;
2358 fmpz_poly_t FLINTF, FLINTG;
2362 fmpz_poly_mullow (FLINTF, FLINTF, FLINTG, d1*
degree (
M));
2367 fmpz_poly_clear (FLINTF);
2368 fmpz_poly_clear (FLINTG);
2379 result.rep.SetLength (d*(degAy + 1));
2382 resultp=
result.rep.elts();
2385 int j,
k, bufRepLength;
2389 if (
i.coeff().inCoeffDomain())
2395 bufp=
buf.rep.elts();
2396 bufRepLength= (int)
buf.rep.length();
2397 for (
j= 0;
j < bufRepLength;
j++)
2398 resultp [
j +
k]= bufp [
j];
2406#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2411 result.rep.SetLength (d*(degAy + 1));
2415 resultp=
result.rep.elts();
2420 int j,
k, buf1RepLength;
2424 if (
i.coeff().inCoeffDomain())
2433 buf1p=
buf1.rep.elts();
2434 buf1RepLength= (int)
buf1.rep.length();
2435 for (
j= 0;
j < buf1RepLength;
j++)
2436 resultp [
j +
k]= buf1p [
j];
2448 subA1.rep.SetLength ((
long) d*(degAy + 2));
2449 subA2.rep.SetLength ((
long) d*(degAy + 2));
2454 subA1p= subA1.rep.elts();
2455 subA2p= subA2.rep.elts();
2460 int j,
k, kk, bufRepLength;
2464 if (
i.coeff().inCoeffDomain())
2467 buf= to_zz_pEX (to_zz_pE (
buf2));
2473 kk= (degAy -
i.exp())*d;
2474 bufp=
buf.rep.elts();
2475 bufRepLength= (int)
buf.rep.length();
2476 for (
j= 0;
j < bufRepLength;
j++)
2478 subA1p [
j +
k] += bufp [
j];
2479 subA2p [
j + kk] += bufp [
j];
2492 subA1.rep.SetLength ((
long) d*(degAy + 2));
2493 subA2.rep.SetLength ((
long) d*(degAy + 2));
2497 subA1p= subA1.rep.elts();
2498 subA2p= subA2.rep.elts();
2501 int j,
k, kk, bufRepLength;
2508 kk= (degAy -
i.exp())*d;
2509 bufp=
buf.rep.elts();
2510 bufRepLength= (int)
buf.rep.length();
2511 for (
j= 0;
j < bufRepLength;
j++)
2513 subA1p [
j +
k] += bufp [
j];
2514 subA2p [
j + kk] += bufp [
j];
2522#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2542 if (
f.rep.length() < (
long) d*(
k+1))
2543 f.rep.SetLength ((
long)d*(
k+1));
2545 zz_pE *
gp=
g.rep.elts();
2546 zz_pE *
fp=
f.rep.elts();
2551 int degfSubLf= degf;
2552 int deggSubLg=
degg-lg;
2553 int repLengthBuf2, repLengthBuf1, ind, tmp;
2554 zz_pE zzpEZero= zz_pE();
2556 while (degf >= lf || lg >= 0)
2560 else if (degfSubLf < 0)
2563 repLengthBuf1= degfSubLf + 1;
2564 buf1.rep.SetLength((
long) repLengthBuf1);
2566 buf1p=
buf1.rep.elts();
2567 for (ind= 0; ind < repLengthBuf1; ind++)
2568 buf1p [ind]=
fp [ind + lf];
2571 repLengthBuf1=
buf1.rep.length();
2573 if (deggSubLg >= d - 1)
2574 repLengthBuf2= d - 1;
2575 else if (deggSubLg < 0)
2578 repLengthBuf2= deggSubLg + 1;
2580 buf2.rep.SetLength ((
long) repLengthBuf2);
2581 buf2p=
buf2.rep.elts();
2582 for (ind= 0; ind < repLengthBuf2; ind++)
2583 buf2p [ind]=
gp [ind + lg];
2586 repLengthBuf2=
buf2.rep.length();
2588 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2589 buf3p= buf3.rep.elts();
2590 buf2p=
buf2.rep.elts();
2591 buf1p=
buf1.rep.elts();
2592 for (ind= 0; ind < repLengthBuf1; ind++)
2593 buf3p [ind]= buf1p [ind];
2594 for (ind= repLengthBuf1; ind < d; ind++)
2595 buf3p [ind]= zzpEZero;
2596 for (ind= 0; ind < repLengthBuf2; ind++)
2597 buf3p [ind + d]= buf2p [ind];
2605 degfSubLf= degf - lf;
2608 deggSubLg=
degg - lg;
2610 buf1p=
buf1.rep.elts();
2612 if (lg >= 0 && deggSubLg > 0)
2614 if (repLengthBuf2 > degfSubLf + 1)
2615 degfSubLf= repLengthBuf2 - 1;
2616 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2617 for (ind= 0; ind < tmp; ind++)
2618 gp [ind + lg] -= buf1p [ind];
2624 buf2p=
buf2.rep.elts();
2627 for (ind= 0; ind < repLengthBuf2; ind++)
2628 fp [ind + lf] -= buf2p [ind];
2656 if (
f.rep.length() < (
long) d*(
k+1))
2657 f.rep.SetLength ((
long)d*(
k+1));
2659 zz_p *
gp=
g.rep.elts();
2660 zz_p *
fp=
f.rep.elts();
2665 int degfSubLf= degf;
2666 int deggSubLg=
degg-lg;
2667 int repLengthBuf2, repLengthBuf1, ind, tmp;
2668 zz_p zzpZero= zz_p();
2669 while (degf >= lf || lg >= 0)
2673 else if (degfSubLf < 0)
2676 repLengthBuf1= degfSubLf + 1;
2677 buf1.rep.SetLength((
long) repLengthBuf1);
2679 buf1p=
buf1.rep.elts();
2680 for (ind= 0; ind < repLengthBuf1; ind++)
2681 buf1p [ind]=
fp [ind + lf];
2684 repLengthBuf1=
buf1.rep.length();
2686 if (deggSubLg >= d - 1)
2687 repLengthBuf2= d - 1;
2688 else if (deggSubLg < 0)
2691 repLengthBuf2= deggSubLg + 1;
2693 buf2.rep.SetLength ((
long) repLengthBuf2);
2694 buf2p=
buf2.rep.elts();
2695 for (ind= 0; ind < repLengthBuf2; ind++)
2696 buf2p [ind]=
gp [ind + lg];
2700 repLengthBuf2=
buf2.rep.length();
2703 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2704 buf3p= buf3.rep.elts();
2705 buf2p=
buf2.rep.elts();
2706 buf1p=
buf1.rep.elts();
2707 for (ind= 0; ind < repLengthBuf1; ind++)
2708 buf3p [ind]= buf1p [ind];
2709 for (ind= repLengthBuf1; ind < d; ind++)
2710 buf3p [ind]= zzpZero;
2711 for (ind= 0; ind < repLengthBuf2; ind++)
2712 buf3p [ind + d]= buf2p [ind];
2720 degfSubLf= degf - lf;
2723 deggSubLg=
degg - lg;
2725 buf1p=
buf1.rep.elts();
2727 if (lg >= 0 && deggSubLg > 0)
2729 if (repLengthBuf2 > degfSubLf + 1)
2730 degfSubLf= repLengthBuf2 - 1;
2731 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2732 for (ind= 0; ind < tmp; ind++)
2733 gp [ind + lg] -= buf1p [ind];
2738 buf2p=
buf2.rep.elts();
2741 for (ind= 0; ind < repLengthBuf2; ind++)
2742 fp [ind + lf] -= buf2p [ind];
2750#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2757 zz_pE *
fp=
f.rep.elts();
2765 int degfSubK, repLength,
j;
2772 repLength= degfSubK + 1;
2774 buf.rep.SetLength ((
long) repLength);
2775 bufp=
buf.rep.elts();
2776 for (
j= 0;
j < repLength;
j++)
2777 bufp [
j]=
fp [
j +
k];
2796 zz_p *
fp=
f.rep.elts();
2804 int degfSubK, repLength,
j;
2811 repLength= degfSubK + 1;
2813 buf.rep.SetLength ((
long) repLength);
2814 bufp=
buf.rep.elts();
2815 for (
j= 0;
j < repLength;
j++)
2816 bufp [
j]=
fp [
j +
k];
2842 MulTrunc (F1, F1, G1, (
long)
k);
2848 int b=
k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2852 MulTrunc (F2, F2, G2,
b + 1);
2855 int d2=
tmax (deg (F2)/d1, deg (F1)/d1);
2871 int d1= degAx + 1 + degBx;
2872 int d2=
tmax (degAy, degBy);
2874 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (
M)))
2875 return mulMod2NTLFpReci (
A,
B,
M);
2881 MulTrunc (NTLA, NTLA, NTLB, (
long)
k);
2889#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2905 MulTrunc (F1, F1, G1, (
long)
k);
2911 int b=
k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2915 MulTrunc (F2, F2, G2,
b + 1);
2918 int d2=
tmax (deg (F2)/d1, deg (F1)/d1);
2939#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
2940 nmod_poly_t FLINTmipo;
2954 int d1= degAx + degBx + 1;
2955 int d2=
tmax (degAy, degBy);
2965 if ((d1 > 128/degMipo) && (d2 > 160/degMipo) && (degAy == degBy) &&
2967 return mulMod2NTLFqReci (
A,
B,
M,
alpha);
2974 MulTrunc (NTLA, NTLA, NTLB, (
long)
k);
2984 A= mulMod2NTLFp (
A,
B,
M);
2996 ASSERT (
M.isUnivariate(),
"M must be univariate");
3002 if (
G.inCoeffDomain())
3009 if ((degF < 1 && degG < 1) && (F.
isUnivariate() &&
G.isUnivariate()) &&
3010 (F.
level() ==
G.level()))
3015 else if (degF <= 1 && degG <= 1)
3021 int sizeF=
size (F);
3022 int sizeG=
size (
G);
3024 int fallBackToNaive= 50;
3025 if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
3028 return mod (
G*F,
M);
3030 return mod (F*
G,
M);
3039 (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
3043 if (degF >=
m || degG >=
m)
3054 return F0G0 + MLo*(F0G1 + F1G0);
3067 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3069 DEBOUTLN (cerr,
"fatal end in mulMod2");
3098 if (
G.inCoeffDomain())
3101 int sizeF=
size (F);
3102 int sizeG=
size (
G);
3104 if (sizeF / MOD.
length() < 100 || sizeG / MOD.
length() < 100)
3107 return mod (
G*F, MOD);
3109 return mod (F*
G, MOD);
3116 if ((degF <= 1 && F.
level() <=
M.level()) &&
3117 (degG <= 1 &&
G.level() <=
M.level()))
3121 if (degF == 1 && degG == 1)
3132 return H11*
y*
y + (H01 - H00 - H11)*
y + H00;
3144 else if (degF == 1 && degG == 0)
3146 else if (degF == 0 && degG == 1)
3152 if (degF >=
m || degG >=
m)
3166 return F0G0 + MLo*(F0G1 + F1G0);
3170 m= (
tmax(degF, degG)+1)/2;
3179 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3181 DEBOUTLN (cerr,
"fatal end in mulMod");
3201 for (
int j= 1;
j <=
l;
j++,
i++)
3215 else if (L.
length() == 1)
3217 else if (L.
length() == 2)
3225 for (
int j= 1;
j <=
l;
j++,
i++)
3250 while (d -
i.exp() < 0)
3253 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
3268 ASSERT (!
g.isZero(),
"expected a unit");
3284 for (
int i= 1;
i <=
l;
i++)
3353#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3354 nmod_poly_t FLINTmipo;
3363 fq_nmod_poly_t FLINTA, FLINTB;
3367 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB,
fq_con);
3376 bool zz_pEbak= zz_pE::initialized();
3384 div (NTLA, NTLA, NTLB);
3436#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3437 nmod_poly_t FLINTmipo;
3445 fq_nmod_poly_t FLINTA, FLINTB;
3449 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB,
fq_con);
3464 DivRem (NTLQ, NTLR, NTLA, NTLB);
3480 else if (
x.
level() !=
A.level())
3491 while (
i.hasTerms() &&
i.exp() -
j*
m >= 0)
3534 int m= (int)
ceil ((
double) (degB + 1)/2.0) + 1;
3535 ASSERT (4*
m >= degA,
"expected degree (F, 1) < 2*degree (G, 1)");
3537 if (splitA.
length() == 3)
3539 if (splitA.
length() == 2)
3544 if (splitA.
length() == 1)
3566 if (splitR.
length() == 1)
3605 int m= (int)
ceil ((
double) (degB + 1)/ 2.0);
3606 ASSERT (3*
m > degA,
"expected degree (F, 1) < 3*degree (G, 1)");
3610 if (splitA.
length() == 2)
3614 if (splitA.
length() == 1)
3644 Q +=
LC (
R,
x)*xToM;
3703 H=
i.getItem()*xToDegB;
3713 H=
R*xToDegB +
i.getItem();
3747 H=
i.getItem()*xToDegB;
3755 H=
R*xToDegB +
i.getItem();
3774 if (
A.inCoeffDomain())
3781#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
3791#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3792 nmod_poly_t FLINTmipo;
3800 fq_nmod_poly_t FLINTA, FLINTB;
3803 int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA,
fq_con);
3814 return divide (NTLB, NTLA);
3818 nmod_poly_t FLINTA, FLINTB;
3821 nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3822 bool result= nmod_poly_is_zero (FLINTA);
3829 return divide (NTLB, NTLA);
3839 fmpq_poly_t FLINTA,FLINTB;
3842 fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3843 bool result= fmpq_poly_is_zero (FLINTA);
3844 fmpq_poly_clear (FLINTA);
3845 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.
const signed long floor(const ampf< Precision > &x)
const signed long ceil(const ampf< Precision > &x)
int status int void * buf
bool getReduce(const Variable &alpha)