My Project
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 FACTORY_PUBLIC 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 936 of file facMul.cc.

937 {
939  return div (F, G);
940  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
941  {
942  return 0;
943  }
944  else if (F.inCoeffDomain() && G.inCoeffDomain())
945  {
946  if (b.getp() != 0)
947  {
948  if (!F.inBaseDomain() || !G.inBaseDomain())
949  {
950  Variable alpha;
951  hasFirstAlgVar (F, alpha);
953 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
954  fmpz_t FLINTp;
955  fmpz_mod_poly_t FLINTmipo;
956  fq_ctx_t fq_con;
957  fq_t FLINTF, FLINTG;
958 
959  fmpz_init (FLINTp);
960  convertCF2initFmpz (FLINTp, b.getpk());
961 
962  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
963 
964  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
965  fmpz_mod_ctx_t fmpz_ctx;
966  fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
967  fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
968  #else
969  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
970  #endif
971 
972  convertFacCF2Fq_t (FLINTF, F, fq_con);
973  convertFacCF2Fq_t (FLINTG, G, fq_con);
974 
975  fq_inv (FLINTG, FLINTG, fq_con);
976  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
977 
979 
980  fmpz_clear (FLINTp);
981  fq_clear (FLINTF, fq_con);
982  fq_clear (FLINTG, fq_con);
983  fq_ctx_clear (fq_con);
984  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
985  fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
986  fmpz_mod_ctx_clear(fmpz_ctx);
987  #else
988  fmpz_mod_poly_clear (FLINTmipo);
989  #endif
990  return b (result);
991 #else
992  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
993  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
994  ZZ_pE::init (NTLmipo);
995  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
996  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
997  ZZ_pE result;
998  div (result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
999  return b (convertNTLZZpX2CF (rep (result), alpha));
1000 #endif
1001  }
1002  return b(div (F,G));
1003  }
1004  return div (F, G);
1005  }
1006  else if (F.isUnivariate() && G.inCoeffDomain())
1007  {
1008  if (b.getp() != 0)
1009  {
1010  if (!G.inBaseDomain())
1011  {
1012  Variable alpha;
1013  hasFirstAlgVar (G, alpha);
1014 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1015  fmpz_t FLINTp;
1016  fmpz_mod_poly_t FLINTmipo;
1017  fq_ctx_t fq_con;
1018  fq_poly_t FLINTF;
1019  fq_t FLINTG;
1020 
1021  fmpz_init (FLINTp);
1022  convertCF2initFmpz (FLINTp, b.getpk());
1023 
1024  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
1025 
1026  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1027  fmpz_mod_ctx_t fmpz_ctx;
1028  fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1029  fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
1030  #else
1031  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1032  #endif
1033 
1034  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
1035  convertFacCF2Fq_t (FLINTG, G, fq_con);
1036 
1037  fq_inv (FLINTG, FLINTG, fq_con);
1038  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
1039 
1041  alpha, fq_con);
1042 
1043  fmpz_clear (FLINTp);
1044  fq_poly_clear (FLINTF, fq_con);
1045  fq_clear (FLINTG, fq_con);
1046  fq_ctx_clear (fq_con);
1047  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1048  fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1049  fmpz_mod_ctx_clear(fmpz_ctx);
1050  #else
1051  fmpz_mod_poly_clear (FLINTmipo);
1052  #endif
1053  return b (result);
1054 #else
1055  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1056  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
1057  ZZ_pE::init (NTLmipo);
1058  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
1059  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
1060  div (NTLf, NTLf, to_ZZ_pE (NTLg));
1061  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
1062 #endif
1063  }
1064  return b(div (F,G));
1065  }
1066  return div (F, G);
1067  }
1068 
1069  if (getCharacteristic() == 0)
1070  {
1071 
1072  Variable alpha;
1073  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
1074  {
1075 #ifdef HAVE_FLINT
1076  if (b.getp() != 0)
1077  {
1078  fmpz_t FLINTpk;
1079  fmpz_init (FLINTpk);
1080  convertCF2initFmpz (FLINTpk, b.getpk());
1081  fmpz_mod_poly_t FLINTF, FLINTG;
1082  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
1083  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
1084  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1085  fmpz_mod_ctx_t fmpz_ctx;
1086  fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
1087  fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fmpz_ctx);
1088  #else
1089  fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
1090  #endif
1092  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1093  fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
1094  fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
1095  fmpz_mod_ctx_clear(fmpz_ctx);
1096  #else
1097  fmpz_mod_poly_clear (FLINTG);
1098  fmpz_mod_poly_clear (FLINTF);
1099  #endif
1100  fmpz_clear (FLINTpk);
1101  return result;
1102  }
1103  return divFLINTQ (F,G);
1104 #else
1105  if (b.getp() != 0)
1106  {
1107  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1108  ZZX ZZf= convertFacCF2NTLZZX (F);
1109  ZZX ZZg= convertFacCF2NTLZZX (G);
1110  ZZ_pX NTLf= to_ZZ_pX (ZZf);
1111  ZZ_pX NTLg= to_ZZ_pX (ZZg);
1112  div (NTLf, NTLf, NTLg);
1113  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
1114  }
1115  return div (F, G);
1116 #endif
1117  }
1118  else
1119  {
1120  if (b.getp() != 0)
1121  {
1122 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1123  fmpz_t FLINTp;
1124  fmpz_mod_poly_t FLINTmipo;
1125  fq_ctx_t fq_con;
1126  fq_poly_t FLINTF, FLINTG;
1127 
1128  fmpz_init (FLINTp);
1129  convertCF2initFmpz (FLINTp, b.getpk());
1130 
1131  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
1132 
1133  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1134  fmpz_mod_ctx_t fmpz_ctx;
1135  fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1136  fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
1137  #else
1138  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1139  #endif
1140 
1141  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
1142  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
1143 
1144  fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1145 
1147  alpha, fq_con);
1148 
1149  fmpz_clear (FLINTp);
1150  fq_poly_clear (FLINTF, fq_con);
1151  fq_poly_clear (FLINTG, fq_con);
1152  fq_ctx_clear (fq_con);
1153  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1154  fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1155  fmpz_mod_ctx_clear(fmpz_ctx);
1156  #else
1157  fmpz_mod_poly_clear (FLINTmipo);
1158  #endif
1159  return b (result);
1160 #else
1161  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1162  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
1163  ZZ_pE::init (NTLmipo);
1164  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
1165  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
1166  div (NTLf, NTLf, NTLg);
1167  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
1168 #endif
1169  }
1170 #ifdef HAVE_FLINT
1171  CanonicalForm Q;
1172  newtonDiv (F, G, Q);
1173  return Q;
1174 #else
1175  return div (F,G);
1176 #endif
1177  }
1178  }
1179 
1180  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
1181  ASSERT (F.level() == G.level(), "expected polys of same level");
1182 #if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
1184  {
1187  }
1188 #endif
1189  Variable alpha;
1191  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
1192  {
1193 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1194  nmod_poly_t FLINTmipo;
1195  fq_nmod_ctx_t fq_con;
1196 
1197  nmod_poly_init (FLINTmipo, getCharacteristic());
1198  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
1199 
1200  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1201 
1202  fq_nmod_poly_t FLINTF, FLINTG;
1203  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
1205 
1206  fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1207 
1209 
1210  fq_nmod_poly_clear (FLINTF, fq_con);
1211  fq_nmod_poly_clear (FLINTG, fq_con);
1212  nmod_poly_clear (FLINTmipo);
1214 #else
1215  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
1216  zz_pE::init (NTLMipo);
1217  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
1218  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
1219  div (NTLF, NTLF, NTLG);
1220  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
1221 #endif
1222  }
1223  else
1224  {
1225 #ifdef HAVE_FLINT
1226  nmod_poly_t FLINTF, FLINTG;
1227  convertFacCF2nmod_poly_t (FLINTF, F);
1228  convertFacCF2nmod_poly_t (FLINTG, G);
1229  nmod_poly_div (FLINTF, FLINTF, FLINTG);
1230  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
1231  nmod_poly_clear (FLINTF);
1232  nmod_poly_clear (FLINTG);
1233 #else
1234  zz_pX NTLF= convertFacCF2NTLzzpX (F);
1235  zz_pX NTLG= convertFacCF2NTLzzpX (G);
1236  div (NTLF, NTLF, NTLG);
1237  result= convertNTLzzpX2CF(NTLF, F.mvar());
1238 #endif
1239  }
1240  return result;
1241 }
CanonicalForm convertFq_poly_t2FacCF(const fq_poly_t p, const Variable &x, const Variable &alpha, const fq_ctx_t ctx)
conversion of a FLINT poly over Fq (for non-word size p) to a CanonicalForm with alg....
void convertFacCF2Fq_t(fq_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory element of F_q (for non-word size p) to a FLINT fq_t
CanonicalForm convertFq_nmod_poly_t2FacCF(const fq_nmod_poly_t p, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t ctx)
conversion of a FLINT poly over Fq to a CanonicalForm with alg. variable alpha and polynomial variabl...
CanonicalForm convertFq_t2FacCF(const fq_t poly, const Variable &alpha)
conversion of a FLINT element of F_q with non-word size p to a CanonicalForm with alg....
CanonicalForm convertFmpz_mod_poly_t2FacCF(const fmpz_mod_poly_t poly, const Variable &x, const modpk &b)
conversion of a FLINT poly over Z/p (for non word size p) to a CanonicalForm over Z
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
void convertFacCF2Fmpz_mod_poly_t(fmpz_mod_poly_t result, const CanonicalForm &f, const fmpz_t p)
conversion of a factory univariate poly over Z to a FLINT poly over Z/p (for non word size p)
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
void convertFacCF2Fq_poly_t(fq_poly_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory univariate poly over F_q (for non-word size p) to a FLINT fq_poly_t
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1092
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
Definition: NTLconvert.cc:1037
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
Definition: NTLconvert.cc:250
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:285
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1115
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
Definition: NTLconvert.cc:64
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:670
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
CanonicalForm b
Definition: cfModGcd.cc:4105
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:24
static int gettype()
Definition: cf_factory.h:28
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool inBaseDomain() const
bool isUnivariate() const
factory's class for variables
Definition: factory.h:134
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm divFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:174
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition: facMul.cc:380
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR jList * Q
Definition: janet.cc:30
void init()
Definition: lintree.cc:864

◆ divrem()

void FACTORY_PUBLIC 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 3716 of file facMul.cc.

3718 {
3719  CanonicalForm A= mod (F, MOD);
3720  CanonicalForm B= mod (G, MOD);
3721  Variable x= Variable (1);
3722  int degB= degree (B, x);
3723  if (degB > degree (A, x))
3724  {
3725  Q= 0;
3726  R= A;
3727  return;
3728  }
3729 
3730  if (degB <= 0)
3731  {
3732  divrem (A, B, Q, R);
3733  Q= mod (Q, MOD);
3734  R= mod (R, MOD);
3735  return;
3736  }
3737  CFList splitA= split (A, degB, x);
3738 
3739  CanonicalForm xToDegB= power (x, degB);
3740  CanonicalForm H, bufQ;
3741  Q= 0;
3742  CFListIterator i= splitA;
3743  H= i.getItem()*xToDegB;
3744  i++;
3745  H += i.getItem();
3746  while (i.hasItem())
3747  {
3748  divrem21 (H, B, bufQ, R, MOD);
3749  i++;
3750  if (i.hasItem())
3751  H= R*xToDegB + i.getItem();
3752  Q *= xToDegB;
3753  Q += bufQ;
3754  }
3755  return;
3756 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int degree(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4084
CanonicalForm H
Definition: facAbsFact.cc:60
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:3072
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:3716
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3469
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3509
#define R
Definition: sirandom.c:27
#define A
Definition: sirandom.c:24

◆ 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 3649 of file facMul.cc.

3651 {
3652  CanonicalForm A= mod (F, M);
3653  CanonicalForm B= mod (G, M);
3654 
3655  if (B.inCoeffDomain())
3656  {
3657  divrem (A, B, Q, R);
3658  return;
3659  }
3660  if (A.inCoeffDomain() && !B.inCoeffDomain())
3661  {
3662  Q= 0;
3663  R= A;
3664  return;
3665  }
3666 
3667  if (B.level() < A.level())
3668  {
3669  divrem (A, B, Q, R);
3670  return;
3671  }
3672  if (A.level() > B.level())
3673  {
3674  R= A;
3675  Q= 0;
3676  return;
3677  }
3678  if (B.level() == 1 && B.isUnivariate())
3679  {
3680  divrem (A, B, Q, R);
3681  return;
3682  }
3683 
3684  Variable x= Variable (1);
3685  int degB= degree (B, x);
3686  if (degB > degree (A, x))
3687  {
3688  Q= 0;
3689  R= A;
3690  return;
3691  }
3692 
3693  CFList splitA= split (A, degB, x);
3694 
3695  CanonicalForm xToDegB= power (x, degB);
3696  CanonicalForm H, bufQ;
3697  Q= 0;
3698  CFListIterator i= splitA;
3699  H= i.getItem()*xToDegB;
3700  i++;
3701  H += i.getItem();
3702  CFList buf;
3703  while (i.hasItem())
3704  {
3705  buf= CFList (M);
3706  divrem21 (H, B, bufQ, R, buf);
3707  i++;
3708  if (i.hasItem())
3709  H= R*xToDegB + i.getItem();
3710  Q *= xToDegB;
3711  Q += bufQ;
3712  }
3713  return;
3714 }
List< CanonicalForm > CFList
int status int void * buf
Definition: si_signals.h:59
#define M
Definition: sirandom.c:25

◆ 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 3072 of file facMul.cc.

3073 {
3074  CanonicalForm A= F;
3075  for (CFListIterator i= M; i.hasItem(); i++)
3076  A= mod (A, i.getItem());
3077  return A;
3078 }

◆ 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 731 of file facMul.cc.

732 {
734  return mod (F, G);
735  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
736  {
737  if (b.getp() != 0)
738  return b(F);
739  return F;
740  }
741  else if (F.inCoeffDomain() && G.inCoeffDomain())
742  {
743  if (b.getp() != 0)
744  return b(F%G);
745  return mod (F, G);
746  }
747  else if (F.isUnivariate() && G.inCoeffDomain())
748  {
749  if (b.getp() != 0)
750  return b(F%G);
751  return mod (F,G);
752  }
753 
754  if (getCharacteristic() == 0)
755  {
756  Variable alpha;
757  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
758  {
759 #ifdef HAVE_FLINT
760  if (b.getp() != 0)
761  {
762  fmpz_t FLINTpk;
763  fmpz_init (FLINTpk);
764  convertCF2initFmpz (FLINTpk, b.getpk());
765  fmpz_mod_poly_t FLINTF, FLINTG;
766  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
767  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
768  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
769  fmpz_mod_ctx_t fmpz_ctx;
770  fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
771  fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG, fmpz_ctx);
772  #else
773  fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
774  #endif
776  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
777  fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
778  fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
779  fmpz_mod_ctx_clear(fmpz_ctx);
780  #else
781  fmpz_mod_poly_clear (FLINTG);
782  fmpz_mod_poly_clear (FLINTF);
783  #endif
784  fmpz_clear (FLINTpk);
785  return result;
786  }
787  return modFLINTQ (F, G);
788 #else
789  if (b.getp() != 0)
790  {
791  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
792  ZZX ZZf= convertFacCF2NTLZZX (F);
793  ZZX ZZg= convertFacCF2NTLZZX (G);
794  ZZ_pX NTLf= to_ZZ_pX (ZZf);
795  ZZ_pX NTLg= to_ZZ_pX (ZZg);
796  rem (NTLf, NTLf, NTLg);
797  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
798  }
799  return mod (F, G);
800 #endif
801  }
802  else
803  {
804  if (b.getp() != 0)
805  {
806 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
807  fmpz_t FLINTp;
808  fmpz_mod_poly_t FLINTmipo;
809  fq_ctx_t fq_con;
810  fq_poly_t FLINTF, FLINTG;
811 
812  fmpz_init (FLINTp);
813 
814  convertCF2initFmpz (FLINTp, b.getpk());
815 
817  bool rat=isOn(SW_RATIONAL);
818  On(SW_RATIONAL);
820  mipo *= cd;
821  if (!rat) Off(SW_RATIONAL);
822  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
823 
824  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
825  fmpz_mod_ctx_t fmpz_ctx;
826  fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
827  fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
828  #else
829  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
830  #endif
831 
832  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
833  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
834 
835  fq_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
836 
838  alpha, fq_con);
839 
840  fmpz_clear (FLINTp);
841  fq_poly_clear (FLINTF, fq_con);
842  fq_poly_clear (FLINTG, fq_con);
843  fq_ctx_clear (fq_con);
844  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
845  fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
846  fmpz_mod_ctx_clear(fmpz_ctx);
847  #else
848  fmpz_mod_poly_clear (FLINTmipo);
849  #endif
850 
851  return b(result);
852 #else
853  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
854  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
855  ZZ_pE::init (NTLmipo);
856  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
857  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
858  rem (NTLf, NTLf, NTLg);
859  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
860 #endif
861  }
862 #ifdef HAVE_FLINT
863  CanonicalForm Q, R;
864  newtonDivrem (F, G, Q, R);
865  return R;
866 #else
867  return mod (F,G);
868 #endif
869  }
870  }
871 
872  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
873  ASSERT (F.level() == G.level(), "expected polys of same level");
874 #if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
876  {
879  }
880 #endif
881  Variable alpha;
883  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
884  {
885 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
886  nmod_poly_t FLINTmipo;
887  fq_nmod_ctx_t fq_con;
888 
889  nmod_poly_init (FLINTmipo, getCharacteristic());
890  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
891 
892  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
893 
894  fq_nmod_poly_t FLINTF, FLINTG;
895  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
897 
898  fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
899 
901 
902  fq_nmod_poly_clear (FLINTF, fq_con);
903  fq_nmod_poly_clear (FLINTG, fq_con);
904  nmod_poly_clear (FLINTmipo);
906 #else
907  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
908  zz_pE::init (NTLMipo);
909  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
910  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
911  rem (NTLF, NTLF, NTLG);
912  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
913 #endif
914  }
915  else
916  {
917 #ifdef HAVE_FLINT
918  nmod_poly_t FLINTF, FLINTG;
919  convertFacCF2nmod_poly_t (FLINTF, F);
920  convertFacCF2nmod_poly_t (FLINTG, G);
921  nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
922  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
923  nmod_poly_clear (FLINTF);
924  nmod_poly_clear (FLINTG);
925 #else
926  zz_pX NTLF= convertFacCF2NTLzzpX (F);
927  zz_pX NTLG= convertFacCF2NTLzzpX (G);
928  rem (NTLF, NTLF, NTLG);
929  result= convertNTLzzpX2CF(NTLF, F.mvar());
930 #endif
931  }
932  return result;
933 }
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4091
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
CanonicalForm mipo
Definition: facAlgExt.cc:57
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:346
CanonicalForm modFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:192
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572

◆ 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 3080 of file facMul.cc.

3082 {
3083  if (A.isZero() || B.isZero())
3084  return 0;
3085 
3086  if (MOD.length() == 1)
3087  return mulMod2 (A, B, MOD.getLast());
3088 
3089  CanonicalForm M= MOD.getLast();
3090  CanonicalForm F= mod (A, M);
3091  CanonicalForm G= mod (B, M);
3092  if (F.inCoeffDomain())
3093  return G*F;
3094  if (G.inCoeffDomain())
3095  return F*G;
3096 
3097  int sizeF= size (F);
3098  int sizeG= size (G);
3099 
3100  if (sizeF / MOD.length() < 100 || sizeG / MOD.length() < 100)
3101  {
3102  if (sizeF < sizeG)
3103  return mod (G*F, MOD);
3104  else
3105  return mod (F*G, MOD);
3106  }
3107 
3108  Variable y= M.mvar();
3109  int degF= degree (F, y);
3110  int degG= degree (G, y);
3111 
3112  if ((degF <= 1 && F.level() <= M.level()) &&
3113  (degG <= 1 && G.level() <= M.level()))
3114  {
3115  CFList buf= MOD;
3116  buf.removeLast();
3117  if (degF == 1 && degG == 1)
3118  {
3119  CanonicalForm F0= mod (F, y);
3120  CanonicalForm F1= div (F, y);
3121  CanonicalForm G0= mod (G, y);
3122  CanonicalForm G1= div (G, y);
3123  if (degree (M) > 2)
3124  {
3125  CanonicalForm H00= mulMod (F0, G0, buf);
3126  CanonicalForm H11= mulMod (F1, G1, buf);
3127  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, buf);
3128  return H11*y*y + (H01 - H00 - H11)*y + H00;
3129  }
3130  else //here degree (M) == 2
3131  {
3132  buf.append (y);
3133  CanonicalForm F0G1= mulMod (F0, G1, buf);
3134  CanonicalForm F1G0= mulMod (F1, G0, buf);
3135  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3136  CanonicalForm result= F0G0 + y*(F0G1 + F1G0);
3137  return result;
3138  }
3139  }
3140  else if (degF == 1 && degG == 0)
3141  return mulMod (div (F, y), G, buf)*y + mulMod (mod (F, y), G, buf);
3142  else if (degF == 0 && degG == 1)
3143  return mulMod (div (G, y), F, buf)*y + mulMod (mod (G, y), F, buf);
3144  else
3145  return mulMod (F, G, buf);
3146  }
3147  int m= (int) ceil (degree (M)/2.0);
3148  if (degF >= m || degG >= m)
3149  {
3150  CanonicalForm MLo= power (y, m);
3151  CanonicalForm MHi= power (y, degree (M) - m);
3152  CanonicalForm F0= mod (F, MLo);
3153  CanonicalForm F1= div (F, MLo);
3154  CanonicalForm G0= mod (G, MLo);
3155  CanonicalForm G1= div (G, MLo);
3156  CFList buf= MOD;
3157  buf.removeLast();
3158  buf.append (MHi);
3159  CanonicalForm F0G1= mulMod (F0, G1, buf);
3160  CanonicalForm F1G0= mulMod (F1, G0, buf);
3161  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3162  return F0G0 + MLo*(F0G1 + F1G0);
3163  }
3164  else
3165  {
3166  m= (tmax(degF, degG)+1)/2;
3167  CanonicalForm yToM= power (y, m);
3168  CanonicalForm F0= mod (F, yToM);
3169  CanonicalForm F1= div (F, yToM);
3170  CanonicalForm G0= mod (G, yToM);
3171  CanonicalForm G1= div (G, yToM);
3172  CanonicalForm H00= mulMod (F0, G0, MOD);
3173  CanonicalForm H11= mulMod (F1, G1, MOD);
3174  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, MOD);
3175  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3176  }
3177  DEBOUTLN (cerr, "fatal end in mulMod");
3178 }
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int m
Definition: cfEzgcd.cc:128
CF_NO_INLINE bool isZero() const
int length() const
Definition: ftmpl_list.cc:273
T getLast() const
Definition: ftmpl_list.cc:309
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2986
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:3080
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:788

