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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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