My Project
Functions
facMul.cc File Reference

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

#include "debug.h"
#include "config.h"
#include "canonicalform.h"
#include "facMul.h"
#include "cf_util.h"
#include "cf_iter.h"
#include "cf_algorithm.h"
#include "templates/ftmpl_functions.h"
#include <NTL/lzz_pEX.h>
#include "NTLconvert.h"
#include "FLINTconvert.h"
#include "flint/fq_nmod_vec.h"

Go to the source code of this file.

Functions

void kronSubQa (fmpz_poly_t result, const CanonicalForm &A, int d)
 
CanonicalForm reverseSubstQa (const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
 
CanonicalForm mulFLINTQa (const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
 
CanonicalForm mulFLINTQ (const CanonicalForm &F, const CanonicalForm &G)
 
CanonicalForm divFLINTQ (const CanonicalForm &F, const CanonicalForm &G)
 
CanonicalForm modFLINTQ (const CanonicalForm &F, const CanonicalForm &G)
 
CanonicalForm mulFLINTQaTrunc (const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, int m)
 
CanonicalForm mulFLINTQTrunc (const CanonicalForm &F, const CanonicalForm &G, int m)
 
CanonicalForm uniReverse (const CanonicalForm &F, int d, const Variable &x)
 
CanonicalForm newtonInverse (const CanonicalForm &F, const int n, const Variable &x)
 
void newtonDivrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
 division with remainder of univariate polynomials over Q and Q(a) using Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G) More...
 
void newtonDiv (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
 
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), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f). More...
 
CanonicalForm modNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
 mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked More...
 
