32 #include <NTL/lzz_pEX.h> 45 fmpz_poly_init2 (result, d*(degAy + 1));
46 _fmpz_poly_set_length (result, d*(degAy + 1));
50 if (
i.coeff().inBaseDomain())
57 _fmpz_poly_normalise(result);
67 int degf= fmpz_poly_degree (F);
80 repLength= degfSubK + 1;
82 fmpq_poly_init2 (buf, repLength);
83 _fmpq_poly_set_length (buf, repLength);
84 _fmpz_vec_set (buf->coeffs, F->coeffs + k, repLength);
85 _fmpq_poly_normalise (buf);
86 fmpq_poly_rem (buf, buf, mipo);
89 fmpq_poly_clear (buf);
93 fmpq_poly_clear (mipo);
110 int degAa=
degree (A, alpha);
111 int degBa=
degree (B, alpha);
112 int d= degAa + 1 + degBa;
114 fmpz_poly_t FLINTA,FLINTB;
118 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
123 fmpz_poly_clear (FLINTA);
124 fmpz_poly_clear (FLINTB);
139 fmpz_poly_t FLINTA,FLINTB;
142 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
146 fmpz_poly_clear (FLINTA);
147 fmpz_poly_clear (FLINTB);
175 fmpq_poly_t FLINTA,FLINTB;
179 fmpq_poly_div (FLINTA, FLINTA, FLINTB);
182 fmpq_poly_clear (FLINTA);
183 fmpq_poly_clear (FLINTB);
193 fmpq_poly_t FLINTA,FLINTB;
197 fmpq_poly_rem (FLINTA, FLINTA, FLINTB);
200 fmpq_poly_clear (FLINTA);
201 fmpq_poly_clear (FLINTB);
218 int degAa=
degree (A, alpha);
219 int degBa=
degree (B, alpha);
220 int d= degAa + 1 + degBa;
222 fmpz_poly_t FLINTA,FLINTB;
227 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, k);
231 fmpz_poly_clear (FLINTA);
232 fmpz_poly_clear (FLINTB);
243 if (G.inCoeffDomain())
257 fmpz_poly_t FLINTA,FLINTB;
260 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, m);
264 fmpz_poly_clear (FLINTA);
265 fmpz_poly_clear (FLINTB);
275 return F*
power (x,d);
278 while (d - i.
exp() < 0)
298 ASSERT (F.
mvar() ==
x,
"main variable of F and x differ");
312 for (
int i= 1;
i <=
l;
i++)
317 g -=
power (x, (1 << (
i - 1)))*
325 h=
mod (h,
power (x, exp + (1 <<
i)) - 1);
426 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 428 fmpz_mod_poly_t FLINTmipo;
430 fq_poly_t FLINTF, FLINTG;
438 fq_ctx_init_modulus (fq_con, FLINTmipo,
"Z");
443 fq_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
449 fmpz_mod_poly_clear (FLINTmipo);
450 fq_poly_clear (FLINTF, fq_con);
451 fq_poly_clear (FLINTG, fq_con);
452 fq_ctx_clear (fq_con);
457 ZZ_pE::init (NTLmipo);
460 mul (NTLf, NTLf, NTLg);
480 fmpz_mod_poly_t FLINTF, FLINTG;
483 fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
485 fmpz_mod_poly_clear (FLINTG);
486 fmpz_mod_poly_clear (FLINTF);
487 fmpz_clear (FLINTpk);
497 ZZ_pX NTLf= to_ZZ_pX (ZZf);
498 ZZ_pX NTLg= to_ZZ_pX (ZZg);
499 mul (NTLf, NTLf, NTLg);
511 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 513 fmpz_mod_poly_t FLINTmipo;
521 fq_ctx_init_modulus (fq_con, FLINTmipo,
"Z");
532 fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF, fq_con);
535 fmpz_poly_clear (FLINTF);
536 fq_poly_clear (FLINTG, fq_con);
546 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
549 fmpz_poly_clear (FLINTG);
550 fq_poly_clear (FLINTF, fq_con);
559 fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
562 fq_clear (FLINTF, fq_con);
563 fq_clear (FLINTG, fq_con);
567 fmpz_mod_poly_clear (FLINTmipo);
568 fq_ctx_clear (fq_con);
574 ZZ_pE::init (NTLmipo);
580 mul (NTLg, to_ZZ_pE (NTLf), NTLg);
587 mul (NTLf, NTLf, to_ZZ_pE (NTLg));
595 mul (result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
608 ASSERT (F.
level() == G.level(),
"expected polys of same level");
625 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 626 nmod_poly_t FLINTmipo;
634 fq_nmod_poly_t FLINTF, FLINTG;
638 fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
648 zz_pE::init (NTLMipo);
651 mul (NTLF, NTLF, NTLG);
658 nmod_poly_t FLINTF, FLINTG;
661 nmod_poly_mul (FLINTF, FLINTF, FLINTG);
668 mul (NTLF, NTLF, NTLG);
710 fmpz_mod_poly_t FLINTF, FLINTG;
713 fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
715 fmpz_mod_poly_clear (FLINTG);
716 fmpz_mod_poly_clear (FLINTF);
717 fmpz_clear (FLINTpk);
727 ZZ_pX NTLf= to_ZZ_pX (ZZf);
728 ZZ_pX NTLg= to_ZZ_pX (ZZg);
729 rem (NTLf, NTLf, NTLg);
739 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 741 fmpz_mod_poly_t FLINTmipo;
743 fq_poly_t FLINTF, FLINTG;
751 fq_ctx_init_modulus (fq_con, FLINTmipo,
"Z");
756 fq_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
762 fmpz_mod_poly_clear (FLINTmipo);
763 fq_poly_clear (FLINTF, fq_con);
764 fq_poly_clear (FLINTG, fq_con);
765 fq_ctx_clear (fq_con);
771 ZZ_pE::init (NTLmipo);
774 rem (NTLf, NTLf, NTLg);
799 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 800 nmod_poly_t FLINTmipo;
808 fq_nmod_poly_t FLINTF, FLINTG;
812 fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
822 zz_pE::init (NTLMipo);
825 rem (NTLF, NTLF, NTLG);
832 nmod_poly_t FLINTF, FLINTG;
835 nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
842 rem (NTLF, NTLF, NTLG);
867 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 869 fmpz_mod_poly_t FLINTmipo;
878 fq_ctx_init_modulus (fq_con, FLINTmipo,
"Z");
883 fq_inv (FLINTG, FLINTG, fq_con);
884 fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
889 fmpz_mod_poly_clear (FLINTmipo);
890 fq_clear (FLINTF, fq_con);
891 fq_clear (FLINTG, fq_con);
892 fq_ctx_clear (fq_con);
897 ZZ_pE::init (NTLmipo);
901 div (result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
917 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 919 fmpz_mod_poly_t FLINTmipo;
929 fq_ctx_init_modulus (fq_con, FLINTmipo,
"Z");
934 fq_inv (FLINTG, FLINTG, fq_con);
935 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
941 fmpz_mod_poly_clear (FLINTmipo);
942 fq_poly_clear (FLINTF, fq_con);
943 fq_clear (FLINTG, fq_con);
944 fq_ctx_clear (fq_con);
949 ZZ_pE::init (NTLmipo);
952 div (NTLf, NTLf, to_ZZ_pE (NTLg));
973 fmpz_mod_poly_t FLINTF, FLINTG;
976 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
978 fmpz_mod_poly_clear (FLINTG);
979 fmpz_mod_poly_clear (FLINTF);
980 fmpz_clear (FLINTpk);
990 ZZ_pX NTLf= to_ZZ_pX (ZZf);
991 ZZ_pX NTLg= to_ZZ_pX (ZZg);
992 div (NTLf, NTLf, NTLg);
1002 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 1004 fmpz_mod_poly_t FLINTmipo;
1006 fq_poly_t FLINTF, FLINTG;
1013 fq_ctx_init_modulus (fq_con, FLINTmipo,
"Z");
1018 fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1023 fmpz_clear (FLINTp);
1024 fmpz_mod_poly_clear (FLINTmipo);
1025 fq_ctx_clear (fq_con);
1026 fq_poly_clear (FLINTF, fq_con);
1027 fq_poly_clear (FLINTG, fq_con);
1032 ZZ_pE::init (NTLmipo);
1035 div (NTLf, NTLf, NTLg);
1060 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 1061 nmod_poly_t FLINTmipo;
1069 fq_nmod_poly_t FLINTF, FLINTG;
1073 fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1083 zz_pE::init (NTLMipo);
1086 div (NTLF, NTLF, NTLG);
1093 nmod_poly_t FLINTF, FLINTG;
1096 nmod_poly_div (FLINTF, FLINTF, FLINTG);
1103 div (NTLF, NTLF, NTLG);
1119 result->length= d*(degAy + 1);
1120 flint_mpn_zero (result->coeffs, d*(degAy+1));
1129 flint_mpn_copyi (result->coeffs+k, buf->coeffs, nmod_poly_length(buf));
1133 _nmod_poly_normalise (result);
1136 #if ( __FLINT_RELEASE >= 20400) 1139 const fq_nmod_ctx_t
fq_con)
1142 fq_nmod_poly_init2 (result, d*(degAy + 1), fq_con);
1143 _fq_nmod_poly_set_length (result, d*(degAy + 1), fq_con);
1144 _fq_nmod_vec_zero (result->coeffs, d*(degAy + 1), fq_con);
1146 fq_nmod_poly_t
buf1;
1154 if (
i.coeff().inCoeffDomain())
1157 fq_nmod_poly_init2 (buf1, 1, fq_con);
1158 fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1165 _fq_nmod_vec_set (result->coeffs+k, buf1->coeffs,
1166 fq_nmod_poly_length (buf1, fq_con), fq_con);
1171 _fq_nmod_poly_normalise (result, fq_con);
1223 fmpz_poly_init2 (result, d1*(degAy + 1));
1224 _fmpz_poly_set_length (result, d1*(degAy + 1));
1232 if (
i.coeff().inCoeffDomain())
1236 _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1237 fmpz_poly_clear (buf);
1246 _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1247 fmpz_poly_clear (buf);
1251 _fmpz_poly_normalise (result);
1265 int k, kk,
j, bufRepLength;
1271 kk= (degAy -
i.exp())*d;
1272 bufRepLength= (int) nmod_poly_length (buf);
1273 for (j= 0; j < bufRepLength; j++)
1275 nmod_poly_set_coeff_ui (subA1, j + k,
1276 n_addmod (nmod_poly_get_coeff_ui (subA1, j+k),
1277 nmod_poly_get_coeff_ui (buf, j),
1281 nmod_poly_set_coeff_ui (subA2, j + kk,
1282 n_addmod (nmod_poly_get_coeff_ui (subA2, j + kk),
1283 nmod_poly_get_coeff_ui (buf, j),
1290 _nmod_poly_normalise (subA1);
1291 _nmod_poly_normalise (subA2);
1294 #if ( __FLINT_RELEASE >= 20400) 1300 fq_nmod_poly_init2 (subA1, d*(degAy + 2), fq_con);
1301 fq_nmod_poly_init2 (subA2, d*(degAy + 2), fq_con);
1303 _fq_nmod_poly_set_length (subA1, d*(degAy + 2), fq_con);
1304 _fq_nmod_vec_zero (subA1->coeffs, d*(degAy + 2), fq_con);
1306 _fq_nmod_poly_set_length (subA2, d*(degAy + 2), fq_con);
1307 _fq_nmod_vec_zero (subA2->coeffs, d*(degAy + 2), fq_con);
1309 fq_nmod_poly_t
buf1;
1316 if (
i.coeff().inCoeffDomain())
1319 fq_nmod_poly_init2 (buf1, 1, fq_con);
1320 fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1327 kk= (degAy -
i.exp())*d;
1328 _fq_nmod_vec_add (subA1->coeffs+k, subA1->coeffs+k, buf1->coeffs,
1329 fq_nmod_poly_length(buf1, fq_con), fq_con);
1330 _fq_nmod_vec_add (subA2->coeffs+kk, subA2->coeffs+kk, buf1->coeffs,
1331 fq_nmod_poly_length(buf1, fq_con), fq_con);
1335 _fq_nmod_poly_normalise (subA1, fq_con);
1336 _fq_nmod_poly_normalise (subA2, fq_con);
1345 fmpz_poly_init2 (subA1, d*(degAy + 2));
1346 fmpz_poly_init2 (subA2, d*(degAy + 2));
1356 kk= (degAy -
i.exp())*d;
1357 _fmpz_vec_add (subA1->coeffs+k, subA1->coeffs + k, buf->coeffs, buf->length);
1358 _fmpz_vec_add (subA2->coeffs+kk, subA2->coeffs + kk, buf->coeffs, buf->length);
1359 fmpz_poly_clear (buf);
1362 _fmpz_poly_normalise (subA1);
1363 _fmpz_poly_normalise (subA2);
1374 int degf= fmpz_poly_degree(F);
1376 int degfSubK, repLength;
1383 repLength= degfSubK + 1;
1385 fmpz_poly_init2 (buf, repLength);
1386 _fmpz_poly_set_length (buf, repLength);
1387 _fmpz_vec_set (buf->coeffs, F->coeffs+k, repLength);
1388 _fmpz_poly_normalise (buf);
1393 fmpz_poly_clear (buf);
1473 const fmpq_poly_t mipo)
1481 int degf= fmpz_poly_degree(F);
1491 repLength= degfSubK + 1;
1495 while (j*d2 < repLength)
1497 fmpq_poly_init2 (buf, d2);
1498 _fmpq_poly_set_length (buf, d2);
1499 _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, d2);
1500 _fmpq_poly_normalise (buf);
1501 fmpq_poly_rem (buf, buf, mipo);
1504 fmpq_poly_clear (buf);
1506 if (repLength - j*d2 != 0 && j*d2 - repLength < d2)
1510 fmpq_poly_init2 (buf, repLength);
1511 _fmpq_poly_set_length (buf, repLength);
1513 _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, repLength);
1514 _fmpq_poly_normalise (buf);
1515 fmpq_poly_rem (buf, buf, mipo);
1517 fmpq_poly_clear (buf);
1520 result += result2*
power (y, i);
1538 nmod_poly_set (f, F);
1539 nmod_poly_set (g, G);
1540 int degf= nmod_poly_degree(f);
1541 int degg= nmod_poly_degree(g);
1546 if (nmod_poly_length (f) < (
long) d*(k+1))
1547 nmod_poly_fit_length (f,(
long)d*(k+1));
1553 int degfSubLf= degf;
1554 int deggSubLg= degg-lg;
1555 int repLengthBuf2, repLengthBuf1, ind, tmp;
1556 while (degf >= lf || lg >= 0)
1560 else if (degfSubLf < 0)
1563 repLengthBuf1= degfSubLf + 1;
1566 for (ind= 0; ind < repLengthBuf1; ind++)
1567 nmod_poly_set_coeff_ui (buf1, ind, nmod_poly_get_coeff_ui (f, ind+lf));
1568 _nmod_poly_normalise (buf1);
1570 repLengthBuf1= nmod_poly_length (buf1);
1572 if (deggSubLg >= d - 1)
1573 repLengthBuf2= d - 1;
1574 else if (deggSubLg < 0)
1577 repLengthBuf2= deggSubLg + 1;
1580 for (ind= 0; ind < repLengthBuf2; ind++)
1581 nmod_poly_set_coeff_ui (buf2, ind, nmod_poly_get_coeff_ui (g, ind + lg));
1583 _nmod_poly_normalise (buf2);
1584 repLengthBuf2= nmod_poly_length (buf2);
1587 for (ind= 0; ind < repLengthBuf1; ind++)
1588 nmod_poly_set_coeff_ui (buf3, ind, nmod_poly_get_coeff_ui (buf1, ind));
1589 for (ind= repLengthBuf1; ind < d; ind++)
1590 nmod_poly_set_coeff_ui (buf3, ind, 0);
1591 for (ind= 0; ind < repLengthBuf2; ind++)
1592 nmod_poly_set_coeff_ui (buf3, ind+d, nmod_poly_get_coeff_ui (buf2, ind));
1593 _nmod_poly_normalise (buf3);
1600 degfSubLf= degf - lf;
1603 deggSubLg= degg - lg;
1605 if (lg >= 0 && deggSubLg > 0)
1607 if (repLengthBuf2 > degfSubLf + 1)
1608 degfSubLf= repLengthBuf2 - 1;
1609 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1610 for (ind= 0; ind < tmp; ind++)
1611 nmod_poly_set_coeff_ui (g, ind + lg,
1612 n_submod (nmod_poly_get_coeff_ui (g, ind + lg),
1613 nmod_poly_get_coeff_ui (buf1, ind),
1627 for (ind= 0; ind < repLengthBuf2; ind++)
1628 nmod_poly_set_coeff_ui (f, ind + lf,
1629 n_submod (nmod_poly_get_coeff_ui (f, ind + lf),
1630 nmod_poly_get_coeff_ui (buf2, ind),
1646 #if ( __FLINT_RELEASE >= 20400) 1654 fq_nmod_poly_t
f,
g;
1655 int degf= fq_nmod_poly_degree(F, fq_con);
1656 int degg= fq_nmod_poly_degree(G, fq_con);
1662 fq_nmod_poly_set (f, F, fq_con);
1663 fq_nmod_poly_set (g, G, fq_con);
1664 if (fq_nmod_poly_length (f, fq_con) < (
long) d*(k + 1))
1665 fq_nmod_poly_fit_length (f, (
long) d*(k + 1), fq_con);
1671 int degfSubLf= degf;
1672 int deggSubLg= degg-lg;
1673 int repLengthBuf2, repLengthBuf1, tmp;
1674 while (degf >= lf || lg >= 0)
1678 else if (degfSubLf < 0)
1681 repLengthBuf1= degfSubLf + 1;
1682 fq_nmod_poly_init2 (buf1, repLengthBuf1, fq_con);
1683 _fq_nmod_poly_set_length (buf1, repLengthBuf1, fq_con);
1685 _fq_nmod_vec_set (buf1->coeffs, f->coeffs + lf, repLengthBuf1, fq_con);
1686 _fq_nmod_poly_normalise (buf1, fq_con);
1688 repLengthBuf1= fq_nmod_poly_length (buf1, fq_con);
1690 if (deggSubLg >= d - 1)
1691 repLengthBuf2= d - 1;
1692 else if (deggSubLg < 0)
1695 repLengthBuf2= deggSubLg + 1;
1697 fq_nmod_poly_init2 (buf2, repLengthBuf2, fq_con);
1698 _fq_nmod_poly_set_length (buf2, repLengthBuf2, fq_con);
1699 _fq_nmod_vec_set (buf2->coeffs, g->coeffs + lg, repLengthBuf2, fq_con);
1701 _fq_nmod_poly_normalise (buf2, fq_con);
1702 repLengthBuf2= fq_nmod_poly_length (buf2, fq_con);
1704 fq_nmod_poly_init2 (buf3, repLengthBuf2 + d, fq_con);
1705 _fq_nmod_poly_set_length (buf3, repLengthBuf2 + d, fq_con);
1706 _fq_nmod_vec_set (buf3->coeffs, buf1->coeffs, repLengthBuf1, fq_con);
1707 _fq_nmod_vec_set (buf3->coeffs + d, buf2->coeffs, repLengthBuf2, fq_con);
1709 _fq_nmod_poly_normalise (buf3, fq_con);
1716 degfSubLf= degf - lf;
1719 deggSubLg= degg - lg;
1721 if (lg >= 0 && deggSubLg > 0)
1723 if (repLengthBuf2 > degfSubLf + 1)
1724 degfSubLf= repLengthBuf2 - 1;
1725 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1726 _fq_nmod_vec_sub (g->coeffs + lg, g->coeffs + lg, buf1->
coeffs,
1737 _fq_nmod_vec_sub (f->coeffs + lf, f->coeffs + lf, buf2->coeffs,
1738 repLengthBuf2, fq_con);
1760 fmpz_poly_set (f, F);
1761 fmpz_poly_set (g, G);
1762 int degf= fmpz_poly_degree(f);
1763 int degg= fmpz_poly_degree(g);
1767 if (fmpz_poly_length (f) < (
long) d*(k+1))
1768 fmpz_poly_fit_length (f,(
long)d*(k+1));
1774 int degfSubLf= degf;
1775 int deggSubLg= degg-lg;
1776 int repLengthBuf2, repLengthBuf1, ind, tmp;
1778 while (degf >= lf || lg >= 0)
1782 else if (degfSubLf < 0)
1785 repLengthBuf1= degfSubLf + 1;
1787 fmpz_poly_init2 (buf1, repLengthBuf1);
1789 for (ind= 0; ind < repLengthBuf1; ind++)
1791 fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
1792 fmpz_poly_set_coeff_fmpz (buf1, ind, tmp1);
1794 _fmpz_poly_normalise (buf1);
1796 repLengthBuf1= fmpz_poly_length (buf1);
1798 if (deggSubLg >= d - 1)
1799 repLengthBuf2= d - 1;
1800 else if (deggSubLg < 0)
1803 repLengthBuf2= deggSubLg + 1;
1805 fmpz_poly_init2 (buf2, repLengthBuf2);
1807 for (ind= 0; ind < repLengthBuf2; ind++)
1809 fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1810 fmpz_poly_set_coeff_fmpz (buf2, ind, tmp1);
1813 _fmpz_poly_normalise (buf2);
1814 repLengthBuf2= fmpz_poly_length (buf2);
1816 fmpz_poly_init2 (buf3, repLengthBuf2 + d);
1817 for (ind= 0; ind < repLengthBuf1; ind++)
1819 fmpz_poly_get_coeff_fmpz (tmp1, buf1, ind);
1820 fmpz_poly_set_coeff_fmpz (buf3, ind, tmp1);
1822 for (ind= repLengthBuf1; ind < d; ind++)
1823 fmpz_poly_set_coeff_ui (buf3, ind, 0);
1824 for (ind= 0; ind < repLengthBuf2; ind++)
1826 fmpz_poly_get_coeff_fmpz (tmp1, buf2, ind);
1827 fmpz_poly_set_coeff_fmpz (buf3, ind + d, tmp1);
1829 _fmpz_poly_normalise (buf3);
1836 degfSubLf= degf - lf;
1839 deggSubLg= degg - lg;
1841 if (lg >= 0 && deggSubLg > 0)
1843 if (repLengthBuf2 > degfSubLf + 1)
1844 degfSubLf= repLengthBuf2 - 1;
1845 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
1846 for (ind= 0; ind < tmp; ind++)
1848 fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1849 fmpz_poly_get_coeff_fmpz (tmp2, buf1, ind);
1850 fmpz_sub (tmp1, tmp1, tmp2);
1851 fmpz_poly_set_coeff_fmpz (g, ind + lg, tmp1);
1856 fmpz_poly_clear (buf1);
1857 fmpz_poly_clear (buf2);
1858 fmpz_poly_clear (buf3);
1863 for (ind= 0; ind < repLengthBuf2; ind++)
1865 fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
1866 fmpz_poly_get_coeff_fmpz (tmp2, buf2, ind);
1867 fmpz_sub (tmp1, tmp1, tmp2);
1868 fmpz_poly_set_coeff_fmpz (f, ind + lf, tmp1);
1871 fmpz_poly_clear (buf1);
1872 fmpz_poly_clear (buf2);
1873 fmpz_poly_clear (buf3);
1876 fmpz_poly_clear (f);
1877 fmpz_poly_clear (g);
1884 #if ( __FLINT_RELEASE >= 20400) 1887 const fq_nmod_ctx_t
fq_con)
1895 int degf= fq_nmod_poly_degree(F, fq_con);
1897 int degfSubK, repLength;
1904 repLength= degfSubK + 1;
1906 fq_nmod_poly_init2 (buf, repLength, fq_con);
1907 _fq_nmod_poly_set_length (buf, repLength, fq_con);
1908 _fq_nmod_vec_set (buf->coeffs, F->coeffs+k, repLength, fq_con);
1909 _fq_nmod_poly_normalise (buf, fq_con);
1931 int degf= nmod_poly_degree(F);
1933 int degfSubK, repLength,
j;
1940 repLength= degfSubK + 1;
1943 for (j= 0; j < repLength; j++)
1944 nmod_poly_set_coeff_ui (buf, j, nmod_poly_get_coeff_ui (F, j + k));
1945 _nmod_poly_normalise (buf);
1971 nmod_poly_mullow (F1, F1, G1, (
long) k);
1978 int b= nmod_poly_degree (F2) + nmod_poly_degree (G2) - k - degtailF - degtailG
1979 + d1*(2+taildegF + taildegG);
1980 nmod_poly_mulhigh (F2, F2, G2, b);
1981 nmod_poly_shift_right (F2, F2, b);
1982 int d2=
tmax (nmod_poly_degree (F2)/d1, nmod_poly_degree (F1)/d1);
2001 int degAx=
degree (A, 1);
2002 int degAy=
degree (A, 2);
2003 int degBx=
degree (B, 1);
2004 int degBy=
degree (B, 2);
2005 int d1= degAx + 1 + degBx;
2006 int d2=
tmax (degAy, degBy);
2008 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (M)))
2011 nmod_poly_t FLINTA, FLINTB;
2016 nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long) k);
2025 #if ( __FLINT_RELEASE >= 20400) 2029 const fq_nmod_ctx_t
fq_con)
2035 fq_nmod_poly_t F1, F2;
2038 fq_nmod_poly_t G1, G2;
2042 fq_nmod_poly_mullow (F1, F1, G1, (
long) k, fq_con);
2049 int b= k + degtailF + degtailG - d1*(2+taildegF + taildegG);
2051 fq_nmod_poly_reverse (F2, F2, fq_nmod_poly_length (F2, fq_con), fq_con);
2052 fq_nmod_poly_reverse (G2, G2, fq_nmod_poly_length (G2, fq_con), fq_con);
2053 fq_nmod_poly_mullow (F2, F2, G2, b+1, fq_con);
2054 fq_nmod_poly_reverse (F2, F2, b+1, fq_con);
2056 int d2=
tmax (fq_nmod_poly_degree (F2, fq_con)/d1,
2057 fq_nmod_poly_degree (F1, fq_con)/d1);
2071 const fq_nmod_ctx_t
fq_con)
2076 int degAx=
degree (A, 1);
2077 int degAy=
degree (A, 2);
2078 int degBx=
degree (B, 1);
2079 int degBy=
degree (B, 2);
2080 int d1= degAx + 1 + degBx;
2081 int d2=
tmax (degAy, degBy);
2083 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (M)))
2086 fq_nmod_poly_t FLINTA, FLINTB;
2091 fq_nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (
long) k, fq_con);
2116 fmpz_poly_mullow (F1, F1, G1, (
long) k);
2123 int b= fmpz_poly_degree (F2) + fmpz_poly_degree (G2) - k - degtailF - degtailG
2124 + d1*(2+taildegF + taildegG);
2125 fmpz_poly_mulhigh_n (F2, F2, G2, b);
2126 fmpz_poly_shift_right (F2, F2, b);
2127 int d2=
tmax (fmpz_poly_degree (F2)/d1, fmpz_poly_degree (F1)/d1);
2131 fmpz_poly_clear (F1);
2132 fmpz_poly_clear (F2);
2133 fmpz_poly_clear (G1);
2134 fmpz_poly_clear (G2);
2145 int degAx=
degree (A, 1);
2146 int degBx=
degree (B, 1);
2147 int d1= degAx + 1 + degBx;
2154 fmpz_poly_t FLINTA, FLINTB;
2159 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, (
long) k);
2161 fmpz_poly_clear (FLINTA);
2162 fmpz_poly_clear (FLINTB);
2207 int degFx=
degree (F, 1);
2208 int degFa=
degree (F, a);
2209 int degGx=
degree (G, 1);
2210 int degGa=
degree (G, a);
2212 int d2= degFa+degGa+1;
2213 int d1= degFx + 1 + degGx;
2221 fmpz_poly_t FLINTF, FLINTG;
2225 fmpz_poly_mullow (FLINTF, FLINTF, FLINTG, d1*
degree (M));
2230 fmpz_poly_clear (FLINTF);
2231 fmpz_poly_clear (FLINTG);
2242 result.rep.SetLength (d*(degAy + 1));
2245 resultp= result.rep.elts();
2248 int j,
k, bufRepLength;
2252 if (
i.coeff().inCoeffDomain())
2258 bufp= buf.rep.elts();
2259 bufRepLength= (int) buf.rep.length();
2260 for (j= 0; j < bufRepLength; j++)
2261 resultp [j + k]= bufp [j];
2269 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400)) 2274 result.rep.SetLength (d*(degAy + 1));
2278 resultp= result.rep.elts();
2283 int j,
k, buf1RepLength;
2287 if (
i.coeff().inCoeffDomain())
2290 buf1= to_zz_pEX (to_zz_pE (buf2));
2296 buf1p= buf1.rep.elts();
2297 buf1RepLength= (int) buf1.rep.length();
2298 for (j= 0; j < buf1RepLength; j++)
2299 resultp [j + k]= buf1p [j];
2311 subA1.rep.SetLength ((
long) d*(degAy + 2));
2312 subA2.rep.SetLength ((
long) d*(degAy + 2));
2317 subA1p= subA1.rep.elts();
2318 subA2p= subA2.rep.elts();
2323 int j,
k, kk, bufRepLength;
2327 if (
i.coeff().inCoeffDomain())
2330 buf= to_zz_pEX (to_zz_pE (buf2));
2336 kk= (degAy -
i.exp())*d;
2337 bufp= buf.rep.elts();
2338 bufRepLength= (int) buf.rep.length();
2339 for (j= 0; j < bufRepLength; j++)
2341 subA1p [j +
k] += bufp [
j];
2342 subA2p [j + kk] += bufp [
j];
2355 subA1.rep.SetLength ((
long) d*(degAy + 2));
2356 subA2.rep.SetLength ((
long) d*(degAy + 2));
2360 subA1p= subA1.rep.elts();
2361 subA2p= subA2.rep.elts();
2364 int j,
k, kk, bufRepLength;
2371 kk= (degAy -
i.exp())*d;
2372 bufp= buf.rep.elts();
2373 bufRepLength= (int) buf.rep.length();
2374 for (j= 0; j < bufRepLength; j++)
2376 subA1p [j +
k] += bufp [
j];
2377 subA2p [j + kk] += bufp [
j];
2385 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400)) 2405 if (f.rep.length() < (long) d*(
k+1))
2406 f.rep.SetLength ((
long)d*(
k+1));
2408 zz_pE *
gp= g.rep.elts();
2409 zz_pE *
fp= f.rep.elts();
2414 int degfSubLf= degf;
2415 int deggSubLg= degg-lg;
2416 int repLengthBuf2, repLengthBuf1, ind, tmp;
2417 zz_pE zzpEZero= zz_pE();
2419 while (degf >= lf || lg >= 0)
2423 else if (degfSubLf < 0)
2426 repLengthBuf1= degfSubLf + 1;
2427 buf1.rep.SetLength((
long) repLengthBuf1);
2429 buf1p= buf1.rep.elts();
2430 for (ind= 0; ind < repLengthBuf1; ind++)
2431 buf1p [ind]= fp [ind + lf];
2434 repLengthBuf1= buf1.rep.length();
2436 if (deggSubLg >= d - 1)
2437 repLengthBuf2= d - 1;
2438 else if (deggSubLg < 0)
2441 repLengthBuf2= deggSubLg + 1;
2443 buf2.rep.SetLength ((
long) repLengthBuf2);
2444 buf2p= buf2.rep.elts();
2445 for (ind= 0; ind < repLengthBuf2; ind++)
2446 buf2p [ind]= gp [ind + lg];
2449 repLengthBuf2= buf2.rep.length();
2451 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2452 buf3p= buf3.rep.elts();
2453 buf2p= buf2.rep.elts();
2454 buf1p= buf1.rep.elts();
2455 for (ind= 0; ind < repLengthBuf1; ind++)
2456 buf3p [ind]= buf1p [ind];
2457 for (ind= repLengthBuf1; ind < d; ind++)
2458 buf3p [ind]= zzpEZero;
2459 for (ind= 0; ind < repLengthBuf2; ind++)
2460 buf3p [ind + d]= buf2p [ind];
2468 degfSubLf= degf - lf;
2471 deggSubLg= degg - lg;
2473 buf1p= buf1.rep.elts();
2475 if (lg >= 0 && deggSubLg > 0)
2477 if (repLengthBuf2 > degfSubLf + 1)
2478 degfSubLf= repLengthBuf2 - 1;
2479 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2480 for (ind= 0; ind < tmp; ind++)
2481 gp [ind + lg] -= buf1p [ind];
2487 buf2p= buf2.rep.elts();
2490 for (ind= 0; ind < repLengthBuf2; ind++)
2491 fp [ind + lf] -= buf2p [ind];
2519 if (f.rep.length() < (long) d*(k+1))
2520 f.rep.SetLength ((
long)d*(k+1));
2522 zz_p *
gp= g.rep.elts();
2523 zz_p *
fp= f.rep.elts();
2528 int degfSubLf= degf;
2529 int deggSubLg= degg-lg;
2530 int repLengthBuf2, repLengthBuf1, ind, tmp;
2531 zz_p zzpZero= zz_p();
2532 while (degf >= lf || lg >= 0)
2536 else if (degfSubLf < 0)
2539 repLengthBuf1= degfSubLf + 1;
2540 buf1.rep.SetLength((
long) repLengthBuf1);
2542 buf1p= buf1.rep.elts();
2543 for (ind= 0; ind < repLengthBuf1; ind++)
2544 buf1p [ind]= fp [ind + lf];
2547 repLengthBuf1= buf1.rep.length();
2549 if (deggSubLg >= d - 1)
2550 repLengthBuf2= d - 1;
2551 else if (deggSubLg < 0)
2554 repLengthBuf2= deggSubLg + 1;
2556 buf2.rep.SetLength ((
long) repLengthBuf2);
2557 buf2p= buf2.rep.elts();
2558 for (ind= 0; ind < repLengthBuf2; ind++)
2559 buf2p [ind]= gp [ind + lg];
2563 repLengthBuf2= buf2.rep.length();
2566 buf3.rep.SetLength((
long) repLengthBuf2 + d);
2567 buf3p= buf3.rep.elts();
2568 buf2p= buf2.rep.elts();
2569 buf1p= buf1.rep.elts();
2570 for (ind= 0; ind < repLengthBuf1; ind++)
2571 buf3p [ind]= buf1p [ind];
2572 for (ind= repLengthBuf1; ind < d; ind++)
2573 buf3p [ind]= zzpZero;
2574 for (ind= 0; ind < repLengthBuf2; ind++)
2575 buf3p [ind + d]= buf2p [ind];
2583 degfSubLf= degf - lf;
2586 deggSubLg= degg - lg;
2588 buf1p= buf1.rep.elts();
2590 if (lg >= 0 && deggSubLg > 0)
2592 if (repLengthBuf2 > degfSubLf + 1)
2593 degfSubLf= repLengthBuf2 - 1;
2594 tmp=
tmin (repLengthBuf1, deggSubLg + 1);
2595 for (ind= 0; ind < tmp; ind++)
2596 gp [ind + lg] -= buf1p [ind];
2601 buf2p= buf2.rep.elts();
2604 for (ind= 0; ind < repLengthBuf2; ind++)
2605 fp [ind + lf] -= buf2p [ind];
2613 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400)) 2620 zz_pE *
fp= f.rep.elts();
2628 int degfSubK, repLength,
j;
2635 repLength= degfSubK + 1;
2637 buf.rep.SetLength ((
long) repLength);
2638 bufp= buf.rep.elts();
2639 for (j= 0; j < repLength; j++)
2640 bufp [j]= fp [j + k];
2659 zz_p *
fp= f.rep.elts();
2667 int degfSubK, repLength,
j;
2674 repLength= degfSubK + 1;
2676 buf.rep.SetLength ((
long) repLength);
2677 bufp= buf.rep.elts();
2678 for (j= 0; j < repLength; j++)
2679 bufp [j]= fp [j + k];
2705 MulTrunc (F1, F1, G1, (
long) k);
2711 int b= k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2715 MulTrunc (F2, F2, G2, b + 1);
2718 int d2=
tmax (deg (F2)/d1, deg (F1)/d1);
2730 int degAx=
degree (A, 1);
2731 int degAy=
degree (A, 2);
2732 int degBx=
degree (B, 1);
2733 int degBy=
degree (B, 2);
2734 int d1= degAx + 1 + degBx;
2735 int d2=
tmax (degAy, degBy);
2737 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy >
degree (M)))
2738 return mulMod2NTLFpReci (A, B, M);
2744 MulTrunc (NTLA, NTLA, NTLB, (
long) k);
2752 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400)) 2768 MulTrunc (F1, F1, G1, (
long) k);
2774 int b= k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2778 MulTrunc (F2, F2, G2, b + 1);
2781 int d2=
tmax (deg (F2)/d1, deg (F1)/d1);
2802 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 2803 nmod_poly_t FLINTmipo;
2813 int degAx=
degree (A, 1);
2814 int degAy=
degree (A, 2);
2815 int degBx=
degree (B, 1);
2816 int degBy=
degree (B, 2);
2817 int d1= degAx + degBx + 1;
2818 int d2=
tmax (degAy, degBy);
2825 zz_pE::init (NTLMipo);
2828 if ((d1 > 128/degMipo) && (d2 > 160/degMipo) && (degAy == degBy) &&
2830 return mulMod2NTLFqReci (A, B, M, alpha);
2837 MulTrunc (NTLA, NTLA, NTLB, (
long) k);
2847 A= mulMod2NTLFp (A, B, M);
2863 if (F.inCoeffDomain())
2872 if ((degF < 1 && degG < 1) && (F.isUnivariate() && G.
isUnivariate()) &&
2873 (F.level() == G.
level()))
2876 return mod (result, M);
2878 else if (degF <= 1 && degG <= 1)
2881 return mod (result, M);
2884 int sizeF=
size (F);
2885 int sizeG=
size (G);
2887 int fallBackToNaive= 50;
2888 if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
2891 return mod (G*F, M);
2893 return mod (F*G, M);
2902 (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
2905 int m= (int) ceil (
degree (M)/2.0);
2906 if (degF >= m || degG >= m)
2917 return F0G0 + MLo*(F0G1 + F1G0);
2921 m= (int) ceil (
tmax (degF, degG)/2.0);
2930 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
2932 DEBOUTLN (cerr,
"fatal end in mulMod2");
2943 A=
mod (A,
i.getItem());
2964 int sizeF=
size (F);
2965 int sizeG=
size (G);
2967 if (sizeF / MOD.
length() < 100 || sizeG / MOD.
length() < 100)
2970 return mod (G*F, MOD);
2972 return mod (F*G, MOD);
2984 if (degF == 1 && degG == 1)
2995 return H11*y*y + (H01 - H00 - H11)*y + H00;
3007 else if (degF == 1 && degG == 0)
3009 else if (degF == 0 && degG == 1)
3012 return mulMod (F, G, buf);
3014 int m= (int) ceil (
degree (M)/2.0);
3015 if (degF >= m || degG >= m)
3029 return F0G0 + MLo*(F0G1 + F1G0);
3033 m= (int) ceil (
tmin (degF, degG)/2.0);
3042 return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3044 DEBOUTLN (cerr,
"fatal end in mulMod");
3064 for (
int j= 1;
j <=
l;
j++, i++)
3078 else if (L.
length() == 1)
3080 else if (L.
length() == 2)
3088 for (
int j= 1;
j <=
l;
j++, i++)
3093 return mulMod (buf1, buf2, M);
3113 while (d - i.
exp() < 0)
3121 return A*
power (x, d);
3147 for (
int i= 1;
i <=
l;
i++)
3153 g -=
power (x, (1 << (
i - 1)))*
3161 h=
mod (h,
power (x, exp + (1 <<
i)) - 1);
3216 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 3217 nmod_poly_t FLINTmipo;
3226 fq_nmod_poly_t FLINTA, FLINTB;
3230 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3239 bool zz_pEbak= zz_pE::initialized();
3247 div (NTLA, NTLA, NTLB);
3299 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 3300 nmod_poly_t FLINTmipo;
3308 fq_nmod_poly_t FLINTA, FLINTB;
3312 fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3327 DivRem (NTLQ, NTLR, NTLA, NTLB);
3349 int j= (int) floor ((
double)
degree (A)/
m);
3397 int m= (int) ceil ((
double) (degB + 1)/2.0) + 1;
3398 ASSERT (4*m >= degA,
"expected degree (F, 1) < 2*degree (G, 1)");
3400 if (splitA.
length() == 3)
3402 if (splitA.
length() == 2)
3407 if (splitA.
length() == 1)
3429 if (splitR.
length() == 1)
3468 int m= (int) ceil ((
double) (degB + 1)/ 2.0);
3469 ASSERT (3*m > degA,
"expected degree (F, 1) < 3*degree (G, 1)");
3473 if (splitA.
length() == 2)
3477 if (splitA.
length() == 1)
3504 while (
degree (R, x) >= degB)
3507 Q +=
LC (R, x)*xToM;
3508 R -=
mulMod (
LC (R, x), B, M)*xToM;
3553 if (degB >
degree (A, x))
3590 if (degB >
degree (A, x))
3652 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400) 3653 nmod_poly_t FLINTmipo;
3661 fq_nmod_poly_t FLINTA, FLINTB;
3664 int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA, fq_con);
3672 zz_pE::init (NTLMipo);
3675 return divide (NTLB, NTLA);
3679 nmod_poly_t FLINTA, FLINTB;
3682 nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3683 bool result= nmod_poly_is_zero (FLINTA);
3690 return divide (NTLB, NTLA);
3700 fmpq_poly_t FLINTA,FLINTB;
3703 fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3704 bool result= fmpq_poly_is_zero (FLINTA);
3705 fmpq_poly_clear (FLINTA);
3706 fmpq_poly_clear (FLINTB);
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...
nmod_poly_init(FLINTmipo, getCharacteristic())
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
const CanonicalForm int const CFList const Variable & y
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
Conversion to and from NTL.
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
void convertCF2Fmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t
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)
void kronSubFq(fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
some useful template functions.
functions to print debug output
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
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory's class for variables
void kronSubFp(nmod_poly_t result, const CanonicalForm &A, int d)
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...
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
CanonicalForm mulMod2FLINTFpReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
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 divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
nmod_poly_clear(FLINTmipo)
CanonicalForm reverseSubstFp(const nmod_poly_t F, int d)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CanonicalForm mulFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
void kronSubReciproFp(nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm &A, int d)
CanonicalForm reverseSubstQ(const fmpz_poly_t F, int d)
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...
static void divrem32(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
CanonicalForm mulMod2FLINTQReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
fq_nmod_ctx_clear(fq_con)
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
CanonicalForm mulMod2FLINTFp(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
CanonicalForm modFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
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), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f).
CanonicalForm reverseSubstReciproFp(const nmod_poly_t F, const nmod_poly_t G, int d, int k)
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
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, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked
The main handler for Singular numbers which are suitable for Singular polynomials.
convertFacCF2nmod_poly_t(FLINTmipo, M)
int status int void * buf
This file defines functions for fast multiplication and division with remainder.
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, 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)...
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
bool getReduce(const Variable &alpha)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo,"Z")
CanonicalForm mulFLINTQa(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
static const int SW_RATIONAL
set to 1 for computations over Q
CanonicalForm mulFLINTQaTrunc(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, int m)
CanonicalForm mulMod2FLINTQa(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
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, satisfying F=G*Q+R, deg(R) < deg(G)
CanonicalForm getpk() const
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm reverseSubstFq(const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
class to iterate through CanonicalForm's
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
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 mulMod2FLINTFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
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) ...
fq_nmod_poly_init(prod, fq_con)
CF_NO_INLINE int exp() const
get the current exponent
CanonicalForm reverseSubstReciproQ(const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
void kronSubReciproQ(fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm &A, int d)
CanonicalForm mulMod2NTLFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
CanonicalForm divFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
#define GaloisFieldDomain
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 ...
#define ASSERT(expression, message)
#define DEBOUTLN(stream, objects)
CanonicalForm reverse(const CanonicalForm &F, int d)
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
CanonicalForm mulMod2FLINTQ(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
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 ...
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
class to do operations mod p^k for int's p and k
CanonicalForm mulMod2FLINTFqReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
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 convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
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. variable alpha and polynomial variable x
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)