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

941{
943 return div (F, G);
944 if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
945 {
946 return 0;
947 }
948 else if (F.inCoeffDomain() && G.inCoeffDomain())
949 {
950 if (b.getp() != 0)
951 {
952 if (!F.inBaseDomain() || !G.inBaseDomain())
953 {
957#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
958 fmpz_t FLINTp;
959 fmpz_mod_poly_t FLINTmipo;
960 fq_ctx_t fq_con;
961 fq_t FLINTF, FLINTG;
962
963 fmpz_init (FLINTp);
964 convertCF2initFmpz (FLINTp, b.getpk());
965
966 convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
967
968 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
969 fmpz_mod_ctx_t fmpz_ctx;
970 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
971 fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
972 #else
973 fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
974 #endif
975
976 convertFacCF2Fq_t (FLINTF, F, fq_con);
977 convertFacCF2Fq_t (FLINTG, G, fq_con);
978
979 fq_inv (FLINTG, FLINTG, fq_con);
980 fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
981
983
984 fmpz_clear (FLINTp);
985 fq_clear (FLINTF, fq_con);
986 fq_clear (FLINTG, fq_con);
987 fq_ctx_clear (fq_con);
988 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
989 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
990 fmpz_mod_ctx_clear(fmpz_ctx);
991 #else
992 fmpz_mod_poly_clear (FLINTmipo);
993 #endif
994 return b (result);
995#else
996 ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
997 ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
998 ZZ_pE::init (NTLmipo);
999 ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
1000 ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
1001 ZZ_pE result;
1002 div (result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
1003 return b (convertNTLZZpX2CF (rep (result), alpha));
1004#endif
1005 }
1006 return b(div (F,G));
1007 }
1008 return div (F, G);
1009 }
1010 else if (F.isUnivariate() && G.inCoeffDomain())
1011 {
1012 if (b.getp() != 0)
1013 {
1014 if (!G.inBaseDomain())
1015 {
1018#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1019 fmpz_t FLINTp;
1020 fmpz_mod_poly_t FLINTmipo;
1021 fq_ctx_t fq_con;
1022 fq_poly_t FLINTF;
1023 fq_t FLINTG;
1024
1025 fmpz_init (FLINTp);
1026 convertCF2initFmpz (FLINTp, b.getpk());
1027
1028 convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
1029
1030 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1031 fmpz_mod_ctx_t fmpz_ctx;
1032 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1033 fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
1034 #else
1035 fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1036 #endif
1037
1038 convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
1039 convertFacCF2Fq_t (FLINTG, G, fq_con);
1040
1041 fq_inv (FLINTG, FLINTG, fq_con);
1042 fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
1043
1045 alpha, fq_con);
1046
1047 fmpz_clear (FLINTp);
1048 fq_poly_clear (FLINTF, fq_con);
1049 fq_clear (FLINTG, fq_con);
1050 fq_ctx_clear (fq_con);
1051 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1052 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1053 fmpz_mod_ctx_clear(fmpz_ctx);
1054 #else
1055 fmpz_mod_poly_clear (FLINTmipo);
1056 #endif
1057 return b (result);
1058#else
1059 ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1060 ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
1061 ZZ_pE::init (NTLmipo);
1062 ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
1063 ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
1064 div (NTLf, NTLf, to_ZZ_pE (NTLg));
1065 return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
1066#endif
1067 }
1068 return b(div (F,G));
1069 }
1070 return div (F, G);
1071 }
1072
1073 if (getCharacteristic() == 0)
1074 {
1075
1077 if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
1078 {
1079#ifdef HAVE_FLINT
1080 if (b.getp() != 0)
1081 {
1082 fmpz_t FLINTpk;
1083 fmpz_init (FLINTpk);
1084 convertCF2initFmpz (FLINTpk, b.getpk());
1085 fmpz_mod_poly_t FLINTF, FLINTG;
1086 convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
1087 convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
1088 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1089 fmpz_mod_ctx_t fmpz_ctx;
1090 fmpz_mod_ctx_init(fmpz_ctx,FLINTpk);
1091 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fmpz_ctx);
1092 #else
1093 fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
1094 #endif
1096 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1097 fmpz_mod_poly_clear (FLINTG, fmpz_ctx);
1098 fmpz_mod_poly_clear (FLINTF, fmpz_ctx);
1099 fmpz_mod_ctx_clear(fmpz_ctx);
1100 #else
1101 fmpz_mod_poly_clear (FLINTG);
1102 fmpz_mod_poly_clear (FLINTF);
1103 #endif
1104 fmpz_clear (FLINTpk);
1105 return result;
1106 }
1107 return divFLINTQ (F,G);
1108#else
1109 if (b.getp() != 0)
1110 {
1111 ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1112 ZZX ZZf= convertFacCF2NTLZZX (F);
1113 ZZX ZZg= convertFacCF2NTLZZX (G);
1114 ZZ_pX NTLf= to_ZZ_pX (ZZf);
1115 ZZ_pX NTLg= to_ZZ_pX (ZZg);
1116 div (NTLf, NTLf, NTLg);
1117 return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
1118 }
1119 return div (F, G);
1120#endif
1121 }
1122 else
1123 {
1124 if (b.getp() != 0)
1125 {
1126#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1127 fmpz_t FLINTp;
1128 fmpz_mod_poly_t FLINTmipo;
1129 fq_ctx_t fq_con;
1130 fq_poly_t FLINTF, FLINTG;
1131
1132 fmpz_init (FLINTp);
1133 convertCF2initFmpz (FLINTp, b.getpk());
1134
1135 convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
1136
1137 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1138 fmpz_mod_ctx_t fmpz_ctx;
1139 fmpz_mod_ctx_init(fmpz_ctx,FLINTp);
1140 fq_ctx_init_modulus (fq_con, FLINTmipo, fmpz_ctx, "Z");
1141 #else
1142 fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1143 #endif
1144
1145 convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
1146 convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
1147
1148 fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1149
1151 alpha, fq_con);
1152
1153 fmpz_clear (FLINTp);
1154 fq_poly_clear (FLINTF, fq_con);
1155 fq_poly_clear (FLINTG, fq_con);
1156 fq_ctx_clear (fq_con);
1157 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1158 fmpz_mod_poly_clear (FLINTmipo, fmpz_ctx);
1159 fmpz_mod_ctx_clear(fmpz_ctx);
1160 #else
1161 fmpz_mod_poly_clear (FLINTmipo);
1162 #endif
1163 return b (result);
1164#else
1165 ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1166 ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
1167 ZZ_pE::init (NTLmipo);
1168 ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
1169 ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
1170 div (NTLf, NTLf, NTLg);
1171 return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
1172#endif
1173 }
1174#ifdef HAVE_FLINT
1176 newtonDiv (F, G, Q);
1177 return Q;
1178#else
1179 return div (F,G);
1180#endif
1181 }
1182 }
1183
1184 ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
1185 ASSERT (F.level() == G.level(), "expected polys of same level");
1186#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
1188 {
1191 }
1192#endif
1195 if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
1196 {
1197#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1198 nmod_poly_t FLINTmipo;
1199 fq_nmod_ctx_t fq_con;
1200
1201 nmod_poly_init (FLINTmipo, getCharacteristic());
1202 convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
1203
1204 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1205
1206 fq_nmod_poly_t FLINTF, FLINTG;
1209
1210 fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1211
1213
1214 fq_nmod_poly_clear (FLINTF, fq_con);
1215 fq_nmod_poly_clear (FLINTG, fq_con);
1216 nmod_poly_clear (FLINTmipo);
1218#else
1219 zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
1220 zz_pE::init (NTLMipo);
1221 zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
1222 zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
1223 div (NTLF, NTLF, NTLG);
1224 result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
1225#endif
1226 }
1227 else
1228 {
1229#ifdef HAVE_FLINT
1230 nmod_poly_t FLINTF, FLINTG;
1231 convertFacCF2nmod_poly_t (FLINTF, F);
1232 convertFacCF2nmod_poly_t (FLINTG, G);
1233 nmod_poly_div (FLINTF, FLINTF, FLINTG);
1234 result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
1235 nmod_poly_clear (FLINTF);
1236 nmod_poly_clear (FLINTG);
1237#else
1238 zz_pX NTLF= convertFacCF2NTLzzpX (F);
1239 zz_pX NTLG= convertFacCF2NTLzzpX (G);
1240 div (NTLF, NTLF, NTLG);
1241 result= convertNTLzzpX2CF(NTLF, F.mvar());
1242#endif
1243 }
1244 return result;
1245}
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:4103
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:18
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:127
Variable alpha
Definition: facAbsBiFact.cc:52
return result
Definition: facAbsBiFact.cc:76
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:178
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition: facMul.cc:384
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 3720 of file facMul.cc.