◆ 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 2986 of file facMul.cc.

2988 {
2989  if (A.isZero() || B.isZero())
2990  return 0;
2991 
2992  ASSERT (M.isUnivariate(), "M must be univariate");
2993 
2994  CanonicalForm F= mod (A, M);
2995  CanonicalForm G= mod (B, M);
2996  if (F.inCoeffDomain())
2997  return G*F;
2998  if (G.inCoeffDomain())
2999  return F*G;
3000 
3001  Variable y= M.mvar();
3002  int degF= degree (F, y);
3003  int degG= degree (G, y);
3004 
3005  if ((degF < 1 && degG < 1) && (F.isUnivariate() && G.isUnivariate()) &&
3006  (F.level() == G.level()))
3007  {
3008  CanonicalForm result= mulNTL (F, G);
3009  return mod (result, M);
3010  }
3011  else if (degF <= 1 && degG <= 1)
3012  {
3013  CanonicalForm result= F*G;
3014  return mod (result, M);
3015  }
3016 
3017  int sizeF= size (F);
3018  int sizeG= size (G);
3019 
3020  int fallBackToNaive= 50;
3021  if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
3022  {
3023  if (sizeF < sizeG)
3024  return mod (G*F, M);
3025  else
3026  return mod (F*G, M);
3027  }
3028 
3029 #ifdef HAVE_FLINT
3030  if (getCharacteristic() == 0)
3031  return mulMod2FLINTQa (F, G, M);
3032 #endif
3033 
3035  (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
3036  return mulMod2NTLFq (F, G, M);
3037 
3038  int m= (int) ceil (degree (M)/2.0);
3039  if (degF >= m || degG >= m)
3040  {
3041  CanonicalForm MLo= power (y, m);
3042  CanonicalForm MHi= power (y, degree (M) - m);
3043  CanonicalForm F0= mod (F, MLo);
3044  CanonicalForm F1= div (F, MLo);
3045  CanonicalForm G0= mod (G, MLo);
3046  CanonicalForm G1= div (G, MLo);
3047  CanonicalForm F0G1= mulMod2 (F0, G1, MHi);
3048  CanonicalForm F1G0= mulMod2 (F1, G0, MHi);
3049  CanonicalForm F0G0= mulMod2 (F0, G0, M);
3050  return F0G0 + MLo*(F0G1 + F1G0);
3051  }
3052  else
3053  {
3054  m= (int) ceil (tmax (degF, degG)/2.0);
3055  CanonicalForm yToM= power (y, m);
3056  CanonicalForm F0= mod (F, yToM);
3057  CanonicalForm F1= div (F, yToM);
3058  CanonicalForm G0= mod (G, yToM);
3059  CanonicalForm G1= div (G, yToM);
3060  CanonicalForm H00= mulMod2 (F0, G0, M);
3061  CanonicalForm H11= mulMod2 (F1, G1, M);
3062  CanonicalForm H01= mulMod2 (F0 + F1, G0 + G1, M);
3063  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3064  }
3065  DEBOUTLN (cerr, "fatal end in mulMod2");
3066 }
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:411
CanonicalForm mulMod2NTLFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2926
CanonicalForm mulMod2FLINTQa(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2332

◆ 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 411 of file facMul.cc.

412 {
414  return F*G;
415  if (getCharacteristic() == 0)
416  {
417  Variable alpha;
418  if ((!F.inCoeffDomain() && !G.inCoeffDomain()) &&
420  {
421  if (b.getp() != 0)
422  {
424  bool is_rat= isOn (SW_RATIONAL);
425  if (!is_rat)
426  On (SW_RATIONAL);
427  mipo *=bCommonDen (mipo);
428  if (!is_rat)
429  Off (SW_RATIONAL);
430 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
431  fmpz_t FLINTp;
432  fmpz_mod_poly_t FLINTmipo;
433  fq_ctx_t fq_con;
434  fq_poly_t FLINTF, FLINTG;
435 
436  fmpz_init (FLINTp);
437 
438  convertCF2initFmpz (FLINTp, b.getpk());
439 
440  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
441 
442  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
443  fmpz_mod_ctx_t fmpz_ctx;
444  fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
445  fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
446  #else
447  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
448  #endif
449 
450  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
451  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
452 
453  fq_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
454 
456  alpha, fq_con);
457 
458  fmpz_clear (FLINTp);
459  fq_poly_clear (FLINTF, fq_con);
460  fq_poly_clear (FLINTG, fq_con);
461  fq_ctx_clear (fq_con);
462  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
463  fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
464  fmpz_mod_ctx_clear(fmpz_ctx);
465  #else
466  fmpz_mod_poly_clear(FLINTmipo);
467  #endif
468  return b (result);
469 #endif
470 #ifdef HAVE_NTL
471  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
472  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (mipo));
473  ZZ_pE::init (NTLmipo);
474  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
475  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
476  mul (NTLf, NTLf, NTLg);
477 
478  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
479 #endif
480  }
481 #ifdef HAVE_FLINT
483  return result;
484 #else
485  return F*G;
486 #endif
487  }
488  else if (!F.inCoeffDomain() && !G.inCoeffDomain())
489  {
490 #ifdef HAVE_FLINT
491  if (b.getp() != 0)
492  {
493  fmpz_t FLINTpk;
494  fmpz_init (FLINTpk);
495  convertCF2initFmpz (FLINTpk, b.getpk());
496  fmpz_mod_poly_t FLINTF, FLINTG;
497  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
498  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
499  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
500  fmpz_mod_ctx_t fmpz_ctx;
501  fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
502  fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG, fmpz_ctx);
503  #else
504  fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
505  #endif
507  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
508  fmpz_mod_poly_clear (FLINTG,fmpz_ctx);
509  fmpz_mod_poly_clear (FLINTF,fmpz_ctx);
510  fmpz_mod_ctx_clear(fmpz_ctx);
511  #else
512  fmpz_mod_poly_clear (FLINTG);
513  fmpz_mod_poly_clear (FLINTF);
514  #endif
515  fmpz_clear (FLINTpk);
516  return result;
517  }
518  return mulFLINTQ (F, G);
519 #endif
520 #ifdef HAVE_NTL
521  if (b.getp() != 0)
522  {
523  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
524  ZZX ZZf= convertFacCF2NTLZZX (F);
525  ZZX ZZg= convertFacCF2NTLZZX (G);
526  ZZ_pX NTLf= to_ZZ_pX (ZZf);
527  ZZ_pX NTLg= to_ZZ_pX (ZZg);
528  mul (NTLf, NTLf, NTLg);
529  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
530  }
531  return F*G;
532 #endif
533  }
534  if (b.getp() != 0)
535  {
536  if (!F.inBaseDomain() && !G.inBaseDomain())
537  {
538  if (hasFirstAlgVar (G, alpha) || hasFirstAlgVar (F, alpha))
539  {
540 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
541  fmpz_t FLINTp;
542  fmpz_mod_poly_t FLINTmipo;
543  fq_ctx_t fq_con;
544 
545  fmpz_init (FLINTp);
546  convertCF2initFmpz (FLINTp, b.getpk());
547 
549  bool rat=isOn(SW_RATIONAL);
550  On(SW_RATIONAL);
552  mipo *= cd;
553  if (!rat) Off(SW_RATIONAL);
554  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
555 
556  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
557  fmpz_mod_ctx_t fmpz_ctx;
558  fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
559  fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
560  #else
561  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
562  #endif
563 
565 
566  if (F.inCoeffDomain() && !G.inCoeffDomain())
567  {
568  fq_poly_t FLINTG;
569  fmpz_poly_t FLINTF;
570  convertFacCF2Fmpz_poly_t (FLINTF, F);
571  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
572 
573  fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF, fq_con);
574 
575  result= convertFq_poly_t2FacCF (FLINTG, G.mvar(), alpha, fq_con);
576  fmpz_poly_clear (FLINTF);
577  fq_poly_clear (FLINTG, fq_con);
578  }
579  else if (!F.inCoeffDomain() && G.inCoeffDomain())
580  {
581  fq_poly_t FLINTF;
582  fmpz_poly_t FLINTG;
583 
584  convertFacCF2Fmpz_poly_t (FLINTG, G);
585  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
586 
587  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
588 
589  result= convertFq_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
590  fmpz_poly_clear (FLINTG);
591  fq_poly_clear (FLINTF, fq_con);
592  }
593  else
594  {
595  fq_t FLINTF, FLINTG;
596 
597  convertFacCF2Fq_t (FLINTF, F, fq_con);
598  convertFacCF2Fq_t (FLINTG, G, fq_con);
599 
600  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
601 
602  result= convertFq_t2FacCF (FLINTF, alpha);
603  fq_clear (FLINTF, fq_con);
604  fq_clear (FLINTG, fq_con);
605  }
606 
607  fmpz_clear (FLINTp);
608  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
609  fmpz_mod_poly_clear (FLINTmipo,fmpz_ctx);
610  fmpz_mod_ctx_clear(fmpz_ctx);
611  #else
612  fmpz_mod_poly_clear (FLINTmipo);
613  #endif
614  fq_ctx_clear (fq_con);
615 
616  return b (result);
617 #endif
618 #ifdef HAVE_NTL
619  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
620  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
621  ZZ_pE::init (NTLmipo);
622 
623  if (F.inCoeffDomain() && !G.inCoeffDomain())
624  {
625  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
626  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
627  mul (NTLg, to_ZZ_pE (NTLf), NTLg);
628  return b (convertNTLZZ_pEX2CF (NTLg, G.mvar(), alpha));
629  }
630  else if (!F.inCoeffDomain() && G.inCoeffDomain())
631  {
632  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
633  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
634  mul (NTLf, NTLf, to_ZZ_pE (NTLg));
635  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
636  }
637  else
638  {
639  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
640  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
641  ZZ_pE result;
642  mul (result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
643  return b (convertNTLZZpX2CF (rep (result), alpha));
644  }
645 #endif
646  }
647  }
648  return b (F*G);
649  }
650  return F*G;
651  }
652  else if (F.inCoeffDomain() || G.inCoeffDomain())
653  return F*G;
654  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
655  ASSERT (F.level() == G.level(), "expected polys of same level");
656 #ifdef HAVE_NTL
657 #if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
659  {
662  }
663 #endif
664 #endif
665  Variable alpha;
667  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
668  {
669  if (!getReduce (alpha))
670  {
671  result= 0;
672  for (CFIterator i= F; i.hasTerms(); i++)
673  result += i.coeff()*G*power (F.mvar(),i.exp());
674  return result;
675  }
676 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
677  nmod_poly_t FLINTmipo;
678  fq_nmod_ctx_t fq_con;
679 
680  nmod_poly_init (FLINTmipo, getCharacteristic());
681  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
682 
683  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
684 
685  fq_nmod_poly_t FLINTF, FLINTG;
686  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
688 
689  fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
690 
692 
693  fq_nmod_poly_clear (FLINTF, fq_con);
694  fq_nmod_poly_clear (FLINTG, fq_con);
695  nmod_poly_clear (FLINTmipo);
697  return result;
698 #elif defined(AHVE_NTL)
699  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
700  zz_pE::init (NTLMipo);
701  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
702  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
703  mul (NTLF, NTLF, NTLG);
704  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
705  return result;
706 #endif
707  }
708  else
709  {
710 #ifdef HAVE_FLINT
711  nmod_poly_t FLINTF, FLINTG;
712  convertFacCF2nmod_poly_t (FLINTF, F);
713  convertFacCF2nmod_poly_t (FLINTG, G);
714  nmod_poly_mul (FLINTF, FLINTF, FLINTG);
715  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
716  nmod_poly_clear (FLINTF);
717  nmod_poly_clear (FLINTG);
718  return result;
719 #endif
720 #ifdef HAVE_NTL
721  zz_pX NTLF= convertFacCF2NTLzzpX (F);
722  zz_pX NTLG= convertFacCF2NTLzzpX (G);
723  mul (NTLF, NTLF, NTLG);
724  return convertNTLzzpX2CF(NTLF, F.mvar());
725 #endif
726  }
727  return F*G;
728 }
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CanonicalForm mulFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:133
CanonicalForm mulFLINTQa(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
Definition: facMul.cc:103
bool getReduce(const Variable &alpha)
Definition: variable.cc:232

◆ 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 3313 of file facMul.cc.

3315 {
3316  ASSERT (getCharacteristic() > 0, "positive characteristic expected");
3317 
3318  CanonicalForm A= mod (F, M);
3319  CanonicalForm B= mod (G, M);
3320 
3321  Variable x= Variable (1);
3322  int degA= degree (A, x);
3323  int degB= degree (B, x);
3324  int m= degA - degB;
3325  if (m < 0)
3326  return 0;
3327 
3328  Variable v;
3329  CanonicalForm Q;
3330  if (degB < 1 || CFFactory::gettype() == GaloisFieldDomain)
3331  {
3332  CanonicalForm R;
3333  divrem2 (A, B, Q, R, M);
3334  }
3335  else
3336  {
3337  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3338  {
3339  CanonicalForm R= reverse (A, degA);
3340  CanonicalForm revB= reverse (B, degB);
3341  revB= newtonInverse (revB, m + 1, M);
3342  Q= mulMod2 (R, revB, M);
3343  Q= mod (Q, power (x, m + 1));
3344  Q= reverse (Q, m);
3345  }
3346  else
3347  {
3348  Variable y= Variable (2);
3349 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3350  nmod_poly_t FLINTmipo;
3351  fq_nmod_ctx_t fq_con;
3352 
3353  nmod_poly_init (FLINTmipo, getCharacteristic());
3354  convertFacCF2nmod_poly_t (FLINTmipo, M);
3355 
3356  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3357 
3358 
3359  fq_nmod_poly_t FLINTA, FLINTB;
3360  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3361  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3362 
3363  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3364 
3365  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3366 
3367  fq_nmod_poly_clear (FLINTA, fq_con);
3368  fq_nmod_poly_clear (FLINTB, fq_con);
3369  nmod_poly_clear (FLINTmipo);
3371 #else
3372  bool zz_pEbak= zz_pE::initialized();
3373  zz_pEBak bak;
3374  if (zz_pEbak)
3375  bak.save();
3376  zz_pX mipo= convertFacCF2NTLzzpX (M);
3377  zz_pEX NTLA, NTLB;
3378  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3379  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3380  div (NTLA, NTLA, NTLB);
3381  Q= convertNTLzz_pEX2CF (NTLA, x, y);
3382  if (zz_pEbak)
3383  bak.restore();
3384 #endif
3385  }
3386  }
3387 
3388  return Q;
3389 }
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
CanonicalForm reverse(const CanonicalForm &F, int d)
Definition: facMul.cc:3234
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:291
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:3649

◆ 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 346 of file facMul.cc.

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

◆ 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 3392 of file facMul.cc.

3394 {
3395  CanonicalForm A= mod (F, M);
3396  CanonicalForm B= mod (G, M);
3397  Variable x= Variable (1);
3398  int degA= degree (A, x);
3399  int degB= degree (B, x);
3400  int m= degA - degB;
3401 
3402  if (m < 0)
3403  {
3404  R= A;
3405  Q= 0;
3406  return;
3407  }
3408 
3409  Variable v;
3410  if (degB <= 1 || CFFactory::gettype() == GaloisFieldDomain)
3411  {
3412  divrem2 (A, B, Q, R, M);
3413  }
3414  else
3415  {
3416  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3417  {
3418  R= reverse (A, degA);
3419 
3420  CanonicalForm revB= reverse (B, degB);
3421  revB= newtonInverse (revB, m + 1, M);
3422  Q= mulMod2 (R, revB, M);
3423 
3424  Q= mod (Q, power (x, m + 1));
3425  Q= reverse (Q, m);
3426 
3427  R= A - mulMod2 (Q, B, M);
3428  }
3429  else
3430  {
3431  Variable y= Variable (2);
3432 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3433  nmod_poly_t FLINTmipo;
3434  fq_nmod_ctx_t fq_con;
3435 
3436  nmod_poly_init (FLINTmipo, getCharacteristic());
3437  convertFacCF2nmod_poly_t (FLINTmipo, M);
3438 
3439  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3440 
3441  fq_nmod_poly_t FLINTA, FLINTB;
3442  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3443  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3444 
3445  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3446 
3447  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3448  R= convertFq_nmod_poly_t2FacCF (FLINTB, x, y, fq_con);
3449 
3450  fq_nmod_poly_clear (FLINTA, fq_con);
3451  fq_nmod_poly_clear (FLINTB, fq_con);
3452  nmod_poly_clear (FLINTmipo);
3454 #else
3455  zz_pX mipo= convertFacCF2NTLzzpX (M);
3456  zz_pEX NTLA, NTLB;
3457  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3458  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3459  zz_pEX NTLQ, NTLR;
3460  DivRem (NTLQ, NTLR, NTLA, NTLB);
3461  Q= convertNTLzz_pEX2CF (NTLQ, x, y);
3462  R= convertNTLzz_pEX2CF (NTLR, x, y);
3463 #endif
3464  }
3465  }
3466 }

◆ 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 3180 of file facMul.cc.

3181 {
3182  if (L.isEmpty())
3183  return 1;
3184  int l= L.length();
3185  if (l == 1)
3186  return mod (L.getFirst(), M);
3187  else if (l == 2) {
3189  return result;
3190  }
3191  else
3192  {
3193  l /= 2;
3194  CFList tmp1, tmp2;
3195  CFListIterator i= L;
3197  for (int j= 1; j <= l; j++, i++)
3198  tmp1.append (i.getItem());
3199  tmp2= Difference (L, tmp1);
3200  buf1= prodMod (tmp1, M);
3201  buf2= prodMod (tmp2, M);
3203  return result;
3204  }
3205 }
int l
Definition: cfEzgcd.cc:100
T getFirst() const
Definition: ftmpl_list.cc:279
void append(const T &)
Definition: ftmpl_list.cc:256
int isEmpty() const
Definition: ftmpl_list.cc:267
CFList tmp1
Definition: facFqBivar.cc:72
CanonicalForm buf2
Definition: facFqBivar.cc:73
CFList tmp2
Definition: facFqBivar.cc:72
CanonicalForm buf1
Definition: facFqBivar.cc:73
int j
Definition: facHensel.cc:110
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3180
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)

