My Project
Loading...
Searching...
No Matches
Functions
facMul.h File Reference

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

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

Go to the source code of this file.

Functions

CanonicalForm mulNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
 multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f). More...
 
CanonicalForm modNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
 mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked More...
 
CanonicalForm divNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b=modpk())
 division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked More...
 
void divrem2 (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
 division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division". More...
 
void FACTORY_PUBLIC divrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &MOD)
 division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division". More...
 
void newtonDivrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
 division with remainder of F by G wrt Variable (1) modulo M using Newton inversion More...
 
CanonicalForm newtonDiv (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 division of F by G wrt Variable (1) modulo M using Newton inversion More...
 
bool uniFdivides (const CanonicalForm &A, const CanonicalForm &B)
 divisibility test for univariate polys More...
 
CanonicalForm mulMod2 (const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
 Karatsuba style modular multiplication for bivariate polynomials. More...
 
CanonicalForm mulMod (const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
 Karatsuba style modular multiplication for multivariate polynomials. More...
 
CanonicalForm mod (const CanonicalForm &F, const CFList &M)
 reduce F modulo elements in M. More...
 
CanonicalForm prodMod (const CFList &L, const CanonicalForm &M)
 product of all elements in L modulo M via divide-and-conquer. More...
 
CanonicalForm prodMod (const CFList &L, const CFList &M)
 product of all elements in L modulo M via divide-and-conquer. More...
 
void newtonDivrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
 division with remainder of univariate polynomials over Q and Q(a) using Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G) More...
 

Detailed Description

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

Author
Martin Lee

Definition in file facMul.h.

Function Documentation

◆ divNTL()

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

division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked

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

Definition at line 936 of file facMul.cc.

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

◆ divrem()

void FACTORY_PUBLIC divrem ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Q,
CanonicalForm R,
const CFList MOD 
)

division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".

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

Definition at line 3716 of file facMul.cc.

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

◆ divrem2()

void divrem2 ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Q,
CanonicalForm R,
const CanonicalForm M 
)

division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".

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

Definition at line 3649 of file facMul.cc.

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

◆ mod()

CanonicalForm mod ( const CanonicalForm F,
const CFList M 
)

reduce F modulo elements in M.

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

Definition at line 3072 of file facMul.cc.

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

◆ modNTL()

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

mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked

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

Definition at line 731 of file facMul.cc.

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

◆ mulMod()

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

Karatsuba style modular multiplication for multivariate polynomials.

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

Definition at line 3080 of file facMul.cc.

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

◆ mulMod2()

Karatsuba style modular multiplication for bivariate polynomials.

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

Definition at line 2986 of file facMul.cc.

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

◆ mulNTL()

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

multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f).

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

Definition at line 411 of file facMul.cc.

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

◆ newtonDiv()

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

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

Definition at line 3313 of file facMul.cc.

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

◆ newtonDivrem() [1/2]

void newtonDivrem ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Q,
CanonicalForm R 
)

division with remainder of univariate polynomials over Q and Q(a) using Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)

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

Definition at line 346 of file facMul.cc.

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

◆ newtonDivrem() [2/2]

void newtonDivrem ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Q,
CanonicalForm R,
const CanonicalForm M 
)

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

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

Definition at line 3392 of file facMul.cc.

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

◆ prodMod() [1/2]

CanonicalForm prodMod ( const CFList L,
const CanonicalForm M 
)

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

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

Definition at line 3180 of file facMul.cc.

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

◆ prodMod() [2/2]

CanonicalForm prodMod ( const CFList L,
const CFList M 
)

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

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

Definition at line 3207 of file facMul.cc.

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

◆ uniFdivides()

bool uniFdivides ( const CanonicalForm A,
const CanonicalForm B 
)

divisibility test for univariate polys

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

Definition at line 3759 of file facMul.cc.

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