3722{
3723 CanonicalForm A= mod (F, MOD);
3724 CanonicalForm B= mod (G, MOD);
3725 Variable x= Variable (1);
3726 int degB= degree (B, x);
3727 if (degB > degree (A, x))
3728 {
3729 Q= 0;
3730 R= A;
3731 return;
3732 }
3733
3734 if (degB <= 0)
3735 {
3736 divrem (A, B, Q, R);
3737 Q= mod (Q, MOD);
3738 R= mod (R, MOD);
3739 return;
3740 }
3741 CFList splitA= split (A, degB, x);
3742
3743 CanonicalForm xToDegB= power (x, degB);
3744 CanonicalForm H, bufQ;
3745 Q= 0;
3746 CFListIterator i= splitA;
3747 H= i.getItem()*xToDegB;
3748 i++;
3749 H += i.getItem();
3750 while (i.hasItem())
3751 {
3752 divrem21 (H, B, bufQ, R, MOD);
3753 i++;
3754 if (i.hasItem())
3755 H= R*xToDegB + i.getItem();
3756 Q *= xToDegB;
3757 Q += bufQ;
3758 }
3759 return;
3760}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int degree(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
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:3076
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:3720
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3473
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3513
#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 3653 of file facMul.cc.

3655{
3656 CanonicalForm A= mod (F, M);
3657 CanonicalForm B= mod (G, M);
3658
3659 if (B.inCoeffDomain())
3660 {
3661 divrem (A, B, Q, R);
3662 return;
3663 }
3664 if (A.inCoeffDomain() && !B.inCoeffDomain())
3665 {
3666 Q= 0;
3667 R= A;
3668 return;
3669 }
3670
3671 if (B.level() < A.level())
3672 {
3673 divrem (A, B, Q, R);
3674 return;
3675 }
3676 if (A.level() > B.level())
3677 {
3678 R= A;
3679 Q= 0;
3680 return;
3681 }
3682 if (B.level() == 1 && B.isUnivariate())
3683 {
3684 divrem (A, B, Q, R);
3685 return;
3686 }
3687
3688 Variable x= Variable (1);
3689 int degB= degree (B, x);
3690 if (degB > degree (A, x))
3691 {
3692 Q= 0;
3693 R= A;
3694 return;
3695 }
3696
3697 CFList splitA= split (A, degB, x);
3698
3699 CanonicalForm xToDegB= power (x, degB);
3700 CanonicalForm H, bufQ;
3701 Q= 0;
3702 CFListIterator i= splitA;
3703 H= i.getItem()*xToDegB;
3704 i++;
3705 H += i.getItem();
3706 CFList buf;
3707 while (i.hasItem())
3708 {
3709 buf= CFList (M);
3710 divrem21 (H, B, bufQ, R, buf);
3711 i++;
3712 if (i.hasItem())
3713 H= R*xToDegB + i.getItem();
3714 Q *= xToDegB;
3715 Q += bufQ;
3716 }
3717 return;
3718}
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 3076 of file facMul.cc.

3077{
3078 CanonicalForm A= F;
3079 for (CFListIterator i= M; i.hasItem(); i++)
3080 A= mod (A, i.getItem());
3081 return A;
3082}

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

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

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

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

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

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

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

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

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

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

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

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

3185{
3186 if (L.isEmpty())
3187 return 1;
3188 int l= L.length();
3189 if (l == 1)
3190 return mod (L.getFirst(), M);
3191 else if (l == 2) {
3193 return result;
3194 }
3195 else
3196 {
3197 l /= 2;
3198 CFList tmp1, tmp2;
3199 CFListIterator i= L;
3201 for (int j= 1; j <= l; j++, i++)
3202 tmp1.append (i.getItem());
3203 tmp2= Difference (L, tmp1);
3204 buf1= prodMod (tmp1, M);
3205 buf2= prodMod (tmp2, M);
3207 return result;
3208 }
3209}
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:74
CanonicalForm buf2
Definition: facFqBivar.cc:75
CFList tmp2
Definition: facFqBivar.cc:74
CanonicalForm buf1
Definition: facFqBivar.cc:75
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:3184
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 3211 of file facMul.cc.

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

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

3764{
3765 if (B.isZero())
3766 return true;
3767 if (A.isZero())
3768 return false;
3770 return fdivides (A, B);
3771 int p= getCharacteristic();
3772 if (A.inCoeffDomain() || B.inCoeffDomain())
3773 {
3774 if (A.inCoeffDomain())
3775 return true;
3776 else
3777 return false;
3778 }
3779 if (p > 0)
3780 {
3781#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
3782 if (fac_NTL_char != p)
3783 {
3784 fac_NTL_char= p;
3785 zz_p::init (p);
3786 }
3787#endif
3790 {
3791#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3792 nmod_poly_t FLINTmipo;
3793 fq_nmod_ctx_t fq_con;
3794
3795 nmod_poly_init (FLINTmipo, getCharacteristic());
3796 convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
3797
3798 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3799
3800 fq_nmod_poly_t FLINTA, FLINTB;
3803 int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA, fq_con);
3804 fq_nmod_poly_clear (FLINTA, fq_con);
3805 fq_nmod_poly_clear (FLINTB, fq_con);
3806 nmod_poly_clear (FLINTmipo);
3808 return result;
3809#else
3810 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3811 zz_pE::init (NTLMipo);
3812 zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
3813 zz_pEX NTLB= convertFacCF2NTLzz_pEX (B, NTLMipo);
3814 return divide (NTLB, NTLA);
3815#endif
3816 }
3817#ifdef HAVE_FLINT
3818 nmod_poly_t FLINTA, FLINTB;
3819 convertFacCF2nmod_poly_t (FLINTA, A);
3820 convertFacCF2nmod_poly_t (FLINTB, B);
3821 nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3822 bool result= nmod_poly_is_zero (FLINTA);
3823 nmod_poly_clear (FLINTA);
3824 nmod_poly_clear (FLINTB);
3825 return result;
3826#else
3827 zz_pX NTLA= convertFacCF2NTLzzpX (A);
3828 zz_pX NTLB= convertFacCF2NTLzzpX (B);
3829 return divide (NTLB, NTLA);
3830#endif
3831 }
3832#ifdef HAVE_FLINT
3834 bool isRat= isOn (SW_RATIONAL);
3835 if (!isRat)
3836 On (SW_RATIONAL);
3837 if (!hasFirstAlgVar (A, alpha) && !hasFirstAlgVar (B, alpha))
3838 {
3839 fmpq_poly_t FLINTA,FLINTB;
3840 convertFacCF2Fmpq_poly_t (FLINTA, A);
3841 convertFacCF2Fmpq_poly_t (FLINTB, B);
3842 fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3843 bool result= fmpq_poly_is_zero (FLINTA);
3844 fmpq_poly_clear (FLINTA);
3845 fmpq_poly_clear (FLINTB);
3846 if (!isRat)
3847 Off (SW_RATIONAL);
3848 return result;
3849 }
3850 CanonicalForm Q, R;
3851 newtonDivrem (B, A, Q, R);
3852 if (!isRat)
3853 Off (SW_RATIONAL);
3854 return R.isZero();
3855#else
3856 bool isRat= isOn (SW_RATIONAL);
3857 if (!isRat)
3858 On (SW_RATIONAL);
3859 bool result= fdivides (A, B);
3860 if (!isRat)
3861 Off (SW_RATIONAL);
3862 return result; //maybe NTL?
3863#endif
3864}
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:4078
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)