My Project  UNKNOWN_GIT_VERSION
Functions
facMul.h File Reference

This file defines functions for fast multiplication and division with remainder. More...

#include "canonicalform.h"
#include "fac_util.h"

Go to the source code of this file.

Functions

CanonicalForm mulNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
 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). More...
 
CanonicalForm modNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
 mod 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 More...
 
CanonicalForm divNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
 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 More...
 
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, Ziegler "Fast recursive division". More...
 
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, Ziegler "Fast recursive division". More...
 
void newtonDivrem (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 using Newton inversion More...
 
CanonicalForm newtonDiv (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 division of F by G wrt Variable (1) modulo M using Newton inversion More...
 
bool uniFdivides (const CanonicalForm &A, const CanonicalForm &B)
 divisibility test for univariate polys More...
 
CanonicalForm mulMod2 (const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
 Karatsuba style modular multiplication for bivariate polynomials. More...
 
CanonicalForm mulMod (const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
 Karatsuba style modular multiplication for multivariate polynomials. More...
 
CanonicalForm mod (const CanonicalForm &F, const CFList &M)
 reduce F modulo elements in M. More...
 
CanonicalForm prodMod (const CFList &L, const CanonicalForm &M)
 product of all elements in L modulo M via divide-and-conquer. More...
 
CanonicalForm prodMod (const CFList &L, const CFList &M)
 product of all elements in L modulo M via divide-and-conquer. More...
 
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) More...
 

Detailed Description

This file defines functions for fast multiplication and division with remainder.

Author
Martin Lee

Definition in file facMul.h.

Function Documentation

◆ divNTL()

CanonicalForm divNTL ( const CanonicalForm F,
const CanonicalForm G,
const modpk b = modpk() 
)

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

Returns
divNTL returns F/G
Parameters
[in]Fa univariate poly
[in]Ga univariate poly
[in]bcoeff bound

Definition at line 850 of file facMul.cc.

851 {
853  return div (F, G);
854  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
855  {
856  return 0;
857  }
858  else if (F.inCoeffDomain() && G.inCoeffDomain())
859  {
860  if (b.getp() != 0)
861  {
862  if (!F.inBaseDomain() || !G.inBaseDomain())
863  {
864  Variable alpha;
865  hasFirstAlgVar (F, alpha);
867 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
868  fmpz_t FLINTp;
869  fmpz_mod_poly_t FLINTmipo;
870  fq_ctx_t fq_con;
871  fq_t FLINTF, FLINTG;
872 
873  fmpz_init (FLINTp);
874  convertCF2Fmpz (FLINTp, b.getpk());
875 
876  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
877 
878  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
879 
880  convertFacCF2Fq_t (FLINTF, F, fq_con);
881  convertFacCF2Fq_t (FLINTG, G, fq_con);
882 
883  fq_inv (FLINTG, FLINTG, fq_con);
884  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
885 
887 
888  fmpz_clear (FLINTp);
889  fmpz_mod_poly_clear (FLINTmipo);
890  fq_clear (FLINTF, fq_con);
891  fq_clear (FLINTG, fq_con);
892  fq_ctx_clear (fq_con);
893  return b (result);
894 #else
895  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
896  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
897  ZZ_pE::init (NTLmipo);
898  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
899  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
900  ZZ_pE result;
901  div (result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
902  return b (convertNTLZZpX2CF (rep (result), alpha));
903 #endif
904  }
905  return b(div (F,G));
906  }
907  return div (F, G);
908  }
909  else if (F.isUnivariate() && G.inCoeffDomain())
910  {
911  if (b.getp() != 0)
912  {
913  if (!G.inBaseDomain())
914  {
915  Variable alpha;
917 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
918  fmpz_t FLINTp;
919  fmpz_mod_poly_t FLINTmipo;
920  fq_ctx_t fq_con;
921  fq_poly_t FLINTF;
922  fq_t FLINTG;
923 
924  fmpz_init (FLINTp);
925  convertCF2Fmpz (FLINTp, b.getpk());
926 
927  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
928 
929  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
930 
931  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
932  convertFacCF2Fq_t (FLINTG, G, fq_con);
933 
934  fq_inv (FLINTG, FLINTG, fq_con);
935  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
936 
938  alpha, fq_con);
939 
940  fmpz_clear (FLINTp);
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);
945  return b (result);
946 #else
947  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
948  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
949  ZZ_pE::init (NTLmipo);
950  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
951  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
952  div (NTLf, NTLf, to_ZZ_pE (NTLg));
953  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
954 #endif
955  }
956  return b(div (F,G));
957  }
958  return div (F, G);
959  }
960 
961  if (getCharacteristic() == 0)
962  {
963 
964  Variable alpha;
965  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
966  {
967 #ifdef HAVE_FLINT
968  if (b.getp() != 0)
969  {
970  fmpz_t FLINTpk;
971  fmpz_init (FLINTpk);
972  convertCF2Fmpz (FLINTpk, b.getpk());
973  fmpz_mod_poly_t FLINTF, FLINTG;
974  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
975  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
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);
981  return result;
982  }
983  return divFLINTQ (F,G);
984 #else
985  if (b.getp() != 0)
986  {
987  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
988  ZZX ZZf= convertFacCF2NTLZZX (F);
989  ZZX ZZg= convertFacCF2NTLZZX (G);
990  ZZ_pX NTLf= to_ZZ_pX (ZZf);
991  ZZ_pX NTLg= to_ZZ_pX (ZZg);
992  div (NTLf, NTLf, NTLg);
993  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
994  }
995  return div (F, G);
996 #endif
997  }
998  else
999  {
1000  if (b.getp() != 0)
1001  {
1002 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1003  fmpz_t FLINTp;
1004  fmpz_mod_poly_t FLINTmipo;
1005  fq_ctx_t fq_con;
1006  fq_poly_t FLINTF, FLINTG;
1007 
1008  fmpz_init (FLINTp);
1009  convertCF2Fmpz (FLINTp, b.getpk());
1010 
1011  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
1012 
1013  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1014 
1015  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
1016  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
1017 
1018  fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1019 
1021  alpha, fq_con);
1022 
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);
1028  return b (result);
1029 #else
1030  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1031  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
1032  ZZ_pE::init (NTLmipo);
1033  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
1034  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
1035  div (NTLf, NTLf, NTLg);
1036  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
1037 #endif
1038  }
1039 #ifdef HAVE_FLINT
1040  CanonicalForm Q;
1041  newtonDiv (F, G, Q);
1042  return Q;
1043 #else
1044  return div (F,G);
1045 #endif
1046  }
1047  }
1048 
1049  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
1050  ASSERT (F.level() == G.level(), "expected polys of same level");
1052  {
1054  zz_p::init (getCharacteristic());
1055  }
1056  Variable alpha;
1058  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
1059  {
1060 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1061  nmod_poly_t FLINTmipo;
1062  fq_nmod_ctx_t fq_con;
1063 
1064  nmod_poly_init (FLINTmipo, getCharacteristic());
1065  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
1066 
1067  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1068 
1069  fq_nmod_poly_t FLINTF, FLINTG;
1070  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
1072 
1073  fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1074 
1076 
1077  fq_nmod_poly_clear (FLINTF, fq_con);
1078  fq_nmod_poly_clear (FLINTG, fq_con);
1079  nmod_poly_clear (FLINTmipo);
1081 #else
1082  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
1083  zz_pE::init (NTLMipo);
1084  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
1085  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
1086  div (NTLF, NTLF, NTLG);
1087  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
1088 #endif
1089  }
1090  else
1091  {
1092 #ifdef HAVE_FLINT
1093  nmod_poly_t FLINTF, FLINTG;
1094  convertFacCF2nmod_poly_t (FLINTF, F);
1095  convertFacCF2nmod_poly_t (FLINTG, G);
1096  nmod_poly_div (FLINTF, FLINTF, FLINTG);
1097  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
1098  nmod_poly_clear (FLINTF);
1099  nmod_poly_clear (FLINTG);
1100 #else
1101  zz_pX NTLF= convertFacCF2NTLzzpX (F);
1102  zz_pX NTLG= convertFacCF2NTLzzpX (G);
1103  div (NTLF, NTLF, NTLG);
1104  result= convertNTLzzpX2CF(NTLF, F.mvar());
1105 #endif
1106  }
1107  return result;
1108 }

