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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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