My Project
Loading...
Searching...
No Matches
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).
 
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
 
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
 
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".
 
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".
 
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
 
CanonicalForm newtonDiv (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 division of F by G wrt Variable (1) modulo M using Newton inversion
 
bool uniFdivides (const CanonicalForm &A, const CanonicalForm &B)
 divisibility test for univariate polys
 
CanonicalForm mulMod2 (const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
 Karatsuba style modular multiplication for bivariate polynomials.
 
CanonicalForm mulMod (const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
 Karatsuba style modular multiplication for multivariate polynomials.
 
CanonicalForm mod (const CanonicalForm &F, const CFList &M)
 reduce F modulo elements in M.
 
CanonicalForm prodMod (const CFList &L, const CanonicalForm &M)
 product of all elements in L modulo M via divide-and-conquer.
 
CanonicalForm prodMod (const CFList &L, const CFList &M)
 product of all elements in L modulo M via divide-and-conquer.
 
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)
 

Detailed Description

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

Author
Martin Lee

Definition in file facMul.h.

Function Documentation

◆ divNTL()

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

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

◆ divrem()

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
Q[in,out] dividend
R[in,out] remainder, degree (R, 1) < degree (G, 1)
[in]MODonly contains powers of Variables of level higher than 1

Definition at line 3721 of file facMul.cc.

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

◆ divrem2()

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
Q[in,out] dividend
R[in,out] remainder, degree (R, 1) < degree (G, 1)
[in]Mpower of Variable (2)

Definition at line 3654 of file facMul.cc.

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

◆ mod()

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

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

◆ modNTL()

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

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

◆ mulMod()

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

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

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

◆ mulNTL()

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

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

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

◆ 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
Q[in, out] quotient
R[in, out] remainder

Definition at line 351 of file facMul.cc.

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

◆ 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)
Q[in,out] dividend
R[in,out] remainder, degree (R, 1) < degree (G, 1)
[in]Mpower of Variable (2)

Definition at line 3397 of file facMul.cc.

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

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

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

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

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

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