◆ divrem()

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, Ziegler "Fast recursive division".

See also
divrem2()
Parameters
[in]Fmultivariate, compressed polynomial
[in]Gmultivariate, compressed polynomial
[in,out]Qdividend
[in,out]Rremainder, degree (R, 1) < degree (G, 1)
[in]MODonly contains powers of Variables of level higher than 1

Definition at line 3583 of file facMul.cc.

3585 {
3586  CanonicalForm A= mod (F, MOD);
3587  CanonicalForm B= mod (G, MOD);
3588  Variable x= Variable (1);
3589  int degB= degree (B, x);
3590  if (degB > degree (A, x))
3591  {
3592  Q= 0;
3593  R= A;
3594  return;
3595  }
3596 
3597  if (degB <= 0)
3598  {
3599  divrem (A, B, Q, R);
3600  Q= mod (Q, MOD);
3601  R= mod (R, MOD);
3602  return;
3603  }
3604  CFList splitA= split (A, degB, x);
3605 
3606  CanonicalForm xToDegB= power (x, degB);
3607  CanonicalForm H, bufQ;
3608  Q= 0;
3609  CFListIterator i= splitA;
3610  H= i.getItem()*xToDegB;
3611  i++;
3612  H += i.getItem();
3613  while (i.hasItem())
3614  {
3615  divrem21 (H, B, bufQ, R, MOD);
3616  i++;
3617  if (i.hasItem())
3618  H= R*xToDegB + i.getItem();
3619  Q *= xToDegB;
3620  Q += bufQ;
3621  }
3622  return;
3623 }

◆ divrem2()

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, Ziegler "Fast recursive division".

Returns
Q returns the dividend, R returns the remainder.
See also
divrem()
Parameters
[in]Fbivariate, compressed polynomial
[in]Gbivariate, compressed polynomial
[in,out]Qdividend
[in,out]Rremainder, degree (R, 1) < degree (G, 1)
[in]Mpower of Variable (2)

Definition at line 3516 of file facMul.cc.

3518 {
3519  CanonicalForm A= mod (F, M);
3520  CanonicalForm B= mod (G, M);
3521 
3522  if (B.inCoeffDomain())
3523  {
3524  divrem (A, B, Q, R);
3525  return;
3526  }
3527  if (A.inCoeffDomain() && !B.inCoeffDomain())
3528  {
3529  Q= 0;
3530  R= A;
3531  return;
3532  }
3533 
3534  if (B.level() < A.level())
3535  {
3536  divrem (A, B, Q, R);
3537  return;
3538  }
3539  if (A.level() > B.level())
3540  {
3541  R= A;
3542  Q= 0;
3543  return;
3544  }
3545  if (B.level() == 1 && B.isUnivariate())
3546  {
3547  divrem (A, B, Q, R);
3548  return;
3549  }
3550 
3551  Variable x= Variable (1);
3552  int degB= degree (B, x);
3553  if (degB > degree (A, x))
3554  {
3555  Q= 0;
3556  R= A;
3557  return;
3558  }
3559 
3560  CFList splitA= split (A, degB, x);
3561 
3562  CanonicalForm xToDegB= power (x, degB);
3563  CanonicalForm H, bufQ;
3564  Q= 0;
3565  CFListIterator i= splitA;
3566  H= i.getItem()*xToDegB;
3567  i++;
3568  H += i.getItem();
3569  CFList buf;
3570  while (i.hasItem())
3571  {
3572  buf= CFList (M);
3573  divrem21 (H, B, bufQ, R, buf);
3574  i++;
3575  if (i.hasItem())
3576  H= R*xToDegB + i.getItem();
3577  Q *= xToDegB;
3578  Q += bufQ;
3579  }
3580  return;
3581 }

◆ mod()

CanonicalForm mod ( const CanonicalForm F,
const CFList M 
)

reduce F modulo elements in M.