CanonicalForm divNTL (const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
 division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked More...
 
void kronSubFp (nmod_poly_t result, const CanonicalForm &A, int d)
 
void kronSubFq (fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
 
void kronSubQa (fmpz_poly_t result, const CanonicalForm &A, int d1, int d2)
 
void kronSubReciproFp (nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm &A, int d)
 
void kronSubReciproFq (fq_nmod_poly_t subA1, fq_nmod_poly_t subA2, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
 
void kronSubReciproQ (fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm &A, int d)
 
CanonicalForm reverseSubstQ (const fmpz_poly_t F, int d)
 
CanonicalForm reverseSubstQa (const fmpz_poly_t F, int d1, int d2, const Variable &alpha, const fmpq_poly_t mipo)
 
CanonicalForm reverseSubstReciproFp (const nmod_poly_t F, const nmod_poly_t G, int d, int k)
 
CanonicalForm reverseSubstReciproFq (const fq_nmod_poly_t F, const fq_nmod_poly_t G, int d, int k, const Variable &alpha, const fq_nmod_ctx_t fq_con)
 
CanonicalForm reverseSubstReciproQ (const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
 
CanonicalForm reverseSubstFq (const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
 
CanonicalForm reverseSubstFp (const nmod_poly_t F, int d)
 
CanonicalForm mulMod2FLINTFpReci (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 
CanonicalForm mulMod2FLINTFp (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 
CanonicalForm mulMod2FLINTFqReci (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
 
CanonicalForm mulMod2FLINTFq (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
 
CanonicalForm mulMod2FLINTQReci (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 
CanonicalForm mulMod2FLINTQ (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 
CanonicalForm mulMod2FLINTQa (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 
CanonicalForm mulMod2NTLFq (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 
CanonicalForm mulMod2 (const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
 Karatsuba style modular multiplication for bivariate polynomials. More...
 
CanonicalForm mod (const CanonicalForm &F, const CFList &M)
 reduce F modulo elements in M. More...
 
CanonicalForm mulMod (const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
 Karatsuba style modular multiplication for multivariate polynomials. More...
 
CanonicalForm prodMod (const CFList &L, const CanonicalForm &M)
 product of all elements in L modulo M via divide-and-conquer. More...
 
CanonicalForm prodMod (const CFList &L, const CFList &M)
 product of all elements in L modulo M via divide-and-conquer. More...
 
CanonicalForm reverse (const CanonicalForm &F, int d)
 
CanonicalForm newtonInverse (const CanonicalForm &F, const int n, const CanonicalForm &M)
 
CanonicalForm newtonDiv (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
 division of F by G wrt Variable (1) modulo M using Newton inversion More...
 
void newtonDivrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
 division with remainder of F by G wrt Variable (1) modulo M using Newton inversion More...
 
static CFList split (const CanonicalForm &F, const int m, const Variable &x)
 
static void divrem32 (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
 
static void divrem21 (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
 
void divrem2 (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
 division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division". More...
 
void divrem (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &MOD)
 division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division". More...
 
bool uniFdivides (const CanonicalForm &A, const CanonicalForm &B)
 divisibility test for univariate polys More...
 

Detailed Description

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

Nomenclature rules: kronSub* -> plain Kronecker substitution reverseSubst* -> reverse Kronecker substitution kronSubRecipro* -> reciprocal Kronecker substitution as described in D. Harvey "Faster polynomial multiplication via multipoint Kronecker substitution"

Author
Martin Lee

Definition in file facMul.cc.

Function Documentation

◆ divFLINTQ()

CanonicalForm divFLINTQ ( const CanonicalForm F,
const CanonicalForm G 
)

Definition at line 178 of file facMul.cc.

179{
180 CanonicalForm A= F;
182
183 fmpq_poly_t FLINTA,FLINTB;
184 convertFacCF2Fmpq_poly_t (FLINTA, A);
185 convertFacCF2Fmpq_poly_t (FLINTB, B);
186
187 fmpq_poly_div (FLINTA, FLINTA, FLINTB);
188 A= convertFmpq_poly_t2FacCF (FLINTA, F.mvar());
189
190 fmpq_poly_clear (FLINTA);
191 fmpq_poly_clear (FLINTB);
192 return A;
193}
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
b *CanonicalForm B
Definition: facBivar.cc:52
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define A
Definition: sirandom.c:24

◆ divNTL()

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

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

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

Definition at line 940 of file facMul.cc.

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

◆ divrem()

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, Ziegler "Fast recursive division".

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

Definition at line 3720 of file facMul.cc.

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

◆ divrem2()

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

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

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

Definition at line 3653 of file facMul.cc.

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

◆ divrem21()

static void divrem21 ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Q,
CanonicalForm R,
const CFList M 
)
inlinestatic

Definition at line 3513 of file facMul.cc.

3515{
3516 CanonicalForm A= mod (F, M);
3517 CanonicalForm B= mod (G, M);
3518 Variable x= Variable (1);
3519 int degB= degree (B, x);
3520 int degA= degree (A, x);
3521 if (degA < degB)
3522 {
3523 Q= 0;
3524 R= A;
3525 return;
3526 }
3527 if (degB < 1)
3528 {
3529 divrem (A, B, Q, R);
3530 Q= mod (Q, M);
3531 R= mod (R, M);
3532 return;
3533 }
3534 int m= (int) ceil ((double) (degB + 1)/2.0) + 1;
3535 ASSERT (4*m >= degA, "expected degree (F, 1) < 2*degree (G, 1)");
3536 CFList splitA= split (A, m, x);
3537 if (splitA.length() == 3)
3538 splitA.insert (0);
3539 if (splitA.length() == 2)
3540 {
3541 splitA.insert (0);
3542 splitA.insert (0);
3543 }
3544 if (splitA.length() == 1)
3545 {
3546 splitA.insert (0);
3547 splitA.insert (0);
3548 splitA.insert (0);
3549 }
3550
3551 CanonicalForm xToM= power (x, m);
3552
3553 CFListIterator i= splitA;
3554 CanonicalForm H= i.getItem();
3555 i++;
3556 H *= xToM;
3557 H += i.getItem();
3558 i++;
3559 H *= xToM;
3560 H += i.getItem();
3561 i++;
3562
3563 divrem32 (H, B, Q, R, M);
3564
3565 CFList splitR= split (R, m, x);
3566 if (splitR.length() == 1)
3567 splitR.insert (0);
3568
3569 H= splitR.getFirst();
3570 H *= xToM;
3571 H += splitR.getLast();
3572 H *= xToM;
3573 H += i.getItem();
3574
3575 CanonicalForm bufQ;
3576 divrem32 (H, B, bufQ, R, M);
3577
3578 Q *= xToM;
3579 Q += bufQ;
3580 return;
3581}
int m
Definition: cfEzgcd.cc:128
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
T getLast() const
Definition: ftmpl_list.cc:309
void insert(const T &)
Definition: ftmpl_list.cc:193
static void divrem32(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3584
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:788

◆ divrem32()

static void divrem32 ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Q,
CanonicalForm R,
const CFList M 
)
inlinestatic

Definition at line 3584 of file facMul.cc.

3586{
3587 CanonicalForm A= mod (F, M);
3588 CanonicalForm B= mod (G, M);
3589 Variable x= Variable (1);
3590 int degB= degree (B, x);
3591 int degA= degree (A, x);
3592 if (degA < degB)
3593 {
3594 Q= 0;
3595 R= A;
3596 return;
3597 }
3598 if (degB < 1)
3599 {
3600 divrem (A, B, Q, R);
3601 Q= mod (Q, M);
3602 R= mod (R, M);
3603 return;
3604 }
3605 int m= (int) ceil ((double) (degB + 1)/ 2.0);
3606 ASSERT (3*m > degA, "expected degree (F, 1) < 3*degree (G, 1)");
3607 CFList splitA= split (A, m, x);
3608 CFList splitB= split (B, m, x);
3609
3610 if (splitA.length() == 2)
3611 {
3612 splitA.insert (0);
3613 }
3614 if (splitA.length() == 1)
3615 {
3616 splitA.insert (0);
3617 splitA.insert (0);
3618 }
3619 CanonicalForm xToM= power (x, m);
3620
3622 CFListIterator i= splitA;
3623 i++;
3624
3625 if (degree (splitA.getFirst(), x) < degree (splitB.getFirst(), x))
3626 {
3627 H= splitA.getFirst()*xToM + i.getItem();
3628 divrem21 (H, splitB.getFirst(), Q, R, M);
3629 }
3630 else
3631 {
3632 R= splitA.getFirst()*xToM + i.getItem() + splitB.getFirst() -
3633 splitB.getFirst()*xToM;
3634 Q= xToM - 1;
3635 }
3636
3637 H= mulMod (Q, splitB.getLast(), M);
3638
3639 R= R*xToM + splitA.getLast() - H;
3640
3641 while (degree (R, x) >= degB)
3642 {
3643 xToM= power (x, degree (R, x) - degB);
3644 Q += LC (R, x)*xToM;
3645 R -= mulMod (LC (R, x), B, M)*xToM;
3646 Q= mod (Q, M);
3647 R= mod (R, M);
3648 }
3649
3650 return;
3651}
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:3084

◆ kronSubFp()

void kronSubFp ( nmod_poly_t  result,
const CanonicalForm A,
int  d 
)

Definition at line 1252 of file facMul.cc.

1253{
1254 int degAy= degree (A);
1255 nmod_poly_init2 (result, getCharacteristic(), d*(degAy + 1));
1256 result->length= d*(degAy + 1);
1257 flint_mpn_zero (result->coeffs, d*(degAy+1));
1258
1259 nmod_poly_t buf;
1260
1261 int k;
1262 for (CFIterator i= A; i.hasTerms(); i++)
1263 {
1264 convertFacCF2nmod_poly_t (buf, i.coeff());
1265 k= i.exp()*d;
1266 flint_mpn_copyi (result->coeffs+k, buf->coeffs, nmod_poly_length(buf));
1267
1269 }
1270 _nmod_poly_normalise (result);
1271}
int k
Definition: cfEzgcd.cc:99
class to iterate through CanonicalForm's
Definition: cf_iter.h:44

◆ kronSubFq()

void kronSubFq ( fq_nmod_poly_t  result,
const CanonicalForm A,
int  d,
const fq_nmod_ctx_t  fq_con 
)

Definition at line 1275 of file facMul.cc.

1277{
1278 int degAy= degree (A);
1279 fq_nmod_poly_init2 (result, d*(degAy + 1), fq_con);
1280 _fq_nmod_poly_set_length (result, d*(degAy + 1), fq_con);
1281 _fq_nmod_vec_zero (result->coeffs, d*(degAy + 1), fq_con);
1282
1283 fq_nmod_poly_t buf1;
1284
1285 nmod_poly_t buf2;
1286
1287 int k;
1288
1289 for (CFIterator i= A; i.hasTerms(); i++)
1290 {
1291 if (i.coeff().inCoeffDomain())
1292 {
1293 convertFacCF2nmod_poly_t (buf2, i.coeff());
1294 fq_nmod_poly_init2 (buf1, 1, fq_con);
1295 fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1297 }
1298 else
1300
1301 k= i.exp()*d;
1302 _fq_nmod_vec_set (result->coeffs+k, buf1->coeffs,
1303 fq_nmod_poly_length (buf1, fq_con), fq_con);
1304
1306 }
1307
1308 _fq_nmod_poly_normalise (result, fq_con);
1309}
CanonicalForm buf2
Definition: facFqBivar.cc:75
CanonicalForm buf1
Definition: facFqBivar.cc:75

◆ kronSubQa() [1/2]

void kronSubQa ( fmpz_poly_t  result,
const CanonicalForm A,
int  d 
)

Definition at line 50 of file facMul.cc.

51{
52 int degAy= degree (A);
53 fmpz_poly_init2 (result, d*(degAy + 1));
54 _fmpz_poly_set_length (result, d*(degAy + 1));
56 for (CFIterator i= A; i.hasTerms(); i++)
57 {
58 if (i.coeff().inBaseDomain())
59 convertCF2initFmpz (fmpz_poly_get_coeff_ptr (result, i.exp()*d), i.coeff());
60 else
61 for (j= i.coeff(); j.hasTerms(); j++)
62 convertCF2initFmpz (fmpz_poly_get_coeff_ptr (result, i.exp()*d+j.exp()),
63 j.coeff());
64 }
65 _fmpz_poly_normalise(result);
66}
int j
Definition: facHensel.cc:110

◆ kronSubQa() [2/2]

void kronSubQa ( fmpz_poly_t  result,
const CanonicalForm A,
int  d1,
int  d2 
)

Definition at line 1357 of file facMul.cc.

1358{
1359 int degAy= degree (A);
1360 fmpz_poly_init2 (result, d1*(degAy + 1));
1361 _fmpz_poly_set_length (result, d1*(degAy + 1));
1362
1363 fmpz_poly_t buf;
1364
1365 int k;
1366 CFIterator j;
1367 for (CFIterator i= A; i.hasTerms(); i++)
1368 {
1369 if (i.coeff().inCoeffDomain())
1370 {
1371 k= d1*i.exp();
1372 convertFacCF2Fmpz_poly_t (buf, i.coeff());
1373 _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1374 fmpz_poly_clear (buf);
1375 }
1376 else
1377 {
1378 for (j= i.coeff(); j.hasTerms(); j++)
1379 {
1380 k= d1*i.exp();
1381 k += d2*j.exp();
1382 convertFacCF2Fmpz_poly_t (buf, j.coeff());
1383 _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1384 fmpz_poly_clear (buf);
1385 }
1386 }
1387 }
1388 _fmpz_poly_normalise (result);
1389}
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t

◆ kronSubReciproFp()

void kronSubReciproFp ( nmod_poly_t  subA1,
nmod_poly_t  subA2,
const CanonicalForm A,
int  d 
)

Definition at line 1392 of file facMul.cc.

1394{
1395 int degAy= degree (A);
1396 mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1397 nmod_poly_init2_preinv (subA1, getCharacteristic(), ninv, d*(degAy + 2));
1398 nmod_poly_init2_preinv (subA2, getCharacteristic(), ninv, d*(degAy + 2));
1399
1400 nmod_poly_t buf;
1401
1402 int k, kk, j, bufRepLength;
1403 for (CFIterator i= A; i.hasTerms(); i++)
1404 {
1405 convertFacCF2nmod_poly_t (buf, i.coeff());
1406
1407 k= i.exp()*d;
1408 kk= (degAy - i.exp())*d;
1409 bufRepLength= (int) nmod_poly_length (buf);
1410 for (j= 0; j < bufRepLength; j++)
1411 {
1412 nmod_poly_set_coeff_ui (subA1, j + k,
1413 n_addmod (nmod_poly_get_coeff_ui (subA1, j+k),
1414 nmod_poly_get_coeff_ui (buf, j),
1416 )
1417 );
1418 nmod_poly_set_coeff_ui (subA2, j + kk,
1419 n_addmod (nmod_poly_get_coeff_ui (subA2, j + kk),
1420 nmod_poly_get_coeff_ui (buf, j),
1422 )
1423 );
1424 }
1426 }
1427 _nmod_poly_normalise (subA1);
1428 _nmod_poly_normalise (subA2);
1429}

◆ kronSubReciproFq()

void kronSubReciproFq ( fq_nmod_poly_t  subA1,
fq_nmod_poly_t  subA2,
const CanonicalForm A,
int  d,
const fq_nmod_ctx_t  fq_con 
)

Definition at line 1433 of file facMul.cc.

1435{
1436 int degAy= degree (A);
1437 fq_nmod_poly_init2 (subA1, d*(degAy + 2), fq_con);
1438 fq_nmod_poly_init2 (subA2, d*(degAy + 2), fq_con);
1439
1440 _fq_nmod_poly_set_length (subA1, d*(degAy + 2), fq_con);
1441 _fq_nmod_vec_zero (subA1->coeffs, d*(degAy + 2), fq_con);
1442
1443 _fq_nmod_poly_set_length (subA2, d*(degAy + 2), fq_con);
1444 _fq_nmod_vec_zero (subA2->coeffs, d*(degAy + 2), fq_con);
1445
1446 fq_nmod_poly_t buf1;
1447
1448 nmod_poly_t buf2;
1449
1450 int k, kk;
1451 for (CFIterator i= A; i.hasTerms(); i++)
1452 {
1453 if (i.coeff().inCoeffDomain())
1454 {
1455 convertFacCF2nmod_poly_t (buf2, i.coeff());
1456 fq_nmod_poly_init2 (buf1, 1, fq_con);
1457 fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1459 }
1460 else
1462
1463 k= i.exp()*d;
1464 kk= (degAy - i.exp())*d;
1465 _fq_nmod_vec_add (subA1->coeffs+k, subA1->coeffs+k, buf1->coeffs,
1466 fq_nmod_poly_length(buf1, fq_con), fq_con);
1467 _fq_nmod_vec_add (subA2->coeffs+kk, subA2->coeffs+kk, buf1->coeffs,
1468 fq_nmod_poly_length(buf1, fq_con), fq_con);
1469
1471 }
1472 _fq_nmod_poly_normalise (subA1, fq_con);
1473 _fq_nmod_poly_normalise (subA2, fq_con);
1474}

◆ kronSubReciproQ()

void kronSubReciproQ ( fmpz_poly_t  subA1,
fmpz_poly_t  subA2,
const CanonicalForm A,
int  d 
)

Definition at line 1478 of file facMul.cc.

1480{
1481 int degAy= degree (A);
1482 fmpz_poly_init2 (subA1, d*(degAy + 2));
1483 fmpz_poly_init2 (subA2, d*(degAy + 2));
1484
1485 fmpz_poly_t buf;
1486
1487 int k, kk;
1488 for (CFIterator i= A; i.hasTerms(); i++)
1489 {
1490 convertFacCF2Fmpz_poly_t (buf, i.coeff());
1491
1492 k= i.exp()*d;
1493 kk= (degAy - i.exp())*d;
1494 _fmpz_vec_add (subA1->coeffs+k, subA1->coeffs + k, buf->coeffs, buf->length);
1495 _fmpz_vec_add (subA2->coeffs+kk, subA2->coeffs + kk, buf->coeffs, buf->length);
1496 fmpz_poly_clear (buf);
1497 }
1498
1499 _fmpz_poly_normalise (subA1);
1500 _fmpz_poly_normalise (subA2);
1501}

◆ mod()

CanonicalForm mod ( const CanonicalForm F,
const CFList M 
)

reduce F modulo elements in M.

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

Definition at line 3076 of file facMul.cc.

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

◆ modFLINTQ()

CanonicalForm modFLINTQ ( const CanonicalForm F,
const CanonicalForm G 
)

Definition at line 196 of file facMul.cc.

197{
198 CanonicalForm A= F;
200
201 fmpq_poly_t FLINTA,FLINTB;
202 convertFacCF2Fmpq_poly_t (FLINTA, A);
203 convertFacCF2Fmpq_poly_t (FLINTB, B);
204
205 fmpq_poly_rem (FLINTA, FLINTA, FLINTB);
206 A= convertFmpq_poly_t2FacCF (FLINTA, F.mvar());
207
208 fmpq_poly_clear (FLINTA);
209 fmpq_poly_clear (FLINTB);
210 return A;
211}

◆ modNTL()

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

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

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

Definition at line 735 of file facMul.cc.

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

◆ mulFLINTQ()

CanonicalForm mulFLINTQ ( const CanonicalForm F,
const CanonicalForm G 
)

Definition at line 137 of file facMul.cc.

138{
139 CanonicalForm A= F;
141
142 CanonicalForm denA= bCommonDen (A);
143 CanonicalForm denB= bCommonDen (B);
144
145 A *= denA;
146 B *= denB;
147 fmpz_poly_t FLINTA,FLINTB;
148 convertFacCF2Fmpz_poly_t (FLINTA, A);
149 convertFacCF2Fmpz_poly_t (FLINTB, B);
150 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
151 denA *= denB;
152 A= convertFmpz_poly_t2FacCF (FLINTA, F.mvar());
153 A /= denA;
154 fmpz_poly_clear (FLINTA);
155 fmpz_poly_clear (FLINTB);
156
157 return A;
158}
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm

◆ mulFLINTQa()

CanonicalForm mulFLINTQa ( const CanonicalForm F,
const CanonicalForm G,
const Variable alpha 
)

Definition at line 107 of file facMul.cc.

109{
110 CanonicalForm A= F;
112
113 CanonicalForm denA= bCommonDen (A);
114 CanonicalForm denB= bCommonDen (B);
115
116 A *= denA;
117 B *= denB;
118 int degAa= degree (A, alpha);
119 int degBa= degree (B, alpha);
120 int d= degAa + 1 + degBa;
121
122 fmpz_poly_t FLINTA,FLINTB;
123 kronSubQa (FLINTA, A, d);
124 kronSubQa (FLINTB, B, d);
125
126 fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
127
128 denA *= denB;
129 A= reverseSubstQa (FLINTA, d, F.mvar(), alpha, denA);
130
131 fmpz_poly_clear (FLINTA);
132 fmpz_poly_clear (FLINTB);
133 return A;
134}
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:50
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
Definition: facMul.cc:70

◆ mulFLINTQaTrunc()

CanonicalForm mulFLINTQaTrunc ( const CanonicalForm F,
const CanonicalForm G,
const Variable alpha,
int  m 
)

Definition at line 214 of file facMul.cc.

216{
217 CanonicalForm A= F;
219
220 CanonicalForm denA= bCommonDen (A);
221 CanonicalForm denB= bCommonDen (B);
222
223 A *= denA;
224 B *= denB;
225
226 int degAa= degree (A, alpha);
227 int degBa= degree (B, alpha);
228 int d= degAa + 1 + degBa;
229
230 fmpz_poly_t FLINTA,FLINTB;
231 kronSubQa (FLINTA, A, d);
232 kronSubQa (FLINTB, B, d);
233
234 int k= d*m;
235 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, k);
236
237 denA *= denB;
238 A= reverseSubstQa (FLINTA, d, F.mvar(), alpha, denA);
239 fmpz_poly_clear (FLINTA);
240 fmpz_poly_clear (FLINTB);
241 return A;
242}

◆ mulFLINTQTrunc()

CanonicalForm mulFLINTQTrunc ( const CanonicalForm F,
const CanonicalForm G,
int  m 
)

Definition at line 245 of file facMul.cc.

246{
247 if (F.inCoeffDomain() && G.inCoeffDomain())
248 return F*G;
249 if (F.inCoeffDomain())
250 return mod (F*G, power (G.mvar(), m));
251 if (G.inCoeffDomain())
252 return mod (F*G, power (F.mvar(), m));
255 return mulFLINTQaTrunc (F, G, alpha, m);
256
257 CanonicalForm A= F;
259
260 CanonicalForm denA= bCommonDen (A);
261 CanonicalForm denB= bCommonDen (B);
262
263 A *= denA;
264 B *= denB;
265 fmpz_poly_t FLINTA,FLINTB;
266 convertFacCF2Fmpz_poly_t (FLINTA, A);
267 convertFacCF2Fmpz_poly_t (FLINTB, B);
268 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, m);
269 denA *= denB;
270 A= convertFmpz_poly_t2FacCF (FLINTA, F.mvar());
271 A /= denA;
272 fmpz_poly_clear (FLINTA);
273 fmpz_poly_clear (FLINTB);
274
275 return A;
276}
CanonicalForm mulFLINTQaTrunc(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, int m)
Definition: facMul.cc:214

◆ mulMod()

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

Karatsuba style modular multiplication for multivariate polynomials.

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

Definition at line 3084 of file facMul.cc.

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

◆ mulMod2()

Karatsuba style modular multiplication for bivariate polynomials.

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

Definition at line 2990 of file facMul.cc.

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

◆ mulMod2FLINTFp()

CanonicalForm mulMod2FLINTFp ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M 
)

Definition at line 2132 of file facMul.cc.

2134{
2135 CanonicalForm A= F;
2136 CanonicalForm B= G;
2137
2138 int degAx= degree (A, 1);
2139 int degAy= degree (A, 2);
2140 int degBx= degree (B, 1);
2141 int degBy= degree (B, 2);
2142 int d1= degAx + 1 + degBx;
2143 int d2= tmax (degAy, degBy);
2144
2145 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy > degree (M)))
2146 return mulMod2FLINTFpReci (A, B, M);
2147
2148 nmod_poly_t FLINTA, FLINTB;
2149 kronSubFp (FLINTA, A, d1);
2150 kronSubFp (FLINTB, B, d1);
2151
2152 int k= d1*degree (M);
2153 nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k);
2154
2155 A= reverseSubstFp (FLINTA, d1);
2156
2157 nmod_poly_clear (FLINTA);
2158 nmod_poly_clear (FLINTB);
2159 return A;
2160}
CanonicalForm reverseSubstFp(const nmod_poly_t F, int d)
Definition: facMul.cc:2058
CanonicalForm mulMod2FLINTFpReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2094
void kronSubFp(nmod_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:1252

◆ mulMod2FLINTFpReci()

CanonicalForm mulMod2FLINTFpReci ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M 
)

Definition at line 2094 of file facMul.cc.

2096{
2097 int d1= degree (F, 1) + degree (G, 1) + 1;
2098 d1 /= 2;
2099 d1 += 1;
2100
2101 nmod_poly_t F1, F2;
2102 kronSubReciproFp (F1, F2, F, d1);
2103
2104 nmod_poly_t G1, G2;
2105 kronSubReciproFp (G1, G2, G, d1);
2106
2107 int k= d1*degree (M);
2108 nmod_poly_mullow (F1, F1, G1, (long) k);
2109
2110 int degtailF= degree (tailcoeff (F), 1);;
2111 int degtailG= degree (tailcoeff (G), 1);
2112 int taildegF= taildegree (F);
2113 int taildegG= taildegree (G);
2114
2115 int b= nmod_poly_degree (F2) + nmod_poly_degree (G2) - k - degtailF - degtailG
2116 + d1*(2+taildegF + taildegG);
2117 nmod_poly_mulhigh (F2, F2, G2, b);
2118 nmod_poly_shift_right (F2, F2, b);
2119 int d2= tmax (nmod_poly_degree (F2)/d1, nmod_poly_degree (F1)/d1);
2120
2121
2122 CanonicalForm result= reverseSubstReciproFp (F1, F2, d1, d2);
2123
2124 nmod_poly_clear (F1);
2125 nmod_poly_clear (F2);
2126 nmod_poly_clear (G1);
2127 nmod_poly_clear (G2);
2128 return result;
2129}
CanonicalForm tailcoeff(const CanonicalForm &f)
int taildegree(const CanonicalForm &f)
void kronSubReciproFp(nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm &A, int d)
Definition: facMul.cc:1392
CanonicalForm reverseSubstReciproFp(const nmod_poly_t F, const nmod_poly_t G, int d, int k)
Definition: facMul.cc:1666

◆ mulMod2FLINTFq()

CanonicalForm mulMod2FLINTFq ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M,
const Variable alpha,
const fq_nmod_ctx_t  fq_con 
)

Definition at line 2206 of file facMul.cc.

2209{
2210 CanonicalForm A= F;
2211 CanonicalForm B= G;
2212
2213 int degAx= degree (A, 1);
2214 int degAy= degree (A, 2);
2215 int degBx= degree (B, 1);
2216 int degBy= degree (B, 2);
2217 int d1= degAx + 1 + degBx;
2218 int d2= tmax (degAy, degBy);
2219
2220 if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy > degree (M)))
2221 return mulMod2FLINTFqReci (A, B, M, alpha, fq_con);
2222
2223 fq_nmod_poly_t FLINTA, FLINTB;
2224 kronSubFq (FLINTA, A, d1, fq_con);
2225 kronSubFq (FLINTB, B, d1, fq_con);
2226
2227 int k= d1*degree (M);
2228 fq_nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k, fq_con);
2229
2230 A= reverseSubstFq (FLINTA, d1, alpha, fq_con);
2231
2232 fq_nmod_poly_clear (FLINTA, fq_con);
2233 fq_nmod_poly_clear (FLINTB, fq_con);
2234 return A;
2235}
void kronSubFq(fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1275
CanonicalForm mulMod2FLINTFqReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:2164
CanonicalForm reverseSubstFq(const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:2023

◆ mulMod2FLINTFqReci()

CanonicalForm mulMod2FLINTFqReci ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M,
const Variable alpha,
const fq_nmod_ctx_t  fq_con 
)

Definition at line 2164 of file facMul.cc.

2167{
2168 int d1= degree (F, 1) + degree (G, 1) + 1;
2169 d1 /= 2;
2170 d1 += 1;
2171
2172 fq_nmod_poly_t F1, F2;
2173 kronSubReciproFq (F1, F2, F, d1, fq_con);
2174
2175 fq_nmod_poly_t G1, G2;
2176 kronSubReciproFq (G1, G2, G, d1, fq_con);
2177
2178 int k= d1*degree (M);
2179 fq_nmod_poly_mullow (F1, F1, G1, (long) k, fq_con);
2180
2181 int degtailF= degree (tailcoeff (F), 1);
2182 int degtailG= degree (tailcoeff (G), 1);
2183 int taildegF= taildegree (F);
2184 int taildegG= taildegree (G);
2185
2186 int b= k + degtailF + degtailG - d1*(2+taildegF + taildegG);
2187
2188 fq_nmod_poly_reverse (F2, F2, fq_nmod_poly_length (F2, fq_con), fq_con);
2189 fq_nmod_poly_reverse (G2, G2, fq_nmod_poly_length (G2, fq_con), fq_con);
2190 fq_nmod_poly_mullow (F2, F2, G2, b+1, fq_con);
2191 fq_nmod_poly_reverse (F2, F2, b+1, fq_con);
2192
2193 int d2= tmax (fq_nmod_poly_degree (F2, fq_con)/d1,
2194 fq_nmod_poly_degree (F1, fq_con)/d1);
2195
2197
2202 return result;
2203}
CanonicalForm reverseSubstReciproFq(const fq_nmod_poly_t F, const fq_nmod_poly_t G, int d, int k, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1785
void kronSubReciproFq(fq_nmod_poly_t subA1, fq_nmod_poly_t subA2, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1433

◆ mulMod2FLINTQ()

CanonicalForm mulMod2FLINTQ ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M 
)

Definition at line 2276 of file facMul.cc.

2278{
2279 CanonicalForm A= F;
2280 CanonicalForm B= G;
2281
2282 int degAx= degree (A, 1);
2283 int degBx= degree (B, 1);
2284 int d1= degAx + 1 + degBx;
2285
2288 A *= f;
2289 B *= g;
2290
2291 fmpz_poly_t FLINTA, FLINTB;
2292 kronSubQa (FLINTA, A, d1);
2293 kronSubQa (FLINTB, B, d1);
2294 int k= d1*degree (M);
2295
2296 fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k);
2297 A= reverseSubstQ (FLINTA, d1);
2298 fmpz_poly_clear (FLINTA);
2299 fmpz_poly_clear (FLINTB);
2300 return A/(f*g);
2301}
g
Definition: cfModGcd.cc:4090
FILE * f
Definition: checklibs.c:9
CanonicalForm reverseSubstQ(const fmpz_poly_t F, int d)
Definition: facMul.cc:1503

◆ mulMod2FLINTQa()

CanonicalForm mulMod2FLINTQa ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M 
)

Definition at line 2336 of file facMul.cc.

2338{
2339 Variable a;
2340 if (!hasFirstAlgVar (F,a) && !hasFirstAlgVar (G, a))
2341 return mulMod2FLINTQ (F, G, M);
2342 CanonicalForm A= F, B= G;
2343
2344 int degFx= degree (F, 1);
2345 int degFa= degree (F, a);
2346 int degGx= degree (G, 1);
2347 int degGa= degree (G, a);
2348
2349 int d2= degFa+degGa+1;
2350 int d1= degFx + 1 + degGx;
2351 d1 *= d2;
2352
2355 A *= f;
2356 B *= g;
2357
2358 fmpz_poly_t FLINTF, FLINTG;
2359 kronSubQa (FLINTF, A, d1, d2);
2360 kronSubQa (FLINTG, B, d1, d2);
2361
2362 fmpz_poly_mullow (FLINTF, FLINTF, FLINTG, d1*degree (M));
2363
2364 fmpq_poly_t mipo;
2366 A= reverseSubstQa (FLINTF, d1, d2, a, mipo);
2367 fmpz_poly_clear (FLINTF);
2368 fmpz_poly_clear (FLINTG);
2369 return A/(f*g);
2370}
CanonicalForm mulMod2FLINTQ(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2276

◆ mulMod2FLINTQReci()

CanonicalForm mulMod2FLINTQReci ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M 
)

Definition at line 2239 of file facMul.cc.

2241{
2242 int d1= degree (F, 1) + degree (G, 1) + 1;
2243 d1 /= 2;
2244 d1 += 1;
2245
2246 fmpz_poly_t F1, F2;
2247 kronSubReciproQ (F1, F2, F, d1);
2248
2249 fmpz_poly_t G1, G2;
2250 kronSubReciproQ (G1, G2, G, d1);
2251
2252 int k= d1*degree (M);
2253 fmpz_poly_mullow (F1, F1, G1, (long) k);
2254
2255 int degtailF= degree (tailcoeff (F), 1);;
2256 int degtailG= degree (tailcoeff (G), 1);
2257 int taildegF= taildegree (F);
2258 int taildegG= taildegree (G);
2259
2260 int b= fmpz_poly_degree (F2) + fmpz_poly_degree (G2) - k - degtailF - degtailG
2261 + d1*(2+taildegF + taildegG);
2262 fmpz_poly_mulhigh_n (F2, F2, G2, b);
2263 fmpz_poly_shift_right (F2, F2, b);
2264 int d2= tmax (fmpz_poly_degree (F2)/d1, fmpz_poly_degree (F1)/d1);
2265
2266 CanonicalForm result= reverseSubstReciproQ (F1, F2, d1, d2);
2267
2268 fmpz_poly_clear (F1);
2269 fmpz_poly_clear (F2);
2270 fmpz_poly_clear (G1);
2271 fmpz_poly_clear (G2);
2272 return result;
2273}
void kronSubReciproQ(fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm &A, int d)
Definition: facMul.cc:1478
CanonicalForm reverseSubstReciproQ(const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
Definition: facMul.cc:1889

◆ mulMod2NTLFq()

CanonicalForm mulMod2NTLFq ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M 
)

Definition at line 2930 of file facMul.cc.

2932{
2934 CanonicalForm A= F;
2935 CanonicalForm B= G;
2936
2938 {
2939#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
2940 nmod_poly_t FLINTmipo;
2941 convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
2942
2943 fq_nmod_ctx_t fq_con;
2944 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
2945
2946 A= mulMod2FLINTFq (A, B, M, alpha, fq_con);
2947 nmod_poly_clear (FLINTmipo);
2949#else
2950 int degAx= degree (A, 1);
2951 int degAy= degree (A, 2);
2952 int degBx= degree (B, 1);
2953 int degBy= degree (B, 2);
2954 int d1= degAx + degBx + 1;
2955 int d2= tmax (degAy, degBy);
2957 {
2960 }
2961 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
2962 zz_pE::init (NTLMipo);
2963
2964 int degMipo= degree (getMipo (alpha));
2965 if ((d1 > 128/degMipo) && (d2 > 160/degMipo) && (degAy == degBy) &&
2966 (2*degAy > degree (M)))
2967 return mulMod2NTLFqReci (A, B, M, alpha);
2968
2969 zz_pEX NTLA= kronSubFq (A, d1, alpha);
2970 zz_pEX NTLB= kronSubFq (B, d1, alpha);
2971
2972 int k= d1*degree (M);
2973
2974 MulTrunc (NTLA, NTLA, NTLB, (long) k);
2975
2976 A= reverseSubstFq (NTLA, d1, alpha);
2977#endif
2978 }
2979 else
2980 {
2981#ifdef HAVE_FLINT
2982 A= mulMod2FLINTFp (A, B, M);
2983#else
2984 A= mulMod2NTLFp (A, B, M);
2985#endif
2986 }
2987 return A;
2988}
CanonicalForm mulMod2FLINTFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:2206
CanonicalForm mulMod2FLINTFp(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2132

◆ mulNTL()

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

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

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

Definition at line 415 of file facMul.cc.

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

◆ newtonDiv() [1/2]

void newtonDiv ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Q 
)

Definition at line 384 of file facMul.cc.

385{
386 ASSERT (F.level() == G.level(), "F and G have different level");
387 CanonicalForm A= F;
389 Variable x= A.mvar();
390 int degA= degree (A);
391 int degB= degree (B);
392 int m= degA - degB;
393
394 if (m < 0)
395 {
396 Q= 0;
397 return;
398 }
399
400 if (degB <= 1)
401 Q= div (A, B);
402 else
403 {
404 CanonicalForm R= uniReverse (A, degA, x);
405 CanonicalForm revB= uniReverse (B, degB, x);
406 revB= newtonInverse (revB, m + 1, x);
407 Q= mulFLINTQTrunc (R, revB, m + 1);
408 Q= uniReverse (Q, m, x);
409 }
410}
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
Definition: facMul.cc:278
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
Definition: facMul.cc:245
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:295

◆ newtonDiv() [2/2]

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

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

Definition at line 3317 of file facMul.cc.

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

◆ newtonDivrem() [1/2]

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

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

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

Definition at line 350 of file facMul.cc.

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

◆ newtonDivrem() [2/2]

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

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

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

Definition at line 3396 of file facMul.cc.

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

◆ newtonInverse() [1/2]

CanonicalForm newtonInverse ( const CanonicalForm F,
const int  n,
const CanonicalForm M 
)

Definition at line 3262 of file facMul.cc.

3263{
3264 int l= ilog2(n);
3265
3266 CanonicalForm g= mod (F, M)[0] [0];
3267
3268 ASSERT (!g.isZero(), "expected a unit");
3269
3271
3272 if (!g.isOne())
3273 g = 1/g;
3274 Variable x= Variable (1);
3276 int exp= 0;
3277 if (n & 1)
3278 {
3279 result= g;
3280 exp= 1;
3281 }
3283
3284 for (int i= 1; i <= l; i++)
3285 {
3286 h= mulMod2 (g, mod (F, power (x, (1 << i))), M);
3287 h= mod (h, power (x, (1 << i)) - 1);
3288 h= div (h, power (x, (1 << (i - 1))));
3289 h= mod (h, M);
3290 g -= power (x, (1 << (i - 1)))*
3291 mod (mulMod2 (g, h, M), power (x, (1 << (i - 1))));
3292
3293 if (n & (1 << i))
3294 {
3295 if (exp)
3296 {
3297 h= mulMod2 (result, mod (F, power (x, exp + (1 << i))), M);
3298 h= mod (h, power (x, exp + (1 << i)) - 1);
3299 h= div (h, power (x, exp));
3300 h= mod (h, M);
3301 result -= power(x, exp)*mod (mulMod2 (g, h, M),
3302 power (x, (1 << i)));
3303 exp += (1 << i);
3304 }
3305 else
3306 {
3307 exp= (1 << i);
3308 result= g;
3309 }
3310 }
3311 }
3312
3313 return result;
3314}
int ilog2(const CanonicalForm &a)
int l
Definition: cfEzgcd.cc:100
STATIC_VAR Poly * h
Definition: janet.cc:971
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357

◆ newtonInverse() [2/2]

CanonicalForm newtonInverse ( const CanonicalForm F,
const int  n,
const Variable x 
)

Definition at line 295 of file facMul.cc.

296{
297 int l= ilog2(n);
298
300 if (F.inCoeffDomain())
301 g= F;
302 else
303 g= F [0];
304
305 if (!F.inCoeffDomain())
306 ASSERT (F.mvar() == x, "main variable of F and x differ");
307 ASSERT (!g.isZero(), "expected a unit");
308
309 if (!g.isOne())
310 g = 1/g;
312 int exp= 0;
313 if (n & 1)
314 {
315 result= g;
316 exp= 1;
317 }
319
320 for (int i= 1; i <= l; i++)
321 {
322 h= mulNTL (g, mod (F, power (x, (1 << i))));
323 h= mod (h, power (x, (1 << i)) - 1);
324 h= div (h, power (x, (1 << (i - 1))));
325 g -= power (x, (1 << (i - 1)))*
326 mulFLINTQTrunc (g, h, 1 << (i-1));
327
328 if (n & (1 << i))
329 {
330 if (exp)
331 {
332 h= mulNTL (result, mod (F, power (x, exp + (1 << i))));
333 h= mod (h, power (x, exp + (1 << i)) - 1);
334 h= div (h, power (x, exp));
335 result -= power(x, exp)*mulFLINTQTrunc (g, h, 1 << i);
336 exp += (1 << i);
337 }
338 else
339 {
340 exp= (1 << i);
341 result= g;
342 }
343 }
344 }
345
346 return result;
347}

◆ prodMod() [1/2]

CanonicalForm prodMod ( const CFList L,
const CanonicalForm M 
)

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

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

Definition at line 3184 of file facMul.cc.

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

◆ prodMod() [2/2]

CanonicalForm prodMod ( const CFList L,
const CFList M 
)

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

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

Definition at line 3211 of file facMul.cc.

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

◆ reverse()

CanonicalForm reverse ( const CanonicalForm F,
int  d 
)

Definition at line 3238 of file facMul.cc.

3239{
3240 if (d == 0)
3241 return F;
3242 CanonicalForm A= F;
3243 Variable y= Variable (2);
3244 Variable x= Variable (1);
3245 if (degree (A, x) > 0)
3246 {
3247 A= swapvar (A, x, y);
3249 CFIterator i= A;
3250 while (d - i.exp() < 0)
3251 i++;
3252
3253 for (; i.hasTerms() && (d - i.exp() >= 0); i++)
3254 result += swapvar (i.coeff(),x,y)*power (x, d - i.exp());
3255 return result;
3256 }
3257 else
3258 return A*power (x, d);
3259}

◆ reverseSubstFp()

CanonicalForm reverseSubstFp ( const nmod_poly_t  F,
int  d 
)

Definition at line 2058 of file facMul.cc.

2059{
2060 Variable y= Variable (2);
2061 Variable x= Variable (1);
2062
2063 mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
2064
2065 nmod_poly_t buf;
2067 int i= 0;
2068 int degf= nmod_poly_degree(F);
2069 int k= 0;
2070 int degfSubK, repLength, j;
2071 while (degf >= k)
2072 {
2073 degfSubK= degf - k;
2074 if (degfSubK >= d)
2075 repLength= d;
2076 else
2077 repLength= degfSubK + 1;
2078
2079 nmod_poly_init2_preinv (buf, getCharacteristic(), ninv, repLength);
2080 for (j= 0; j < repLength; j++)
2081 nmod_poly_set_coeff_ui (buf, j, nmod_poly_get_coeff_ui (F, j + k));
2082 _nmod_poly_normalise (buf);
2083
2085 i++;
2086 k= d*i;
2088 }
2089
2090 return result;
2091}

◆ reverseSubstFq()

CanonicalForm reverseSubstFq ( const fq_nmod_poly_t  F,
int  d,
const Variable alpha,
const fq_nmod_ctx_t  fq_con 
)

Definition at line 2023 of file facMul.cc.

2025{
2026 Variable y= Variable (2);
2027 Variable x= Variable (1);
2028
2029 fq_nmod_poly_t buf;
2031 int i= 0;
2032 int degf= fq_nmod_poly_degree(F, fq_con);
2033 int k= 0;
2034 int degfSubK, repLength;
2035 while (degf >= k)
2036 {
2037 degfSubK= degf - k;
2038 if (degfSubK >= d)
2039 repLength= d;
2040 else
2041 repLength= degfSubK + 1;
2042
2043 fq_nmod_poly_init2 (buf, repLength, fq_con);
2044 _fq_nmod_poly_set_length (buf, repLength, fq_con);
2045 _fq_nmod_vec_set (buf->coeffs, F->coeffs+k, repLength, fq_con);
2046 _fq_nmod_poly_normalise (buf, fq_con);
2047
2049 i++;
2050 k= d*i;
2052 }
2053
2054 return result;
2055}

◆ reverseSubstQ()

CanonicalForm reverseSubstQ ( const fmpz_poly_t  F,
int  d 
)

Definition at line 1503 of file facMul.cc.

1504{
1505 Variable y= Variable (2);
1506 Variable x= Variable (1);
1507
1508 fmpz_poly_t buf;
1510 int i= 0;
1511 int degf= fmpz_poly_degree(F);
1512 int k= 0;
1513 int degfSubK, repLength;
1514 while (degf >= k)
1515 {
1516 degfSubK= degf - k;
1517 if (degfSubK >= d)
1518 repLength= d;
1519 else
1520 repLength= degfSubK + 1;
1521
1522 fmpz_poly_init2 (buf, repLength);
1523 _fmpz_poly_set_length (buf, repLength);
1524 _fmpz_vec_set (buf->coeffs, F->coeffs+k, repLength);
1525 _fmpz_poly_normalise (buf);
1526
1528 i++;
1529 k= d*i;
1530 fmpz_poly_clear (buf);
1531 }
1532
1533 return result;
1534}

◆ reverseSubstQa() [1/2]

CanonicalForm reverseSubstQa ( const fmpz_poly_t  F,
int  d,
const Variable x,
const Variable alpha,
const CanonicalForm den 
)

Definition at line 70 of file facMul.cc.

72{
74 int i= 0;
75 int degf= fmpz_poly_degree (F);
76 int k= 0;
77 int degfSubK;
78 int repLength;
79 fmpq_poly_t buf;
80 fmpq_poly_t mipo;
82 while (degf >= k)
83 {
84 degfSubK= degf - k;
85 if (degfSubK >= d)
86 repLength= d;
87 else
88 repLength= degfSubK + 1;
89
90 fmpq_poly_init2 (buf, repLength);
91 _fmpq_poly_set_length (buf, repLength);
92 _fmpz_vec_set (buf->coeffs, F->coeffs + k, repLength);
93 _fmpq_poly_normalise (buf);
94 fmpq_poly_rem (buf, buf, mipo);
95
97 fmpq_poly_clear (buf);
98 i++;
99 k= d*i;
100 }
101 fmpq_poly_clear (mipo);
102 result /= den;
103 return result;
104}
CanonicalForm den(const CanonicalForm &f)

◆ reverseSubstQa() [2/2]

CanonicalForm reverseSubstQa ( const fmpz_poly_t  F,
int  d1,
int  d2,
const Variable alpha,
const fmpq_poly_t  mipo 
)

Definition at line 1609 of file facMul.cc.

1611{
1612 Variable y= Variable (2);
1613 Variable x= Variable (1);
1614
1615 fmpq_poly_t buf;
1616 CanonicalForm result= 0, result2;
1617 int i= 0;
1618 int degf= fmpz_poly_degree(F);
1619 int k= 0;
1620 int degfSubK;
1621 int repLength;
1622 while (degf >= k)
1623 {
1624 degfSubK= degf - k;
1625 if (degfSubK >= d1)
1626 repLength= d1;
1627 else
1628 repLength= degfSubK + 1;
1629
1630 int j= 0;
1631 result2= 0;
1632 while (j*d2 < repLength)
1633 {
1634 fmpq_poly_init2 (buf, d2);
1635 _fmpq_poly_set_length (buf, d2);
1636 _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, d2);
1637 _fmpq_poly_normalise (buf);
1638 fmpq_poly_rem (buf, buf, mipo);
1639 result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1640 j++;
1641 fmpq_poly_clear (buf);
1642 }
1643 if (repLength - j*d2 != 0 && j*d2 - repLength < d2)
1644 {
1645 j--;
1646 repLength -= j*d2;
1647 fmpq_poly_init2 (buf, repLength);
1648 _fmpq_poly_set_length (buf, repLength);
1649 j++;
1650 _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, repLength);
1651 _fmpq_poly_normalise (buf);
1652 fmpq_poly_rem (buf, buf, mipo);
1653 result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1654 fmpq_poly_clear (buf);
1655 }
1656
1657 result += result2*power (y, i);
1658 i++;
1659 k= d1*i;
1660 }
1661
1662 return result;
1663}

◆ reverseSubstReciproFp()

CanonicalForm reverseSubstReciproFp ( const nmod_poly_t  F,
const nmod_poly_t  G,
int  d,
int  k 
)

Definition at line 1666 of file facMul.cc.

1667{
1668 Variable y= Variable (2);
1669 Variable x= Variable (1);
1670
1671 nmod_poly_t f, g;
1672 mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1673 nmod_poly_init_preinv (f, getCharacteristic(), ninv);
1674 nmod_poly_init_preinv (g, getCharacteristic(), ninv);
1675 nmod_poly_set (f, F);
1676 nmod_poly_set (g, G);
1677 int degf= nmod_poly_degree(f);
1678 int degg= nmod_poly_degree(g);
1679
1680
1681 nmod_poly_t buf1,buf2, buf3;
1682
1683 if (nmod_poly_length (f) < (long) d*(k+1)) //zero padding
1684 nmod_poly_fit_length (f,(long)d*(k+1));
1685
1687 int i= 0;
1688 int lf= 0;
1689 int lg= d*k;
1690 int degfSubLf= degf;
1691 int deggSubLg= degg-lg;
1692 int repLengthBuf2, repLengthBuf1, ind, tmp;
1693 while (degf >= lf || lg >= 0)
1694 {
1695 if (degfSubLf >= d)
1696 repLengthBuf1= d;
1697 else if (degfSubLf < 0)
1698 repLengthBuf1= 0;
1699 else
1700 repLengthBuf1= degfSubLf + 1;
1701 nmod_poly_init2_preinv (buf1, getCharacteristic(), ninv, repLengthBuf1);
1702
1703 for (ind= 0; ind < repLengthBuf1; ind++)
1704 nmod_poly_set_coeff_ui (buf1, ind, nmod_poly_get_coeff_ui (f, ind+lf));
1705 _nmod_poly_normalise (buf1);
1706
1707 repLengthBuf1= nmod_poly_length (buf1);
1708
1709 if (deggSubLg >= d - 1)
1710 repLengthBuf2= d - 1;
1711 else if (deggSubLg < 0)
1712 repLengthBuf2= 0;
1713 else
1714 repLengthBuf2= deggSubLg + 1;
1715
1716 nmod_poly_init2_preinv (buf2, getCharacteristic(), ninv, repLengthBuf2);
1717 for (ind= 0; ind < repLengthBuf2; ind++)
1718 nmod_poly_set_coeff_ui (buf2, ind, nmod_poly_get_coeff_ui (g, ind + lg));
1719
1720 _nmod_poly_normalise (buf2);
1721 repLengthBuf2= nmod_poly_length (buf2);
1722
1723 nmod_poly_init2_preinv (buf3, getCharacteristic(), ninv, repLengthBuf2 + d);
1724 for (ind= 0; ind < repLengthBuf1; ind++)
1725 nmod_poly_set_coeff_ui (buf3, ind, nmod_poly_get_coeff_ui (buf1, ind));
1726 for (ind= repLengthBuf1; ind < d; ind++)
1727 nmod_poly_set_coeff_ui (buf3, ind, 0);
1728 for (ind= 0; ind < repLengthBuf2; ind++)
1729 nmod_poly_set_coeff_ui (buf3, ind+d, nmod_poly_get_coeff_ui (buf2, ind));
1730 _nmod_poly_normalise (buf3);
1731
1732 result += convertnmod_poly_t2FacCF (buf3, x)*power (y, i);
1733 i++;
1734
1735
1736 lf= i*d;
1737 degfSubLf= degf - lf;
1738
1739 lg= d*(k-i);
1740 deggSubLg= degg - lg;
1741
1742 if (lg >= 0 && deggSubLg > 0)
1743 {
1744 if (repLengthBuf2 > degfSubLf + 1)
1745 degfSubLf= repLengthBuf2 - 1;
1746 tmp= tmin (repLengthBuf1, deggSubLg + 1);
1747 for (ind= 0; ind < tmp; ind++)
1748 nmod_poly_set_coeff_ui (g, ind + lg,
1749 n_submod (nmod_poly_get_coeff_ui (g, ind + lg),
1750 nmod_poly_get_coeff_ui (buf1, ind),
1752 )
1753 );
1754 }
1755 if (lg < 0)
1756 {
1759 nmod_poly_clear (buf3);
1760 break;
1761 }
1762 if (degfSubLf >= 0)
1763 {
1764 for (ind= 0; ind < repLengthBuf2; ind++)
1765 nmod_poly_set_coeff_ui (f, ind + lf,
1766 n_submod (nmod_poly_get_coeff_ui (f, ind + lf),
1767 nmod_poly_get_coeff_ui (buf2, ind),
1769 )
1770 );
1771 }
1774 nmod_poly_clear (buf3);
1775 }
1776
1779
1780 return result;
1781}
int degg
Definition: facAlgExt.cc:64
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)

◆ reverseSubstReciproFq()

CanonicalForm reverseSubstReciproFq ( const fq_nmod_poly_t  F,
const fq_nmod_poly_t  G,
int  d,
int  k,
const Variable alpha,
const fq_nmod_ctx_t  fq_con 
)

Definition at line 1785 of file facMul.cc.

1787{
1788 Variable y= Variable (2);
1789 Variable x= Variable (1);
1790
1791 fq_nmod_poly_t f, g;
1792 int degf= fq_nmod_poly_degree(F, fq_con);
1793 int degg= fq_nmod_poly_degree(G, fq_con);
1794
1795 fq_nmod_poly_t buf1,buf2, buf3;
1796
1799 fq_nmod_poly_set (f, F, fq_con);
1800 fq_nmod_poly_set (g, G, fq_con);
1801 if (fq_nmod_poly_length (f, fq_con) < (long) d*(k + 1)) //zero padding
1802 fq_nmod_poly_fit_length (f, (long) d*(k + 1), fq_con);
1803
1805 int i= 0;
1806 int lf= 0;
1807 int lg= d*k;
1808 int degfSubLf= degf;
1809 int deggSubLg= degg-lg;
1810 int repLengthBuf2, repLengthBuf1, tmp;
1811 while (degf >= lf || lg >= 0)
1812 {
1813 if (degfSubLf >= d)
1814 repLengthBuf1= d;
1815 else if (degfSubLf < 0)
1816 repLengthBuf1= 0;
1817 else
1818 repLengthBuf1= degfSubLf + 1;
1819 fq_nmod_poly_init2 (buf1, repLengthBuf1, fq_con);
1820 _fq_nmod_poly_set_length (buf1, repLengthBuf1, fq_con);
1821
1822 _fq_nmod_vec_set (buf1->coeffs, f->coeffs + lf, repLengthBuf1, fq_con);
1823 _fq_nmod_poly_normalise (buf1, fq_con);
1824
1825 repLengthBuf1= fq_nmod_poly_length (buf1, fq_con);
1826
1827 if (deggSubLg >= d - 1)
1828 repLengthBuf2= d - 1;
1829 else if (deggSubLg < 0)
1830 repLengthBuf2= 0;
1831 else
1832 repLengthBuf2= deggSubLg + 1;
1833
1834 fq_nmod_poly_init2 (buf2, repLengthBuf2, fq_con);
1835 _fq_nmod_poly_set_length (buf2, repLengthBuf2, fq_con);
1836 _fq_nmod_vec_set (buf2->coeffs, g->coeffs + lg, repLengthBuf2, fq_con);
1837
1838 _fq_nmod_poly_normalise (buf2, fq_con);
1839 repLengthBuf2= fq_nmod_poly_length (buf2, fq_con);
1840
1841 fq_nmod_poly_init2 (buf3, repLengthBuf2 + d, fq_con);
1842 _fq_nmod_poly_set_length (buf3, repLengthBuf2 + d, fq_con);
1843 _fq_nmod_vec_set (buf3->coeffs, buf1->coeffs, repLengthBuf1, fq_con);
1844 _fq_nmod_vec_set (buf3->coeffs + d, buf2->coeffs, repLengthBuf2, fq_con);
1845
1846 _fq_nmod_poly_normalise (buf3, fq_con);
1847
1849 i++;
1850
1851
1852 lf= i*d;
1853 degfSubLf= degf - lf;
1854
1855 lg= d*(k - i);
1856 deggSubLg= degg - lg;
1857
1858 if (lg >= 0 && deggSubLg > 0)
1859 {
1860 if (repLengthBuf2 > degfSubLf + 1)
1861 degfSubLf= repLengthBuf2 - 1;
1862 tmp= tmin (repLengthBuf1, deggSubLg + 1);
1863 _fq_nmod_vec_sub (g->coeffs + lg, g->coeffs + lg, buf1-> coeffs,
1864 tmp, fq_con);
1865 }
1866 if (lg < 0)
1867 {
1870 fq_nmod_poly_clear (buf3, fq_con);
1871 break;
1872 }
1873 if (degfSubLf >= 0)
1874 _fq_nmod_vec_sub (f->coeffs + lf, f->coeffs + lf, buf2->coeffs,
1875 repLengthBuf2, fq_con);
1878 fq_nmod_poly_clear (buf3, fq_con);
1879 }
1880
1883
1884 return result;
1885}
fq_nmod_poly_init(prod, fq_con)
The main handler for Singular numbers which are suitable for Singular polynomials.

◆ reverseSubstReciproQ()

CanonicalForm reverseSubstReciproQ ( const fmpz_poly_t  F,
const fmpz_poly_t  G,
int  d,
int  k 
)

Definition at line 1889 of file facMul.cc.

1890{
1891 Variable y= Variable (2);
1892 Variable x= Variable (1);
1893
1894 fmpz_poly_t f, g;
1895 fmpz_poly_init (f);
1896 fmpz_poly_init (g);
1897 fmpz_poly_set (f, F);
1898 fmpz_poly_set (g, G);
1899 int degf= fmpz_poly_degree(f);
1900 int degg= fmpz_poly_degree(g);
1901
1902 fmpz_poly_t buf1,buf2, buf3;
1903
1904 if (fmpz_poly_length (f) < (long) d*(k+1)) //zero padding
1905 fmpz_poly_fit_length (f,(long)d*(k+1));
1906
1908 int i= 0;
1909 int lf= 0;
1910 int lg= d*k;
1911 int degfSubLf= degf;
1912 int deggSubLg= degg-lg;
1913 int repLengthBuf2, repLengthBuf1, ind, tmp;
1914 fmpz_t tmp1, tmp2;
1915 while (degf >= lf || lg >= 0)
1916 {
1917 if (degfSubLf >= d)
1918 repLengthBuf1= d;
1919 else if (degfSubLf < 0)
1920 repLengthBuf1= 0;
1921 else
1922 repLengthBuf1= degfSubLf + 1;
1923
1924 fmpz_poly_init2 (buf1, repLengthBuf1);
1925
1926 for (ind= 0; ind < repLengthBuf1; ind++)
1927 {
1928 fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
1929 fmpz_poly_set_coeff_fmpz (buf1, ind, tmp1);
1930 }
1931 _fmpz_poly_normalise (buf1);
1932
1933 repLengthBuf1= fmpz_poly_length (buf1);
1934
1935 if (deggSubLg >= d - 1)
1936 repLengthBuf2= d - 1;
1937 else if (deggSubLg < 0)
1938 repLengthBuf2= 0;
1939 else
1940 repLengthBuf2= deggSubLg + 1;
1941
1942 fmpz_poly_init2 (buf2, repLengthBuf2);
1943
1944 for (ind= 0; ind < repLengthBuf2; ind++)
1945 {
1946 fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1947 fmpz_poly_set_coeff_fmpz (buf2, ind, tmp1);
1948 }
1949
1950 _fmpz_poly_normalise (buf2);
1951 repLengthBuf2= fmpz_poly_length (buf2);
1952
1953 fmpz_poly_init2 (buf3, repLengthBuf2 + d);
1954 for (ind= 0; ind < repLengthBuf1; ind++)
1955 {
1956 fmpz_poly_get_coeff_fmpz (tmp1, buf1, ind);
1957 fmpz_poly_set_coeff_fmpz (buf3, ind, tmp1);
1958 }
1959 for (ind= repLengthBuf1; ind < d; ind++)
1960 fmpz_poly_set_coeff_ui (buf3, ind, 0);
1961 for (ind= 0; ind < repLengthBuf2; ind++)
1962 {
1963 fmpz_poly_get_coeff_fmpz (tmp1, buf2, ind);
1964 fmpz_poly_set_coeff_fmpz (buf3, ind + d, tmp1);
1965 }
1966 _fmpz_poly_normalise (buf3);
1967
1968 result += convertFmpz_poly_t2FacCF (buf3, x)*power (y, i);
1969 i++;
1970
1971
1972 lf= i*d;
1973 degfSubLf= degf - lf;
1974
1975 lg= d*(k-i);
1976 deggSubLg= degg - lg;
1977
1978 if (lg >= 0 && deggSubLg > 0)
1979 {
1980 if (repLengthBuf2 > degfSubLf + 1)
1981 degfSubLf= repLengthBuf2 - 1;
1982 tmp= tmin (repLengthBuf1, deggSubLg + 1);
1983 for (ind= 0; ind < tmp; ind++)
1984 {
1985 fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1986 fmpz_poly_get_coeff_fmpz (tmp2, buf1, ind);
1987 fmpz_sub (tmp1, tmp1, tmp2);
1988 fmpz_poly_set_coeff_fmpz (g, ind + lg, tmp1);
1989 }
1990 }
1991 if (lg < 0)
1992 {
1993 fmpz_poly_clear (buf1);
1994 fmpz_poly_clear (buf2);
1995 fmpz_poly_clear (buf3);
1996 break;
1997 }
1998 if (degfSubLf >= 0)
1999 {
2000 for (ind= 0; ind < repLengthBuf2; ind++)
2001 {
2002 fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
2003 fmpz_poly_get_coeff_fmpz (tmp2, buf2, ind);
2004 fmpz_sub (tmp1, tmp1, tmp2);
2005 fmpz_poly_set_coeff_fmpz (f, ind + lf, tmp1);
2006 }
2007 }
2008 fmpz_poly_clear (buf1);
2009 fmpz_poly_clear (buf2);
2010 fmpz_poly_clear (buf3);
2011 }
2012
2013 fmpz_poly_clear (f);
2014 fmpz_poly_clear (g);
2015 fmpz_clear (tmp1);
2016 fmpz_clear (tmp2);
2017
2018 return result;
2019}

◆ split()

static CFList split ( const CanonicalForm F,
const int  m,
const Variable x 
)
inlinestatic

Definition at line 3473 of file facMul.cc.

3474{
3475 CanonicalForm A= F;
3476 CanonicalForm buf= 0;
3477 bool swap= false;
3478 if (degree (A, x) <= 0)
3479 return CFList(A);
3480 else if (x.level() != A.level())
3481 {
3482 swap= true;
3483 A= swapvar (A, x, A.mvar());
3484 }
3485
3486 int j= (int) floor ((double) degree (A)/ m);
3487 CFList result;
3488 CFIterator i= A;
3489 for (; j >= 0; j--)
3490 {
3491 while (i.hasTerms() && i.exp() - j*m >= 0)
3492 {
3493 if (swap)
3494 buf += i.coeff()*power (A.mvar(), i.exp() - j*m);
3495 else
3496 buf += i.coeff()*power (x, i.exp() - j*m);
3497 i++;
3498 }
3499 if (swap)
3500 result.append (swapvar (buf, x, F.mvar()));
3501 else
3502 result.append (buf);
3503 buf= 0;
3504 }
3505 return result;
3506}
#define swap(_i, _j)
int level() const
Definition: factory.h:143
const signed long floor(const ampf< Precision > &x)
Definition: amp.h:773

◆ uniFdivides()

bool uniFdivides ( const CanonicalForm A,
const CanonicalForm B 
)

divisibility test for univariate polys

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

Definition at line 3763 of file facMul.cc.

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

◆ uniReverse()

CanonicalForm uniReverse ( const CanonicalForm F,
int  d,
const Variable x 
)

Definition at line 278 of file facMul.cc.

279{
280 if (d == 0)
281 return F;
282 if (F.inCoeffDomain())
283 return F*power (x,d);
285 CFIterator i= F;
286 while (d - i.exp() < 0)
287 i++;
288
289 for (; i.hasTerms() && (d - i.exp() >= 0); i++)
290 result += i.coeff()*power (x, d - i.exp());
291 return result;
292}