◆ 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 3207 of file facMul.cc.

3208 {
3209  if (L.isEmpty())
3210  return 1;
3211  else if (L.length() == 1)
3212  return L.getFirst();
3213  else if (L.length() == 2)
3214  return mulMod (L.getFirst(), L.getLast(), M);
3215  else
3216  {
3217  int l= L.length()/2;
3218  CFListIterator i= L;
3219  CFList tmp1, tmp2;
3221  for (int j= 1; j <= l; j++, i++)
3222  tmp1.append (i.getItem());
3223  tmp2= Difference (L, tmp1);
3224  buf1= prodMod (tmp1, M);
3225  buf2= prodMod (tmp2, M);
3226  return mulMod (buf1, buf2, M);
3227  }
3228 }

◆ 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 3759 of file facMul.cc.

3760 {
3761  if (B.isZero())
3762  return true;
3763  if (A.isZero())
3764  return false;
3766  return fdivides (A, B);
3767  int p= getCharacteristic();
3768  if (A.inCoeffDomain() || B.inCoeffDomain())
3769  {
3770  if (A.inCoeffDomain())
3771  return true;
3772  else
3773  return false;
3774  }
3775  if (p > 0)
3776  {
3777 #if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
3778  if (fac_NTL_char != p)
3779  {
3780  fac_NTL_char= p;
3781  zz_p::init (p);
3782  }
3783 #endif
3784  Variable alpha;
3785  if (hasFirstAlgVar (A, alpha) || hasFirstAlgVar (B, alpha))
3786  {
3787 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3788  nmod_poly_t FLINTmipo;
3789  fq_nmod_ctx_t fq_con;
3790 
3791  nmod_poly_init (FLINTmipo, getCharacteristic());
3792  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
3793 
3794  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3795 
3796  fq_nmod_poly_t FLINTA, FLINTB;
3799  int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA, fq_con);
3800  fq_nmod_poly_clear (FLINTA, fq_con);
3801  fq_nmod_poly_clear (FLINTB, fq_con);
3802  nmod_poly_clear (FLINTmipo);
3804  return result;
3805 #else
3806  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3807  zz_pE::init (NTLMipo);
3808  zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
3809  zz_pEX NTLB= convertFacCF2NTLzz_pEX (B, NTLMipo);
3810  return divide (NTLB, NTLA);
3811 #endif
3812  }
3813 #ifdef HAVE_FLINT
3814  nmod_poly_t FLINTA, FLINTB;
3815  convertFacCF2nmod_poly_t (FLINTA, A);
3816  convertFacCF2nmod_poly_t (FLINTB, B);
3817  nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3818  bool result= nmod_poly_is_zero (FLINTA);
3819  nmod_poly_clear (FLINTA);
3820  nmod_poly_clear (FLINTB);
3821  return result;
3822 #else
3823  zz_pX NTLA= convertFacCF2NTLzzpX (A);
3824  zz_pX NTLB= convertFacCF2NTLzzpX (B);
3825  return divide (NTLB, NTLA);
3826 #endif
3827  }
3828 #ifdef HAVE_FLINT
3829  Variable alpha;
3830  bool isRat= isOn (SW_RATIONAL);
3831  if (!isRat)
3832  On (SW_RATIONAL);
3833  if (!hasFirstAlgVar (A, alpha) && !hasFirstAlgVar (B, alpha))
3834  {
3835  fmpq_poly_t FLINTA,FLINTB;
3836  convertFacCF2Fmpq_poly_t (FLINTA, A);
3837  convertFacCF2Fmpq_poly_t (FLINTB, B);
3838  fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3839  bool result= fmpq_poly_is_zero (FLINTA);
3840  fmpq_poly_clear (FLINTA);
3841  fmpq_poly_clear (FLINTB);
3842  if (!isRat)
3843  Off (SW_RATIONAL);
3844  return result;
3845  }
3846  CanonicalForm Q, R;
3847  newtonDivrem (B, A, Q, R);
3848  if (!isRat)
3849  Off (SW_RATIONAL);
3850  return R.isZero();
3851 #else
3852  bool isRat= isOn (SW_RATIONAL);
3853  if (!isRat)
3854  On (SW_RATIONAL);
3855  bool result= fdivides (A, B);
3856  if (!isRat)
3857  Off (SW_RATIONAL);
3858  return result; //maybe NTL?
3859 #endif
3860 }
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
int p
Definition: cfModGcd.cc:4080
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)