Returns
mod returns F modulo M
Parameters
[in]Fcompressed polynomial
[in]Mlist containing only univariate polynomials

Definition at line 2939 of file facMul.cc.

2940 {
2941  CanonicalForm A= F;
2942  for (CFListIterator i= M; i.hasItem(); i++)
2943  A= mod (A, i.getItem());
2944  return A;
2945 }

◆ modNTL()

CanonicalForm modNTL ( const CanonicalForm F,
const CanonicalForm G,
const modpk b = modpk() 
)

mod 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

Returns
modNTL returns F mod G
Parameters
[in]Fa univariate poly
[in]Ga univariate poly
[in]bcoeff bound

Definition at line 676 of file facMul.cc.

677 {
679  return mod (F, G);
680  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
681  {
682  if (b.getp() != 0)
683  return b(F);
684  return F;
685  }
686  else if (F.inCoeffDomain() && G.inCoeffDomain())
687  {
688  if (b.getp() != 0)
689  return b(F%G);
690  return mod (F, G);
691  }
692  else if (F.isUnivariate() && G.inCoeffDomain())
693  {
694  if (b.getp() != 0)
695  return b(F%G);
696  return mod (F,G);
697  }
698 
699  if (getCharacteristic() == 0)
700  {
701  Variable alpha;
702  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
703  {
704 #ifdef HAVE_FLINT
705  if (b.getp() != 0)
706  {
707  fmpz_t FLINTpk;
708  fmpz_init (FLINTpk);
709  convertCF2Fmpz (FLINTpk, b.getpk());
710  fmpz_mod_poly_t FLINTF, FLINTG;
711  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
712  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
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);
718  return result;
719  }
720  return modFLINTQ (F, G);
721 #else
722  if (b.getp() != 0)
723  {
724  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
725  ZZX ZZf= convertFacCF2NTLZZX (F);
726  ZZX ZZg= convertFacCF2NTLZZX (G);
727  ZZ_pX NTLf= to_ZZ_pX (ZZf);
728  ZZ_pX NTLg= to_ZZ_pX (ZZg);
729  rem (NTLf, NTLf, NTLg);
730  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
731  }
732  return mod (F, G);
733 #endif
734  }
735  else
736  {
737  if (b.getp() != 0)
738  {
739 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
740  fmpz_t FLINTp;
741  fmpz_mod_poly_t FLINTmipo;
742  fq_ctx_t fq_con;
743  fq_poly_t FLINTF, FLINTG;
744 
745  fmpz_init (FLINTp);
746 
747  convertCF2Fmpz (FLINTp, b.getpk());
748 
749  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
750 
751  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
752 
753  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
754  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
755 
756  fq_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
757 
759  alpha, fq_con);
760 
761  fmpz_clear (FLINTp);
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);
766 
767  return b(result);
768 #else
769  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
770  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
771  ZZ_pE::init (NTLmipo);
772  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
773  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
774  rem (NTLf, NTLf, NTLg);
775  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
776 #endif
777  }
778 #ifdef HAVE_FLINT
779  CanonicalForm Q, R;
780  newtonDivrem (F, G, Q, R);
781  return R;
782 #else
783  return mod (F,G);
784 #endif
785  }
786  }
787 
788  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
789  ASSERT (F.level() == G.level(), "expected polys of same level");
791  {
793  zz_p::init (getCharacteristic());
794  }
795  Variable alpha;
797  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
798  {
799 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
800  nmod_poly_t FLINTmipo;
801  fq_nmod_ctx_t fq_con;
802 
803  nmod_poly_init (FLINTmipo, getCharacteristic());
804  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
805 
806  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
807 
808  fq_nmod_poly_t FLINTF, FLINTG;
809  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
811 
812  fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
813 
815 
816  fq_nmod_poly_clear (FLINTF, fq_con);
817  fq_nmod_poly_clear (FLINTG, fq_con);
818  nmod_poly_clear (FLINTmipo);
820 #else
821  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
822  zz_pE::init (NTLMipo);
823  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
824  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
825  rem (NTLF, NTLF, NTLG);
826  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
827 #endif
828  }
829  else
830  {
831 #ifdef HAVE_FLINT
832  nmod_poly_t FLINTF, FLINTG;
833  convertFacCF2nmod_poly_t (FLINTF, F);
834  convertFacCF2nmod_poly_t (FLINTG, G);
835  nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
836  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
837  nmod_poly_clear (FLINTF);
838  nmod_poly_clear (FLINTG);
839 #else
840  zz_pX NTLF= convertFacCF2NTLzzpX (F);
841  zz_pX NTLG= convertFacCF2NTLzzpX (G);
842  rem (NTLF, NTLF, NTLG);
843  result= convertNTLzzpX2CF(NTLF, F.mvar());
844 #endif
845  }
846  return result;
847 }

◆ mulMod()

CanonicalForm mulMod ( const CanonicalForm A,
const CanonicalForm B,
const CFList MOD 
)

Karatsuba style modular multiplication for multivariate polynomials.

Returns
mulMod2 returns A * B mod MOD.
Parameters
[in]Amultivariate, compressed polynomial
[in]Bmultivariate, compressed polynomial
[in]MODonly contains powers of Variables of level higher than 1

Definition at line 2947 of file facMul.cc.

2949 {
2950  if (A.isZero() || B.isZero())
2951  return 0;
2952 
2953  if (MOD.length() == 1)
2954  return mulMod2 (A, B, MOD.getLast());
2955 
2956  CanonicalForm M= MOD.getLast();
2957  CanonicalForm F= mod (A, M);
2958  CanonicalForm G= mod (B, M);
2959  if (F.inCoeffDomain())
2960  return G*F;
2961  if (G.inCoeffDomain())
2962  return F*G;
2963 
2964  int sizeF= size (F);
2965  int sizeG= size (G);
2966 
2967  if (sizeF / MOD.length() < 100 || sizeG / MOD.length() < 100)
2968  {
2969  if (sizeF < sizeG)
2970  return mod (G*F, MOD);
2971  else
2972  return mod (F*G, MOD);
2973  }
2974 
2975  Variable y= M.mvar();
2976  int degF= degree (F, y);
2977  int degG= degree (G, y);
2978 
2979  if ((degF <= 1 && F.level() <= M.level()) &&
2980  (degG <= 1 && G.level() <= M.level()))
2981  {
2982  CFList buf= MOD;
2983  buf.removeLast();
2984  if (degF == 1 && degG == 1)
2985  {
2986  CanonicalForm F0= mod (F, y);
2987  CanonicalForm F1= div (F, y);
2988  CanonicalForm G0= mod (G, y);
2989  CanonicalForm G1= div (G, y);
2990  if (degree (M) > 2)
2991  {
2992  CanonicalForm H00= mulMod (F0, G0, buf);
2993  CanonicalForm H11= mulMod (F1, G1, buf);
2994  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, buf);
2995  return H11*y*y + (H01 - H00 - H11)*y + H00;
2996  }
2997  else //here degree (M) == 2
2998  {
2999  buf.append (y);
3000  CanonicalForm F0G1= mulMod (F0, G1, buf);
3001  CanonicalForm F1G0= mulMod (F1, G0, buf);
3002  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3003  CanonicalForm result= F0G0 + y*(F0G1 + F1G0);
3004  return result;
3005  }
3006  }
3007  else if (degF == 1 && degG == 0)
3008  return mulMod (div (F, y), G, buf)*y + mulMod (mod (F, y), G, buf);
3009  else if (degF == 0 && degG == 1)
3010  return mulMod (div (G, y), F, buf)*y + mulMod (mod (G, y), F, buf);
3011  else
3012  return mulMod (F, G, buf);
3013  }
3014  int m= (int) ceil (degree (M)/2.0);
3015  if (degF >= m || degG >= m)
3016  {
3017  CanonicalForm MLo= power (y, m);
3018  CanonicalForm MHi= power (y, degree (M) - m);
3019  CanonicalForm F0= mod (F, MLo);
3020  CanonicalForm F1= div (F, MLo);
3021  CanonicalForm G0= mod (G, MLo);
3022  CanonicalForm G1= div (G, MLo);
3023  CFList buf= MOD;
3024  buf.removeLast();
3025  buf.append (MHi);
3026  CanonicalForm F0G1= mulMod (F0, G1, buf);
3027  CanonicalForm F1G0= mulMod (F1, G0, buf);
3028  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3029  return F0G0 + MLo*(F0G1 + F1G0);
3030  }
3031  else
3032  {
3033  m= (tmax(degF, degG)+1)/2;
3034  CanonicalForm yToM= power (y, m);
3035  CanonicalForm F0= mod (F, yToM);
3036  CanonicalForm F1= div (F, yToM);
3037  CanonicalForm G0= mod (G, yToM);
3038  CanonicalForm G1= div (G, yToM);
3039  CanonicalForm H00= mulMod (F0, G0, MOD);
3040  CanonicalForm H11= mulMod (F1, G1, MOD);
3041  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, MOD);
3042  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3043  }
3044  DEBOUTLN (cerr, "fatal end in mulMod");
3045 }

◆ mulMod2()

Karatsuba style modular multiplication for bivariate polynomials.

Returns
mulMod2 returns A * B mod M.
Parameters
[in]Abivariate, compressed polynomial
[in]Bbivariate, compressed polynomial
[in]Mpower of Variable (2)

Definition at line 2853 of file facMul.cc.

2855 {
2856  if (A.isZero() || B.isZero())
2857  return 0;
2858 
2859  ASSERT (M.isUnivariate(), "M must be univariate");
2860 
2861  CanonicalForm F= mod (A, M);
2862  CanonicalForm G= mod (B, M);
2863  if (F.inCoeffDomain())
2864  return G*F;
2865  if (G.inCoeffDomain())
2866  return F*G;
2867 
2868  Variable y= M.mvar();
2869  int degF= degree (F, y);
2870  int degG= degree (G, y);
2871 
2872  if ((degF < 1 && degG < 1) && (F.isUnivariate() && G.isUnivariate()) &&
2873  (F.level() == G.level()))
2874  {
2875  CanonicalForm result= mulNTL (F, G);
2876  return mod (result, M);
2877  }
2878  else if (degF <= 1 && degG <= 1)
2879  {
2880  CanonicalForm result= F*G;
2881  return mod (result, M);
2882  }
2883 
2884  int sizeF= size (F);
2885  int sizeG= size (G);
2886 
2887  int fallBackToNaive= 50;
2888  if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
2889  {
2890  if (sizeF < sizeG)
2891  return mod (G*F, M);
2892  else
2893  return mod (F*G, M);
2894  }
2895 
2896 #ifdef HAVE_FLINT
2897  if (getCharacteristic() == 0)
2898  return mulMod2FLINTQa (F, G, M);
2899 #endif
2900 
2902  (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
2903  return mulMod2NTLFq (F, G, M);
2904 
2905  int m= (int) ceil (degree (M)/2.0);
2906  if (degF >= m || degG >= m)
2907  {
2908  CanonicalForm MLo= power (y, m);
2909  CanonicalForm MHi= power (y, degree (M) - m);
2910  CanonicalForm F0= mod (F, MLo);
2911  CanonicalForm F1= div (F, MLo);
2912  CanonicalForm G0= mod (G, MLo);
2913  CanonicalForm G1= div (G, MLo);
2914  CanonicalForm F0G1= mulMod2 (F0, G1, MHi);
2915  CanonicalForm F1G0= mulMod2 (F1, G0, MHi);
2916  CanonicalForm F0G0= mulMod2 (F0, G0, M);
2917  return F0G0 + MLo*(F0G1 + F1G0);
2918  }
2919  else
2920  {
2921  m= (int) ceil (tmax (degF, degG)/2.0);
2922  CanonicalForm yToM= power (y, m);
2923  CanonicalForm F0= mod (F, yToM);
2924  CanonicalForm F1= div (F, yToM);
2925  CanonicalForm G0= mod (G, yToM);
2926  CanonicalForm G1= div (G, yToM);
2927  CanonicalForm H00= mulMod2 (F0, G0, M);
2928  CanonicalForm H11= mulMod2 (F1, G1, M);
2929  CanonicalForm H01= mulMod2 (F0 + F1, G0 + G1, M);
2930  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
2931  }
2932  DEBOUTLN (cerr, "fatal end in mulMod2");
2933 }

◆ mulNTL()

CanonicalForm mulNTL ( const CanonicalForm F,
const CanonicalForm G,
const modpk b = modpk() 
)

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).

Returns
mulNTL returns F*G
Parameters
[in]Fa univariate poly
[in]Ga univariate poly
[in]bcoeff bound

Definition at line 407 of file facMul.cc.

408 {
410  return F*G;
411  if (getCharacteristic() == 0)
412  {
413  Variable alpha;
414  if ((!F.inCoeffDomain() && !G.inCoeffDomain()) &&
416  {
417  if (b.getp() != 0)
418  {
420  bool is_rat= isOn (SW_RATIONAL);
421  if (!is_rat)
422  On (SW_RATIONAL);
423  mipo *=bCommonDen (mipo);
424  if (!is_rat)
425  Off (SW_RATIONAL);
426 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
427  fmpz_t FLINTp;
428  fmpz_mod_poly_t FLINTmipo;
429  fq_ctx_t fq_con;
430  fq_poly_t FLINTF, FLINTG;
431 
432  fmpz_init (FLINTp);
433 
434  convertCF2Fmpz (FLINTp, b.getpk());
435 
436  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
437 
438  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
439 
440  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
441  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
442 
443  fq_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
444 
446  alpha, fq_con);
447 
448  fmpz_clear (FLINTp);
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);
453  return b (result);
454 #else
455  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
456  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (mipo));
457  ZZ_pE::init (NTLmipo);
458  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
459  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
460  mul (NTLf, NTLf, NTLg);
461 
462  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
463 #endif
464  }
465 #ifdef HAVE_FLINT
467  return result;
468 #else
469  return F*G;
470 #endif
471  }
472  else if (!F.inCoeffDomain() && !G.inCoeffDomain())
473  {
474 #ifdef HAVE_FLINT
475  if (b.getp() != 0)
476  {
477  fmpz_t FLINTpk;
478  fmpz_init (FLINTpk);
479  convertCF2Fmpz (FLINTpk, b.getpk());
480  fmpz_mod_poly_t FLINTF, FLINTG;
481  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
482  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
483  fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
485  fmpz_mod_poly_clear (FLINTG);
486  fmpz_mod_poly_clear (FLINTF);
487  fmpz_clear (FLINTpk);
488  return result;
489  }
490  return mulFLINTQ (F, G);
491 #else
492  if (b.getp() != 0)
493  {
494  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
495  ZZX ZZf= convertFacCF2NTLZZX (F);
496  ZZX ZZg= convertFacCF2NTLZZX (G);
497  ZZ_pX NTLf= to_ZZ_pX (ZZf);
498  ZZ_pX NTLg= to_ZZ_pX (ZZg);
499  mul (NTLf, NTLf, NTLg);
500  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
501  }
502  return F*G;
503 #endif
504  }
505  if (b.getp() != 0)
506  {
507  if (!F.inBaseDomain() && !G.inBaseDomain())
508  {
509  if (hasFirstAlgVar (G, alpha) || hasFirstAlgVar (F, alpha))
510  {
511 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
512  fmpz_t FLINTp;
513  fmpz_mod_poly_t FLINTmipo;
514  fq_ctx_t fq_con;
515 
516  fmpz_init (FLINTp);
517  convertCF2Fmpz (FLINTp, b.getpk());
518 
519  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
520 
521  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
522 
524 
525  if (F.inCoeffDomain() && !G.inCoeffDomain())
526  {
527  fq_poly_t FLINTG;
528  fmpz_poly_t FLINTF;
529  convertFacCF2Fmpz_poly_t (FLINTF, F);
530  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
531 
532  fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF, fq_con);
533 
534  result= convertFq_poly_t2FacCF (FLINTG, G.mvar(), alpha, fq_con);
535  fmpz_poly_clear (FLINTF);
536  fq_poly_clear (FLINTG, fq_con);
537  }
538  else if (!F.inCoeffDomain() && G.inCoeffDomain())
539  {
540  fq_poly_t FLINTF;
541  fmpz_poly_t FLINTG;
542 
543  convertFacCF2Fmpz_poly_t (FLINTG, G);
544  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
545 
546  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
547 
548  result= convertFq_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
549  fmpz_poly_clear (FLINTG);
550  fq_poly_clear (FLINTF, fq_con);
551  }
552  else
553  {
554  fq_t FLINTF, FLINTG;
555 
556  convertFacCF2Fq_t (FLINTF, F, fq_con);
557  convertFacCF2Fq_t (FLINTG, G, fq_con);
558 
559  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
560 
561  result= convertFq_t2FacCF (FLINTF, alpha);
562  fq_clear (FLINTF, fq_con);
563  fq_clear (FLINTG, fq_con);
564  }
565 
566  fmpz_clear (FLINTp);
567  fmpz_mod_poly_clear (FLINTmipo);
568  fq_ctx_clear (fq_con);
569 
570  return b (result);
571 #else
572  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
573  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
574  ZZ_pE::init (NTLmipo);
575 
576  if (F.inCoeffDomain() && !G.inCoeffDomain())
577  {
578  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
579  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
580  mul (NTLg, to_ZZ_pE (NTLf), NTLg);
581  return b (convertNTLZZ_pEX2CF (NTLg, G.mvar(), alpha));
582  }
583  else if (!F.inCoeffDomain() && G.inCoeffDomain())
584  {
585  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
586  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
587  mul (NTLf, NTLf, to_ZZ_pE (NTLg));
588  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
589  }
590  else
591  {
592  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
593  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
594  ZZ_pE result;
595  mul (result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
596  return b (convertNTLZZpX2CF (rep (result), alpha));
597  }
598 #endif
599  }
600  }
601  return b (F*G);
602  }
603  return F*G;
604  }
605  else if (F.inCoeffDomain() || G.inCoeffDomain())
606  return F*G;
607  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
608  ASSERT (F.level() == G.level(), "expected polys of same level");
610  {
612  zz_p::init (getCharacteristic());
613  }
614  Variable alpha;
616  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
617  {
618  if (!getReduce (alpha))
619  {
620  result= 0;
621  for (CFIterator i= F; i.hasTerms(); i++)
622  result += i.coeff()*G*power (F.mvar(),i.exp());
623  return result;
624  }
625 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
626  nmod_poly_t FLINTmipo;
627  fq_nmod_ctx_t fq_con;
628 
629  nmod_poly_init (FLINTmipo, getCharacteristic());
630  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
631 
632  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
633 
634  fq_nmod_poly_t FLINTF, FLINTG;
635  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
637 
638  fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
639 
641 
642  fq_nmod_poly_clear (FLINTF, fq_con);
643  fq_nmod_poly_clear (FLINTG, fq_con);
644  nmod_poly_clear (FLINTmipo);
646 #else
647  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
648  zz_pE::init (NTLMipo);
649  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
650  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
651  mul (NTLF, NTLF, NTLG);
652  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
653 #endif
654  }
655  else
656  {
657 #ifdef HAVE_FLINT
658  nmod_poly_t FLINTF, FLINTG;
659  convertFacCF2nmod_poly_t (FLINTF, F);
660  convertFacCF2nmod_poly_t (FLINTG, G);
661  nmod_poly_mul (FLINTF, FLINTF, FLINTG);
662  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
663  nmod_poly_clear (FLINTF);
664  nmod_poly_clear (FLINTG);
665 #else
666  zz_pX NTLF= convertFacCF2NTLzzpX (F);
667  zz_pX NTLG= convertFacCF2NTLzzpX (G);
668  mul (NTLF, NTLF, NTLG);
669  result= convertNTLzzpX2CF(NTLF, F.mvar());
670 #endif
671  }
672  return result;
673 }

◆ newtonDiv()

division of F by G wrt Variable (1) modulo M using Newton inversion

Returns
newtonDiv returns the dividend
See also
divrem2(), newtonDivrem()
Parameters
[in]Fbivariate, compressed polynomial
[in]Gbivariate, compressed polynomial which is monic in Variable (1)
[in]Mpower of Variable (2)

Definition at line 3180 of file facMul.cc.

3182 {
3183  ASSERT (getCharacteristic() > 0, "positive characteristic expected");
3184 
3185  CanonicalForm A= mod (F, M);
3186  CanonicalForm B= mod (G, M);
3187 
3188  Variable x= Variable (1);
3189  int degA= degree (A, x);
3190  int degB= degree (B, x);
3191  int m= degA - degB;
3192  if (m < 0)
3193  return 0;
3194 
3195  Variable v;
3196  CanonicalForm Q;
3197  if (degB < 1 || CFFactory::gettype() == GaloisFieldDomain)
3198  {
3199  CanonicalForm R;
3200  divrem2 (A, B, Q, R, M);
3201  }
3202  else
3203  {
3204  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3205  {
3206  CanonicalForm R= reverse (A, degA);
3207  CanonicalForm revB= reverse (B, degB);
3208  revB= newtonInverse (revB, m + 1, M);
3209  Q= mulMod2 (R, revB, M);
3210  Q= mod (Q, power (x, m + 1));
3211  Q= reverse (Q, m);
3212  }
3213  else
3214  {
3215  Variable y= Variable (2);
3216 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3217  nmod_poly_t FLINTmipo;
3218  fq_nmod_ctx_t fq_con;
3219 
3220  nmod_poly_init (FLINTmipo, getCharacteristic());
3221  convertFacCF2nmod_poly_t (FLINTmipo, M);
3222 
3223  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3224 
3225 
3226  fq_nmod_poly_t FLINTA, FLINTB;
3227  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3228  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3229 
3230  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3231 
3232  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3233 
3234  fq_nmod_poly_clear (FLINTA, fq_con);
3235  fq_nmod_poly_clear (FLINTB, fq_con);
3236  nmod_poly_clear (FLINTmipo);
3238 #else
3239  bool zz_pEbak= zz_pE::initialized();
3240  zz_pEBak bak;
3241  if (zz_pEbak)
3242  bak.save();
3243  zz_pX mipo= convertFacCF2NTLzzpX (M);
3244  zz_pEX NTLA, NTLB;
3245  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3246  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3247  div (NTLA, NTLA, NTLB);
3248  Q= convertNTLzz_pEX2CF (NTLA, x, y);
3249  if (zz_pEbak)
3250  bak.restore();
3251 #endif
3252  }
3253  }
3254 
3255  return Q;
3256 }

◆ newtonDivrem() [1/2]

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)

Parameters
[in]Funivariate poly
[in]Gunivariate poly
[in,out]Qquotient
[in,out]Rremainder

Definition at line 342 of file facMul.cc.

344 {
345  ASSERT (F.level() == G.level(), "F and G have different level");
346  CanonicalForm A= F;
347  CanonicalForm B= G;
348  Variable x= A.mvar();
349  int degA= degree (A);
350  int degB= degree (B);
351  int m= degA - degB;
352 
353  if (m < 0)
354  {
355  R= A;
356  Q= 0;
357  return;
358  }
359 
360  if (degB <= 1)
361  divrem (A, B, Q, R);
362  else
363  {
364  R= uniReverse (A, degA, x);
365 
366  CanonicalForm revB= uniReverse (B, degB, x);
367  revB= newtonInverse (revB, m + 1, x);
368  Q= mulFLINTQTrunc (R, revB, m + 1);
369  Q= uniReverse (Q, m, x);
370 
371  R= A - mulNTL (Q, B);
372  }
373 }

◆ newtonDivrem() [2/2]

void newtonDivrem ( 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 using Newton inversion

Returns
Q returns the dividend, R returns the remainder.
See also
divrem2(), newtonDiv()
Parameters
[in]Fbivariate, compressed polynomial
[in]Gbivariate, compressed polynomial which is monic in Variable (1)
[in,out]Qdividend
[in,out]Rremainder, degree (R, 1) < degree (G, 1)
[in]Mpower of Variable (2)

Definition at line 3259 of file facMul.cc.

3261 {
3262  CanonicalForm A= mod (F, M);
3263  CanonicalForm B= mod (G, M);
3264  Variable x= Variable (1);
3265  int degA= degree (A, x);
3266  int degB= degree (B, x);
3267  int m= degA - degB;
3268 
3269  if (m < 0)
3270  {
3271  R= A;
3272  Q= 0;
3273  return;
3274  }
3275 
3276  Variable v;
3277  if (degB <= 1 || CFFactory::gettype() == GaloisFieldDomain)
3278  {
3279  divrem2 (A, B, Q, R, M);
3280  }
3281  else
3282  {
3283  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3284  {
3285  R= reverse (A, degA);
3286 
3287  CanonicalForm revB= reverse (B, degB);
3288  revB= newtonInverse (revB, m + 1, M);
3289  Q= mulMod2 (R, revB, M);
3290 
3291  Q= mod (Q, power (x, m + 1));
3292  Q= reverse (Q, m);
3293 
3294  R= A - mulMod2 (Q, B, M);
3295  }
3296  else
3297  {
3298  Variable y= Variable (2);
3299 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3300  nmod_poly_t FLINTmipo;
3301  fq_nmod_ctx_t fq_con;
3302 
3303  nmod_poly_init (FLINTmipo, getCharacteristic());
3304  convertFacCF2nmod_poly_t (FLINTmipo, M);
3305 
3306  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3307 
3308  fq_nmod_poly_t FLINTA, FLINTB;
3309  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3310  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3311 
3312  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3313 
3314  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3315  R= convertFq_nmod_poly_t2FacCF (FLINTB, x, y, fq_con);
3316 
3317  fq_nmod_poly_clear (FLINTA, fq_con);
3318  fq_nmod_poly_clear (FLINTB, fq_con);
3319  nmod_poly_clear (FLINTmipo);
3321 #else
3322  zz_pX mipo= convertFacCF2NTLzzpX (M);
3323  zz_pEX NTLA, NTLB;
3324  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3325  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3326  zz_pEX NTLQ, NTLR;
3327  DivRem (NTLQ, NTLR, NTLA, NTLB);
3328  Q= convertNTLzz_pEX2CF (NTLQ, x, y);
3329  R= convertNTLzz_pEX2CF (NTLR, x, y);
3330 #endif
3331  }
3332  }
3333 }

◆ prodMod() [1/2]

CanonicalForm prodMod ( const CFList L,
const CanonicalForm M 
)

product of all elements in L modulo M via divide-and-conquer.

Returns
prodMod returns product of all elements in L modulo M.
Parameters
[in]Lcontains only bivariate, compressed polynomials
[in]Mpower of Variable (2)

Definition at line 3047 of file facMul.cc.

3048 {
3049  if (L.isEmpty())
3050  return 1;
3051  int l= L.length();
3052  if (l == 1)
3053  return mod (L.getFirst(), M);
3054  else if (l == 2) {
3056  return result;
3057  }
3058  else
3059  {
3060  l /= 2;
3061  CFList tmp1, tmp2;
3062  CFListIterator i= L;
3064  for (int j= 1; j <= l; j++, i++)
3065  tmp1.append (i.getItem());
3066  tmp2= Difference (L, tmp1);
3067  buf1= prodMod (tmp1, M);
3068  buf2= prodMod (tmp2, M);
3070  return result;
3071  }
3072 }

◆ prodMod() [2/2]

CanonicalForm prodMod ( const CFList L,
const CFList M 
)

product of all elements in L modulo M via divide-and-conquer.

Returns
prodMod returns product of all elements in L modulo M.
Parameters
[in]Lcontains multivariate, compressed polynomials
[in]Mcontains only powers of Variables

Definition at line 3074 of file facMul.cc.

3075 {
3076  if (L.isEmpty())
3077  return 1;
3078  else if (L.length() == 1)
3079  return L.getFirst();
3080  else if (L.length() == 2)
3081  return mulMod (L.getFirst(), L.getLast(), M);
3082  else
3083  {
3084  int l= L.length()/2;
3085  CFListIterator i= L;
3086  CFList tmp1, tmp2;
3088  for (int j= 1; j <= l; j++, i++)
3089  tmp1.append (i.getItem());
3090  tmp2= Difference (L, tmp1);
3091  buf1= prodMod (tmp1, M);
3092  buf2= prodMod (tmp2, M);
3093  return mulMod (buf1, buf2, M);
3094  }
3095 }

◆ uniFdivides()

bool uniFdivides ( const CanonicalForm A,
const CanonicalForm B 
)

divisibility test for univariate polys

Returns
uniFdivides returns true if A divides B
Parameters
[in]Aunivariate poly
[in]Bunivariate poly

Definition at line 3626 of file facMul.cc.

3627 {
3628  if (B.isZero())
3629  return true;
3630  if (A.isZero())
3631  return false;
3633  return fdivides (A, B);
3634  int p= getCharacteristic();
3635  if (A.inCoeffDomain() || B.inCoeffDomain())
3636  {
3637  if (A.inCoeffDomain())
3638  return true;
3639  else
3640  return false;
3641  }
3642  if (p > 0)
3643  {
3644  if (fac_NTL_char != p)
3645  {
3646  fac_NTL_char= p;
3647  zz_p::init (p);
3648  }
3649  Variable alpha;
3650  if (hasFirstAlgVar (A, alpha) || hasFirstAlgVar (B, alpha))
3651  {
3652 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3653  nmod_poly_t FLINTmipo;
3654  fq_nmod_ctx_t fq_con;
3655 
3656  nmod_poly_init (FLINTmipo, getCharacteristic());
3657  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
3658 
3659  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3660 
3661  fq_nmod_poly_t FLINTA, FLINTB;
3664  int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA, fq_con);
3665  fq_nmod_poly_clear (FLINTA, fq_con);
3666  fq_nmod_poly_clear (FLINTB, fq_con);
3667  nmod_poly_clear (FLINTmipo);
3669  return result;
3670 #else
3671  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3672  zz_pE::init (NTLMipo);
3673  zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
3674  zz_pEX NTLB= convertFacCF2NTLzz_pEX (B, NTLMipo);
3675  return divide (NTLB, NTLA);
3676 #endif
3677  }
3678 #ifdef HAVE_FLINT
3679  nmod_poly_t FLINTA, FLINTB;
3680  convertFacCF2nmod_poly_t (FLINTA, A);
3681  convertFacCF2nmod_poly_t (FLINTB, B);
3682  nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3683  bool result= nmod_poly_is_zero (FLINTA);
3684  nmod_poly_clear (FLINTA);
3685  nmod_poly_clear (FLINTB);
3686  return result;
3687 #else
3688  zz_pX NTLA= convertFacCF2NTLzzpX (A);
3689  zz_pX NTLB= convertFacCF2NTLzzpX (B);
3690  return divide (NTLB, NTLA);
3691 #endif
3692  }
3693 #ifdef HAVE_FLINT
3694  Variable alpha;
3695  bool isRat= isOn (SW_RATIONAL);
3696  if (!isRat)
3697  On (SW_RATIONAL);
3698  if (!hasFirstAlgVar (A, alpha) && !hasFirstAlgVar (B, alpha))
3699  {
3700  fmpq_poly_t FLINTA,FLINTB;
3701  convertFacCF2Fmpq_poly_t (FLINTA, A);
3702  convertFacCF2Fmpq_poly_t (FLINTB, B);
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);
3707  if (!isRat)
3708  Off (SW_RATIONAL);
3709  return result;
3710  }
3711  CanonicalForm Q, R;
3712  newtonDivrem (B, A, Q, R);
3713  if (!isRat)
3714  Off (SW_RATIONAL);
3715  return R.isZero();
3716 #else
3717  bool isRat= isOn (SW_RATIONAL);
3718  if (!isRat)
3719  On (SW_RATIONAL);
3720  bool result= fdivides (A, B);
3721  if (!isRat)
3722  Off (SW_RATIONAL);
3723  return result; //maybe NTL?
3724 #endif
3725 }
prodMod
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
convertnmod_poly_t2FacCF
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
Definition: FLINTconvert.cc:137
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
j
int j
Definition: facHensel.cc:105
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
result
return result
Definition: facAbsBiFact.cc:76
convertFacCF2NTLZZ_pEX
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
Definition: NTLconvert.cc:1036
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
convertCF2Fmpz
void convertCF2Fmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t
Definition: FLINTconvert.cc:61
convertNTLZZ_pEX2CF
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1114
fq_con
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
convertFacCF2Fq_t
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
Definition: FLINTconvert.cc:348
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
divrem
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,...
Definition: facMul.cc:3583
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
convertNTLZZpX2CF
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
Definition: NTLconvert.cc:243
CanonicalForm
factory's main class
Definition: canonicalform.h:83
mulFLINTQ
CanonicalForm mulFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:129
amp::ceil
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:789
modFLINTQ
CanonicalForm modFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:188
convertFacCF2Fq_nmod_poly_t
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
Definition: FLINTconvert.cc:385
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
convertFq_nmod_poly_t2FacCF
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...
Definition: FLINTconvert.cc:423
i
int i
Definition: cfEzgcd.cc:125
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
mulNTL
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),...
Definition: facMul.cc:407
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
M
#define M
Definition: sirandom.c:24
buf
int status int void * buf
Definition: si_signals.h:59
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
convertNTLzz_pEX2CF
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
mulMod2FLINTQa
CanonicalForm mulMod2FLINTQa(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2199
buf1
CanonicalForm buf1
Definition: facFqBivar.cc:71
mulFLINTQTrunc
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
Definition: facMul.cc:237
tmp1
CFList tmp1
Definition: facFqBivar.cc:70
convertFacCF2NTLZZpX
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
Definition: NTLconvert.cc:59
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
mulMod2
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
newtonDivrem
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,...
Definition: facMul.cc:342
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
mulFLINTQa
CanonicalForm mulFLINTQa(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
Definition: facMul.cc:99
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
divrem2
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,...
Definition: facMul.cc:3516
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
convertFacCF2Fmpq_poly_t
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
Definition: FLINTconvert.cc:238
split
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3336
div
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs )
Definition: cf_inline.cc:553
convertFacCF2Fmpz_mod_poly_t
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)
Definition: FLINTconvert.cc:293
mulMod
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
newtonDiv
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition: facMul.cc:376
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
divide
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
Definition: facAlgFuncUtil.cc:500
List::length
int length() const
Definition: ftmpl_list.cc:273
Variable
factory's class for variables
Definition: factory.h:118
mulMod2NTLFq
CanonicalForm mulMod2NTLFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2793
divFLINTQ
CanonicalForm divFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:170
B
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
mod
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
m
int m
Definition: cfEzgcd.cc:121
divrem21
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3376
l
int l
Definition: cfEzgcd.cc:93
reverse
CanonicalForm reverse(const CanonicalForm &F, int d)
Definition: facMul.cc:3101
convertFq_poly_t2FacCF
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....
Definition: FLINTconvert.cc:402
R
#define R
Definition: sirandom.c:26
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:278
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List< CanonicalForm >
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
H
CanonicalForm H
Definition: facAbsFact.cc:64
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
uniReverse
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
Definition: facMul.cc:270
convertFq_t2FacCF
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....
Definition: FLINTconvert.cc:361
newtonInverse
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:287
convertFacCF2Fq_poly_t
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
Definition: FLINTconvert.cc:367
Q
#define Q
Definition: sirandom.c:25
fq_nmod_poly_clear
fq_nmod_poly_clear(prod, fq_con)
getReduce
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
convertFacCF2Fmpz_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
Definition: FLINTconvert.cc:74
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
convertFacCF2NTLZZ
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:664
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
A
#define A
Definition: sirandom.c:23
buf2
CanonicalForm buf2
Definition: facFqBivar.cc:71
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
rem
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
convertFmpz_mod_poly_t2FacCF
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
Definition: FLINTconvert.cc:304
ListIterator
Definition: ftmpl_list.h:87