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 "templates/ftmpl_functions.h"
#include <NTL/lzz_pEX.h>
#include "NTLconvert.h"
#include "FLINTconvert.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 170 of file facMul.cc.

171 {
172  CanonicalForm A= F;
173  CanonicalForm B= G;
174 
175  fmpq_poly_t FLINTA,FLINTB;
176  convertFacCF2Fmpq_poly_t (FLINTA, A);
177  convertFacCF2Fmpq_poly_t (FLINTB, B);
178 
179  fmpq_poly_div (FLINTA, FLINTA, FLINTB);
180  A= convertFmpq_poly_t2FacCF (FLINTA, F.mvar());
181 
182  fmpq_poly_clear (FLINTA);
183  fmpq_poly_clear (FLINTB);
184  return A;
185 }
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:32
#define A
Definition: sirandom.c:23
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm

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

851 {
853  return div (F, G);
854  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
855  {
856  return 0;
857  }
858  else if (F.inCoeffDomain() && G.inCoeffDomain())
859  {
860  if (b.getp() != 0)
861  {
862  if (!F.inBaseDomain() || !G.inBaseDomain())
863  {
864  Variable alpha;
865  hasFirstAlgVar (F, alpha);
866  hasFirstAlgVar (G, alpha);
867 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
868  fmpz_t FLINTp;
869  fmpz_mod_poly_t FLINTmipo;
870  fq_ctx_t fq_con;
871  fq_t FLINTF, FLINTG;
872 
873  fmpz_init (FLINTp);
874  convertCF2Fmpz (FLINTp, b.getpk());
875 
876  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
877 
878  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
879 
880  convertFacCF2Fq_t (FLINTF, F, fq_con);
881  convertFacCF2Fq_t (FLINTG, G, fq_con);
882 
883  fq_inv (FLINTG, FLINTG, fq_con);
884  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
885 
886  CanonicalForm result= convertFq_t2FacCF (FLINTF, alpha);
887 
888  fmpz_clear (FLINTp);
889  fmpz_mod_poly_clear (FLINTmipo);
890  fq_clear (FLINTF, fq_con);
891  fq_clear (FLINTG, fq_con);
892  fq_ctx_clear (fq_con);
893  return b (result);
894 #else
895  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
896  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
897  ZZ_pE::init (NTLmipo);
898  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
899  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
900  ZZ_pE result;
901  div (result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
902  return b (convertNTLZZpX2CF (rep (result), alpha));
903 #endif
904  }
905  return b(div (F,G));
906  }
907  return div (F, G);
908  }
909  else if (F.isUnivariate() && G.inCoeffDomain())
910  {
911  if (b.getp() != 0)
912  {
913  if (!G.inBaseDomain())
914  {
915  Variable alpha;
916  hasFirstAlgVar (G, alpha);
917 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
918  fmpz_t FLINTp;
919  fmpz_mod_poly_t FLINTmipo;
920  fq_ctx_t fq_con;
921  fq_poly_t FLINTF;
922  fq_t FLINTG;
923 
924  fmpz_init (FLINTp);
925  convertCF2Fmpz (FLINTp, b.getpk());
926 
927  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
928 
929  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
930 
931  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
932  convertFacCF2Fq_t (FLINTG, G, fq_con);
933 
934  fq_inv (FLINTG, FLINTG, fq_con);
935  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
936 
937  CanonicalForm result= convertFq_poly_t2FacCF (FLINTF, F.mvar(),
938  alpha, fq_con);
939 
940  fmpz_clear (FLINTp);
941  fmpz_mod_poly_clear (FLINTmipo);
942  fq_poly_clear (FLINTF, fq_con);
943  fq_clear (FLINTG, fq_con);
944  fq_ctx_clear (fq_con);
945  return b (result);
946 #else
947  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
948  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
949  ZZ_pE::init (NTLmipo);
950  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
951  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
952  div (NTLf, NTLf, to_ZZ_pE (NTLg));
953  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
954 #endif
955  }
956  return b(div (F,G));
957  }
958  return div (F, G);
959  }
960 
961  if (getCharacteristic() == 0)
962  {
963 
964  Variable alpha;
965  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
966  {
967 #ifdef HAVE_FLINT
968  if (b.getp() != 0)
969  {
970  fmpz_t FLINTpk;
971  fmpz_init (FLINTpk);
972  convertCF2Fmpz (FLINTpk, b.getpk());
973  fmpz_mod_poly_t FLINTF, FLINTG;
974  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
975  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
976  fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
977  CanonicalForm result= convertFmpz_mod_poly_t2FacCF (FLINTF,F.mvar(),b);
978  fmpz_mod_poly_clear (FLINTG);
979  fmpz_mod_poly_clear (FLINTF);
980  fmpz_clear (FLINTpk);
981  return result;
982  }
983  return divFLINTQ (F,G);
984 #else
985  if (b.getp() != 0)
986  {
987  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
988  ZZX ZZf= convertFacCF2NTLZZX (F);
989  ZZX ZZg= convertFacCF2NTLZZX (G);
990  ZZ_pX NTLf= to_ZZ_pX (ZZf);
991  ZZ_pX NTLg= to_ZZ_pX (ZZg);
992  div (NTLf, NTLf, NTLg);
993  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
994  }
995  return div (F, G);
996 #endif
997  }
998  else
999  {
1000  if (b.getp() != 0)
1001  {
1002 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1003  fmpz_t FLINTp;
1004  fmpz_mod_poly_t FLINTmipo;
1005  fq_ctx_t fq_con;
1006  fq_poly_t FLINTF, FLINTG;
1007 
1008  fmpz_init (FLINTp);
1009  convertCF2Fmpz (FLINTp, b.getpk());
1010 
1011  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
1012 
1013  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1014 
1015  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
1016  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
1017 
1018  fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1019 
1020  CanonicalForm result= convertFq_poly_t2FacCF (FLINTF, F.mvar(),
1021  alpha, fq_con);
1022 
1023  fmpz_clear (FLINTp);
1024  fmpz_mod_poly_clear (FLINTmipo);
1025  fq_ctx_clear (fq_con);
1026  fq_poly_clear (FLINTF, fq_con);
1027  fq_poly_clear (FLINTG, fq_con);
1028  return b (result);
1029 #else
1030  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1031  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
1032  ZZ_pE::init (NTLmipo);
1033  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
1034  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
1035  div (NTLf, NTLf, NTLg);
1036  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
1037 #endif
1038  }
1039 #ifdef HAVE_FLINT
1040  CanonicalForm Q;
1041  newtonDiv (F, G, Q);
1042  return Q;
1043 #else
1044  return div (F,G);
1045 #endif
1046  }
1047  }
1048 
1049  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
1050  ASSERT (F.level() == G.level(), "expected polys of same level");
1052  {
1054  zz_p::init (getCharacteristic());
1055  }
1056  Variable alpha;
1058  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
1059  {
1060 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1061  nmod_poly_t FLINTmipo;
1062  fq_nmod_ctx_t fq_con;
1063 
1064  nmod_poly_init (FLINTmipo, getCharacteristic());
1065  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
1066 
1067  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1068 
1069  fq_nmod_poly_t FLINTF, FLINTG;
1070  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
1071  convertFacCF2Fq_nmod_poly_t (FLINTG, G, fq_con);
1072 
1073  fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1074 
1075  result= convertFq_nmod_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
1076 
1077  fq_nmod_poly_clear (FLINTF, fq_con);
1078  fq_nmod_poly_clear (FLINTG, fq_con);
1079  nmod_poly_clear (FLINTmipo);
1080  fq_nmod_ctx_clear (fq_con);
1081 #else
1082  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
1083  zz_pE::init (NTLMipo);
1084  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
1085  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
1086  div (NTLF, NTLF, NTLG);
1087  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
1088 #endif
1089  }
1090  else
1091  {
1092 #ifdef HAVE_FLINT
1093  nmod_poly_t FLINTF, FLINTG;
1094  convertFacCF2nmod_poly_t (FLINTF, F);
1095  convertFacCF2nmod_poly_t (FLINTG, G);
1096  nmod_poly_div (FLINTF, FLINTF, FLINTG);
1097  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
1098  nmod_poly_clear (FLINTF);
1099  nmod_poly_clear (FLINTG);
1100 #else
1101  zz_pX NTLF= convertFacCF2NTLzzpX (F);
1102  zz_pX NTLG= convertFacCF2NTLzzpX (G);
1103  div (NTLF, NTLF, NTLG);
1104  result= convertNTLzzpX2CF(NTLF, F.mvar());
1105 #endif
1106  }
1107  return result;
1108 }
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...
nmod_poly_init(FLINTmipo, getCharacteristic())
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:664
void convertCF2Fmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t
Definition: FLINTconvert.cc:61
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
factory&#39;s class for variables
Definition: factory.h:117
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
Definition: NTLconvert.cc:243
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
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
Definition: NTLconvert.cc:1036
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
Variable alpha
Definition: facAbsBiFact.cc:52
#define Q
Definition: sirandom.c:25
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 getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
CanonicalForm b
Definition: cfModGcd.cc:4044
bool inBaseDomain() const
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1114
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
Definition: NTLconvert.cc:59
convertFacCF2nmod_poly_t(FLINTmipo, M)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
bool isUnivariate() const
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition: facMul.cc:376
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
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) ...
static int gettype()
Definition: cf_factory.h:28
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
CanonicalForm getpk() const
Definition: fac_util.h:38
CanonicalForm divFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:170
#define GaloisFieldDomain
Definition: cf_defs.h:22
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 ...
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
long fac_NTL_char
Definition: NTLconvert.cc:41
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 ...
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:278
return result
Definition: facAbsBiFact.cc:76
int getp() const
Definition: fac_util.h:35
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. variable alpha and polynomial variable x
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

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

3585 {
3586  CanonicalForm A= mod (F, MOD);
3587  CanonicalForm B= mod (G, MOD);
3588  Variable x= Variable (1);
3589  int degB= degree (B, x);
3590  if (degB > degree (A, x))
3591  {
3592  Q= 0;
3593  R= A;
3594  return;
3595  }
3596 
3597  if (degB <= 0)
3598  {
3599  divrem (A, B, Q, R);
3600  Q= mod (Q, MOD);
3601  R= mod (R, MOD);
3602  return;
3603  }
3604  CFList splitA= split (A, degB, x);
3605 
3606  CanonicalForm xToDegB= power (x, degB);
3607  CanonicalForm H, bufQ;
3608  Q= 0;
3609  CFListIterator i= splitA;
3610  H= i.getItem()*xToDegB;
3611  i++;
3612  H += i.getItem();
3613  while (i.hasItem())
3614  {
3615  divrem21 (H, B, bufQ, R, MOD);
3616  i++;
3617  if (i.hasItem())
3618  H= R*xToDegB + i.getItem();
3619  Q *= xToDegB;
3620  Q += bufQ;
3621  }
3622  return;
3623 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s class for variables
Definition: factory.h:117
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:3583
factory&#39;s main class
Definition: canonicalform.h:77
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:125
CanonicalForm H
Definition: facAbsFact.cc:64
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3336
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3376
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)

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

3518 {
3519  CanonicalForm A= mod (F, M);
3520  CanonicalForm B= mod (G, M);
3521 
3522  if (B.inCoeffDomain())
3523  {
3524  divrem (A, B, Q, R);
3525  return;
3526  }
3527  if (A.inCoeffDomain() && !B.inCoeffDomain())
3528  {
3529  Q= 0;
3530  R= A;
3531  return;
3532  }
3533 
3534  if (B.level() < A.level())
3535  {
3536  divrem (A, B, Q, R);
3537  return;
3538  }
3539  if (A.level() > B.level())
3540  {
3541  R= A;
3542  Q= 0;
3543  return;
3544  }
3545  if (B.level() == 1 && B.isUnivariate())
3546  {
3547  divrem (A, B, Q, R);
3548  return;
3549  }
3550 
3551  Variable x= Variable (1);
3552  int degB= degree (B, x);
3553  if (degB > degree (A, x))
3554  {
3555  Q= 0;
3556  R= A;
3557  return;
3558  }
3559 
3560  CFList splitA= split (A, degB, x);
3561 
3562  CanonicalForm xToDegB= power (x, degB);
3563  CanonicalForm H, bufQ;
3564  Q= 0;
3565  CFListIterator i= splitA;
3566  H= i.getItem()*xToDegB;
3567  i++;
3568  H += i.getItem();
3569  CFList buf;
3570  while (i.hasItem())
3571  {
3572  buf= CFList (M);
3573  divrem21 (H, B, bufQ, R, buf);
3574  i++;
3575  if (i.hasItem())
3576  H= R*xToDegB + i.getItem();
3577  Q *= xToDegB;
3578  Q += bufQ;
3579  }
3580  return;
3581 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
factory&#39;s class for variables
Definition: factory.h:117
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:3583
factory&#39;s main class
Definition: canonicalform.h:77
int status int void * buf
Definition: si_signals.h:59
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:125
CanonicalForm H
Definition: facAbsFact.cc:64
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3336
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3376
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
bool inCoeffDomain() const

◆ divrem21()

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

Definition at line 3376 of file facMul.cc.

3378 {
3379  CanonicalForm A= mod (F, M);
3380  CanonicalForm B= mod (G, M);
3381  Variable x= Variable (1);
3382  int degB= degree (B, x);
3383  int degA= degree (A, x);
3384  if (degA < degB)
3385  {
3386  Q= 0;
3387  R= A;
3388  return;
3389  }
3390  if (degB < 1)
3391  {
3392  divrem (A, B, Q, R);
3393  Q= mod (Q, M);
3394  R= mod (R, M);
3395  return;
3396  }
3397  int m= (int) ceil ((double) (degB + 1)/2.0) + 1;
3398  ASSERT (4*m >= degA, "expected degree (F, 1) < 2*degree (G, 1)");
3399  CFList splitA= split (A, m, x);
3400  if (splitA.length() == 3)
3401  splitA.insert (0);
3402  if (splitA.length() == 2)
3403  {
3404  splitA.insert (0);
3405  splitA.insert (0);
3406  }
3407  if (splitA.length() == 1)
3408  {
3409  splitA.insert (0);
3410  splitA.insert (0);
3411  splitA.insert (0);
3412  }
3413 
3414  CanonicalForm xToM= power (x, m);
3415 
3416  CFListIterator i= splitA;
3417  CanonicalForm H= i.getItem();
3418  i++;
3419  H *= xToM;
3420  H += i.getItem();
3421  i++;
3422  H *= xToM;
3423  H += i.getItem();
3424  i++;
3425 
3426  divrem32 (H, B, Q, R, M);
3427 
3428  CFList splitR= split (R, m, x);
3429  if (splitR.length() == 1)
3430  splitR.insert (0);
3431 
3432  H= splitR.getFirst();
3433  H *= xToM;
3434  H += splitR.getLast();
3435  H *= xToM;
3436  H += i.getItem();
3437 
3438  CanonicalForm bufQ;
3439  divrem32 (H, B, bufQ, R, M);
3440 
3441  Q *= xToM;
3442  Q += bufQ;
3443  return;
3444 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s class for variables
Definition: factory.h:117
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:3583
factory&#39;s main class
Definition: canonicalform.h:77
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:3447
T getFirst() const
Definition: ftmpl_list.cc:279
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:789
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm H
Definition: facAbsFact.cc:64
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3336
int length() const
Definition: ftmpl_list.cc:273
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)

◆ divrem32()

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

Definition at line 3447 of file facMul.cc.

3449 {
3450  CanonicalForm A= mod (F, M);
3451  CanonicalForm B= mod (G, M);
3452  Variable x= Variable (1);
3453  int degB= degree (B, x);
3454  int degA= degree (A, x);
3455  if (degA < degB)
3456  {
3457  Q= 0;
3458  R= A;
3459  return;
3460  }
3461  if (degB < 1)
3462  {
3463  divrem (A, B, Q, R);
3464  Q= mod (Q, M);
3465  R= mod (R, M);
3466  return;
3467  }
3468  int m= (int) ceil ((double) (degB + 1)/ 2.0);
3469  ASSERT (3*m > degA, "expected degree (F, 1) < 3*degree (G, 1)");
3470  CFList splitA= split (A, m, x);
3471  CFList splitB= split (B, m, x);
3472 
3473  if (splitA.length() == 2)
3474  {
3475  splitA.insert (0);
3476  }
3477  if (splitA.length() == 1)
3478  {
3479  splitA.insert (0);
3480  splitA.insert (0);
3481  }
3482  CanonicalForm xToM= power (x, m);
3483 
3484  CanonicalForm H;
3485  CFListIterator i= splitA;
3486  i++;
3487 
3488  if (degree (splitA.getFirst(), x) < degree (splitB.getFirst(), x))
3489  {
3490  H= splitA.getFirst()*xToM + i.getItem();
3491  divrem21 (H, splitB.getFirst(), Q, R, M);
3492  }
3493  else
3494  {
3495  R= splitA.getFirst()*xToM + i.getItem() + splitB.getFirst() -
3496  splitB.getFirst()*xToM;
3497  Q= xToM - 1;
3498  }
3499 
3500  H= mulMod (Q, splitB.getLast(), M);
3501 
3502  R= R*xToM + splitA.getLast() - H;
3503 
3504  while (degree (R, x) >= degB)
3505  {
3506  xToM= power (x, degree (R, x) - degB);
3507  Q += LC (R, x)*xToM;
3508  R -= mulMod (LC (R, x), B, M)*xToM;
3509  Q= mod (Q, M);
3510  R= mod (R, M);
3511  }
3512 
3513  return;
3514 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s class for variables
Definition: factory.h:117
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:3583
factory&#39;s main class
Definition: canonicalform.h:77
#define Q
Definition: sirandom.c:25
void insert(const T &)
Definition: ftmpl_list.cc:193
T getFirst() const
Definition: ftmpl_list.cc:279
#define M
Definition: sirandom.c:24
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:789
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm H
Definition: facAbsFact.cc:64
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3336
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
int length() const
Definition: ftmpl_list.cc:273
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3376
b *CanonicalForm B
Definition: facBivar.cc:52
#define R
Definition: sirandom.c:26
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

◆ kronSubFp()

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

Definition at line 1115 of file facMul.cc.

1116 {
1117  int degAy= degree (A);
1118  nmod_poly_init2 (result, getCharacteristic(), d*(degAy + 1));
1119  result->length= d*(degAy + 1);
1120  flint_mpn_zero (result->coeffs, d*(degAy+1));
1121 
1122  nmod_poly_t buf;
1123 
1124  int k;
1125  for (CFIterator i= A; i.hasTerms(); i++)
1126  {
1127  convertFacCF2nmod_poly_t (buf, i.coeff());
1128  k= i.exp()*d;
1129  flint_mpn_copyi (result->coeffs+k, buf->coeffs, nmod_poly_length(buf));
1130 
1131  nmod_poly_clear (buf);
1132  }
1133  _nmod_poly_normalise (result);
1134 }
nmod_poly_clear(FLINTmipo)
int k
Definition: cfEzgcd.cc:92
int getCharacteristic()
Definition: cf_char.cc:51
convertFacCF2nmod_poly_t(FLINTmipo, M)
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

◆ kronSubFq()

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

Definition at line 1138 of file facMul.cc.

1140 {
1141  int degAy= degree (A);
1142  fq_nmod_poly_init2 (result, d*(degAy + 1), fq_con);
1143  _fq_nmod_poly_set_length (result, d*(degAy + 1), fq_con);
1144  _fq_nmod_vec_zero (result->coeffs, d*(degAy + 1), fq_con);
1145 
1146  fq_nmod_poly_t buf1;
1147 
1148  nmod_poly_t buf2;
1149 
1150  int k;
1151 
1152  for (CFIterator i= A; i.hasTerms(); i++)
1153  {
1154  if (i.coeff().inCoeffDomain())
1155  {
1156  convertFacCF2nmod_poly_t (buf2, i.coeff());
1157  fq_nmod_poly_init2 (buf1, 1, fq_con);
1158  fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1159  nmod_poly_clear (buf2);
1160  }
1161  else
1162  convertFacCF2Fq_nmod_poly_t (buf1, i.coeff(), fq_con);
1163 
1164  k= i.exp()*d;
1165  _fq_nmod_vec_set (result->coeffs+k, buf1->coeffs,
1166  fq_nmod_poly_length (buf1, fq_con), fq_con);
1167 
1168  fq_nmod_poly_clear (buf1, fq_con);
1169  }
1170 
1171  _fq_nmod_poly_normalise (result, fq_con);
1172 }
CanonicalForm buf1
Definition: facFqBivar.cc:71
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
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
int k
Definition: cfEzgcd.cc:92
convertFacCF2nmod_poly_t(FLINTmipo, M)
int i
Definition: cfEzgcd.cc:125
fq_nmod_poly_clear(prod, fq_con)
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm buf2
Definition: facFqBivar.cc:71
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

◆ kronSubQa() [1/2]

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

Definition at line 42 of file facMul.cc.

43 {
44  int degAy= degree (A);
45  fmpz_poly_init2 (result, d*(degAy + 1));
46  _fmpz_poly_set_length (result, d*(degAy + 1));
47  CFIterator j;
48  for (CFIterator i= A; i.hasTerms(); i++)
49  {
50  if (i.coeff().inBaseDomain())
51  convertCF2Fmpz (fmpz_poly_get_coeff_ptr (result, i.exp()*d), i.coeff());
52  else
53  for (j= i.coeff(); j.hasTerms(); j++)
54  convertCF2Fmpz (fmpz_poly_get_coeff_ptr (result, i.exp()*d+j.exp()),
55  j.coeff());
56  }
57  _fmpz_poly_normalise(result);
58 }
int j
Definition: facHensel.cc:105
void convertCF2Fmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t
Definition: FLINTconvert.cc:61
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
int degree(const CanonicalForm &f)
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

◆ kronSubQa() [2/2]

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

Definition at line 1220 of file facMul.cc.

1221 {
1222  int degAy= degree (A);
1223  fmpz_poly_init2 (result, d1*(degAy + 1));
1224  _fmpz_poly_set_length (result, d1*(degAy + 1));
1225 
1226  fmpz_poly_t buf;
1227 
1228  int k;
1229  CFIterator j;
1230  for (CFIterator i= A; i.hasTerms(); i++)
1231  {
1232  if (i.coeff().inCoeffDomain())
1233  {
1234  k= d1*i.exp();
1235  convertFacCF2Fmpz_poly_t (buf, i.coeff());
1236  _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1237  fmpz_poly_clear (buf);
1238  }
1239  else
1240  {
1241  for (j= i.coeff(); j.hasTerms(); j++)
1242  {
1243  k= d1*i.exp();
1244  k += d2*j.exp();
1245  convertFacCF2Fmpz_poly_t (buf, j.coeff());
1246  _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1247  fmpz_poly_clear (buf);
1248  }
1249  }
1250  }
1251  _fmpz_poly_normalise (result);
1252 }
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
int j
Definition: facHensel.cc:105
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int k
Definition: cfEzgcd.cc:92
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
int degree(const CanonicalForm &f)
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

◆ kronSubReciproFp()

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

Definition at line 1255 of file facMul.cc.

1257 {
1258  int degAy= degree (A);
1259  mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1260  nmod_poly_init2_preinv (subA1, getCharacteristic(), ninv, d*(degAy + 2));
1261  nmod_poly_init2_preinv (subA2, getCharacteristic(), ninv, d*(degAy + 2));
1262 
1263  nmod_poly_t buf;
1264 
1265  int k, kk, j, bufRepLength;
1266  for (CFIterator i= A; i.hasTerms(); i++)
1267  {
1268  convertFacCF2nmod_poly_t (buf, i.coeff());
1269 
1270  k= i.exp()*d;
1271  kk= (degAy - i.exp())*d;
1272  bufRepLength= (int) nmod_poly_length (buf);
1273  for (j= 0; j < bufRepLength; j++)
1274  {
1275  nmod_poly_set_coeff_ui (subA1, j + k,
1276  n_addmod (nmod_poly_get_coeff_ui (subA1, j+k),
1277  nmod_poly_get_coeff_ui (buf, j),
1279  )
1280  );
1281  nmod_poly_set_coeff_ui (subA2, j + kk,
1282  n_addmod (nmod_poly_get_coeff_ui (subA2, j + kk),
1283  nmod_poly_get_coeff_ui (buf, j),
1285  )
1286  );
1287  }
1288  nmod_poly_clear (buf);
1289  }
1290  _nmod_poly_normalise (subA1);
1291  _nmod_poly_normalise (subA2);
1292 }
int j
Definition: facHensel.cc:105
nmod_poly_clear(FLINTmipo)
int k
Definition: cfEzgcd.cc:92
int getCharacteristic()
Definition: cf_char.cc:51
convertFacCF2nmod_poly_t(FLINTmipo, M)
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int degree(const CanonicalForm &f)

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

1298 {
1299  int degAy= degree (A);
1300  fq_nmod_poly_init2 (subA1, d*(degAy + 2), fq_con);
1301  fq_nmod_poly_init2 (subA2, d*(degAy + 2), fq_con);
1302 
1303  _fq_nmod_poly_set_length (subA1, d*(degAy + 2), fq_con);
1304  _fq_nmod_vec_zero (subA1->coeffs, d*(degAy + 2), fq_con);
1305 
1306  _fq_nmod_poly_set_length (subA2, d*(degAy + 2), fq_con);
1307  _fq_nmod_vec_zero (subA2->coeffs, d*(degAy + 2), fq_con);
1308 
1309  fq_nmod_poly_t buf1;
1310 
1311  nmod_poly_t buf2;
1312 
1313  int k, kk;
1314  for (CFIterator i= A; i.hasTerms(); i++)
1315  {
1316  if (i.coeff().inCoeffDomain())
1317  {
1318  convertFacCF2nmod_poly_t (buf2, i.coeff());
1319  fq_nmod_poly_init2 (buf1, 1, fq_con);
1320  fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1321  nmod_poly_clear (buf2);
1322  }
1323  else
1324  convertFacCF2Fq_nmod_poly_t (buf1, i.coeff(), fq_con);
1325 
1326  k= i.exp()*d;
1327  kk= (degAy - i.exp())*d;
1328  _fq_nmod_vec_add (subA1->coeffs+k, subA1->coeffs+k, buf1->coeffs,
1329  fq_nmod_poly_length(buf1, fq_con), fq_con);
1330  _fq_nmod_vec_add (subA2->coeffs+kk, subA2->coeffs+kk, buf1->coeffs,
1331  fq_nmod_poly_length(buf1, fq_con), fq_con);
1332 
1333  fq_nmod_poly_clear (buf1, fq_con);
1334  }
1335  _fq_nmod_poly_normalise (subA1, fq_con);
1336  _fq_nmod_poly_normalise (subA2, fq_con);
1337 }
CanonicalForm buf1
Definition: facFqBivar.cc:71
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
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
int k
Definition: cfEzgcd.cc:92
convertFacCF2nmod_poly_t(FLINTmipo, M)
int i
Definition: cfEzgcd.cc:125
fq_nmod_poly_clear(prod, fq_con)
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm buf2
Definition: facFqBivar.cc:71
int degree(const CanonicalForm &f)

◆ kronSubReciproQ()

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

Definition at line 1341 of file facMul.cc.

1343 {
1344  int degAy= degree (A);
1345  fmpz_poly_init2 (subA1, d*(degAy + 2));
1346  fmpz_poly_init2 (subA2, d*(degAy + 2));
1347 
1348  fmpz_poly_t buf;
1349 
1350  int k, kk;
1351  for (CFIterator i= A; i.hasTerms(); i++)
1352  {
1353  convertFacCF2Fmpz_poly_t (buf, i.coeff());
1354 
1355  k= i.exp()*d;
1356  kk= (degAy - i.exp())*d;
1357  _fmpz_vec_add (subA1->coeffs+k, subA1->coeffs + k, buf->coeffs, buf->length);
1358  _fmpz_vec_add (subA2->coeffs+kk, subA2->coeffs + kk, buf->coeffs, buf->length);
1359  fmpz_poly_clear (buf);
1360  }
1361 
1362  _fmpz_poly_normalise (subA1);
1363  _fmpz_poly_normalise (subA2);
1364 }
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
int k
Definition: cfEzgcd.cc:92
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int degree(const CanonicalForm &f)

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

2940 {
2941  CanonicalForm A= F;
2942  for (CFListIterator i= M; i.hasItem(); i++)
2943  A= mod (A, i.getItem());
2944  return A;
2945 }
factory&#39;s main class
Definition: canonicalform.h:77
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:125
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939

◆ modFLINTQ()

CanonicalForm modFLINTQ ( const CanonicalForm F,
const CanonicalForm G 
)

Definition at line 188 of file facMul.cc.

189 {
190  CanonicalForm A= F;
191  CanonicalForm B= G;
192 
193  fmpq_poly_t FLINTA,FLINTB;
194  convertFacCF2Fmpq_poly_t (FLINTA, A);
195  convertFacCF2Fmpq_poly_t (FLINTB, B);
196 
197  fmpq_poly_rem (FLINTA, FLINTA, FLINTB);
198  A= convertFmpq_poly_t2FacCF (FLINTA, F.mvar());
199 
200  fmpq_poly_clear (FLINTA);
201  fmpq_poly_clear (FLINTB);
202  return A;
203 }
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:32
#define A
Definition: sirandom.c:23
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm

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

677 {
679  return mod (F, G);
680  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
681  {
682  if (b.getp() != 0)
683  return b(F);
684  return F;
685  }
686  else if (F.inCoeffDomain() && G.inCoeffDomain())
687  {
688  if (b.getp() != 0)
689  return b(F%G);
690  return mod (F, G);
691  }
692  else if (F.isUnivariate() && G.inCoeffDomain())
693  {
694  if (b.getp() != 0)
695  return b(F%G);
696  return mod (F,G);
697  }
698 
699  if (getCharacteristic() == 0)
700  {
701  Variable alpha;
702  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
703  {
704 #ifdef HAVE_FLINT
705  if (b.getp() != 0)
706  {
707  fmpz_t FLINTpk;
708  fmpz_init (FLINTpk);
709  convertCF2Fmpz (FLINTpk, b.getpk());
710  fmpz_mod_poly_t FLINTF, FLINTG;
711  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
712  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
713  fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
715  fmpz_mod_poly_clear (FLINTG);
716  fmpz_mod_poly_clear (FLINTF);
717  fmpz_clear (FLINTpk);
718  return result;
719  }
720  return modFLINTQ (F, G);
721 #else
722  if (b.getp() != 0)
723  {
724  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
725  ZZX ZZf= convertFacCF2NTLZZX (F);
726  ZZX ZZg= convertFacCF2NTLZZX (G);
727  ZZ_pX NTLf= to_ZZ_pX (ZZf);
728  ZZ_pX NTLg= to_ZZ_pX (ZZg);
729  rem (NTLf, NTLf, NTLg);
730  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
731  }
732  return mod (F, G);
733 #endif
734  }
735  else
736  {
737  if (b.getp() != 0)
738  {
739 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
740  fmpz_t FLINTp;
741  fmpz_mod_poly_t FLINTmipo;
742  fq_ctx_t fq_con;
743  fq_poly_t FLINTF, FLINTG;
744 
745  fmpz_init (FLINTp);
746 
747  convertCF2Fmpz (FLINTp, b.getpk());
748 
749  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
750 
751  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
752 
753  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
754  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
755 
756  fq_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
757 
758  CanonicalForm result= convertFq_poly_t2FacCF (FLINTF, F.mvar(),
759  alpha, fq_con);
760 
761  fmpz_clear (FLINTp);
762  fmpz_mod_poly_clear (FLINTmipo);
763  fq_poly_clear (FLINTF, fq_con);
764  fq_poly_clear (FLINTG, fq_con);
765  fq_ctx_clear (fq_con);
766 
767  return b(result);
768 #else
769  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
770  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
771  ZZ_pE::init (NTLmipo);
772  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
773  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
774  rem (NTLf, NTLf, NTLg);
775  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
776 #endif
777  }
778 #ifdef HAVE_FLINT
779  CanonicalForm Q, R;
780  newtonDivrem (F, G, Q, R);
781  return R;
782 #else
783  return mod (F,G);
784 #endif
785  }
786  }
787 
788  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
789  ASSERT (F.level() == G.level(), "expected polys of same level");
791  {
793  zz_p::init (getCharacteristic());
794  }
795  Variable alpha;
797  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
798  {
799 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
800  nmod_poly_t FLINTmipo;
801  fq_nmod_ctx_t fq_con;
802 
803  nmod_poly_init (FLINTmipo, getCharacteristic());
804  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
805 
806  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
807 
808  fq_nmod_poly_t FLINTF, FLINTG;
809  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
810  convertFacCF2Fq_nmod_poly_t (FLINTG, G, fq_con);
811 
812  fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
813 
814  result= convertFq_nmod_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
815 
816  fq_nmod_poly_clear (FLINTF, fq_con);
817  fq_nmod_poly_clear (FLINTG, fq_con);
818  nmod_poly_clear (FLINTmipo);
819  fq_nmod_ctx_clear (fq_con);
820 #else
821  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
822  zz_pE::init (NTLMipo);
823  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
824  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
825  rem (NTLF, NTLF, NTLG);
826  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
827 #endif
828  }
829  else
830  {
831 #ifdef HAVE_FLINT
832  nmod_poly_t FLINTF, FLINTG;
833  convertFacCF2nmod_poly_t (FLINTF, F);
834  convertFacCF2nmod_poly_t (FLINTG, G);
835  nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
836  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
837  nmod_poly_clear (FLINTF);
838  nmod_poly_clear (FLINTG);
839 #else
840  zz_pX NTLF= convertFacCF2NTLzzpX (F);
841  zz_pX NTLG= convertFacCF2NTLzzpX (G);
842  rem (NTLF, NTLF, NTLG);
843  result= convertNTLzzpX2CF(NTLF, F.mvar());
844 #endif
845  }
846  return result;
847 }
nmod_poly_init(FLINTmipo, getCharacteristic())
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:664
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
void convertCF2Fmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t
Definition: FLINTconvert.cc:61
factory&#39;s class for variables
Definition: factory.h:117
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
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
Definition: NTLconvert.cc:1036
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
Variable alpha
Definition: facAbsBiFact.cc:52
#define Q
Definition: sirandom.c:25
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 getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
CanonicalForm modFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:188
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1114
convertFacCF2nmod_poly_t(FLINTmipo, M)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
bool isUnivariate() const
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
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)
Definition: facMul.cc:342
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
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) ...
static int gettype()
Definition: cf_factory.h:28
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
CanonicalForm getpk() const
Definition: fac_util.h:38
#define R
Definition: sirandom.c:26
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
#define GaloisFieldDomain
Definition: cf_defs.h:22
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 ...
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
long fac_NTL_char
Definition: NTLconvert.cc:41
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 ...
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:278
return result
Definition: facAbsBiFact.cc:76
int getp() const
Definition: fac_util.h:35
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. variable alpha and polynomial variable x
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

◆ mulFLINTQ()

CanonicalForm mulFLINTQ ( const CanonicalForm F,
const CanonicalForm G 
)

Definition at line 129 of file facMul.cc.

130 {
131  CanonicalForm A= F;
132  CanonicalForm B= G;
133 
134  CanonicalForm denA= bCommonDen (A);
135  CanonicalForm denB= bCommonDen (B);
136 
137  A *= denA;
138  B *= denB;
139  fmpz_poly_t FLINTA,FLINTB;
140  convertFacCF2Fmpz_poly_t (FLINTA, A);
141  convertFacCF2Fmpz_poly_t (FLINTB, B);
142  fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
143  denA *= denB;
144  A= convertFmpz_poly_t2FacCF (FLINTA, F.mvar());
145  A /= denA;
146  fmpz_poly_clear (FLINTA);
147  fmpz_poly_clear (FLINTB);
148 
149  return A;
150 }
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:32
#define A
Definition: sirandom.c:23
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
b *CanonicalForm B
Definition: facBivar.cc:52

◆ mulFLINTQa()

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

Definition at line 99 of file facMul.cc.

101 {
102  CanonicalForm A= F;
103  CanonicalForm B= G;
104 
105  CanonicalForm denA= bCommonDen (A);
106  CanonicalForm denB= bCommonDen (B);
107 
108  A *= denA;
109  B *= denB;
110  int degAa= degree (A, alpha);
111  int degBa= degree (B, alpha);
112  int d= degAa + 1 + degBa;
113 
114  fmpz_poly_t FLINTA,FLINTB;
115  kronSubQa (FLINTA, A, d);
116  kronSubQa (FLINTB, B, d);
117 
118  fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
119 
120  denA *= denB;
121  A= reverseSubstQa (FLINTA, d, F.mvar(), alpha, denA);
122 
123  fmpz_poly_clear (FLINTA);
124  fmpz_poly_clear (FLINTB);
125  return A;
126 }
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
Definition: facMul.cc:62
factory&#39;s main class
Definition: canonicalform.h:77
Variable alpha
Definition: facAbsBiFact.cc:52
static TreeM * G
Definition: janet.cc:32
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:42
#define A
Definition: sirandom.c:23
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
b *CanonicalForm B
Definition: facBivar.cc:52
int degree(const CanonicalForm &f)

◆ mulFLINTQaTrunc()

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

Definition at line 206 of file facMul.cc.

208 {
209  CanonicalForm A= F;
210  CanonicalForm B= G;
211 
212  CanonicalForm denA= bCommonDen (A);
213  CanonicalForm denB= bCommonDen (B);
214 
215  A *= denA;
216  B *= denB;
217 
218  int degAa= degree (A, alpha);
219  int degBa= degree (B, alpha);
220  int d= degAa + 1 + degBa;
221 
222  fmpz_poly_t FLINTA,FLINTB;
223  kronSubQa (FLINTA, A, d);
224  kronSubQa (FLINTB, B, d);
225 
226  int k= d*m;
227  fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, k);
228 
229  denA *= denB;
230  A= reverseSubstQa (FLINTA, d, F.mvar(), alpha, denA);
231  fmpz_poly_clear (FLINTA);
232  fmpz_poly_clear (FLINTB);
233  return A;
234 }
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
Definition: facMul.cc:62
factory&#39;s main class
Definition: canonicalform.h:77
int k
Definition: cfEzgcd.cc:92
Variable alpha
Definition: facAbsBiFact.cc:52
static TreeM * G
Definition: janet.cc:32
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:42
#define A
Definition: sirandom.c:23
int m
Definition: cfEzgcd.cc:121
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
b *CanonicalForm B
Definition: facBivar.cc:52
int degree(const CanonicalForm &f)

◆ mulFLINTQTrunc()

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

Definition at line 237 of file facMul.cc.

238 {
239  if (F.inCoeffDomain() && G.inCoeffDomain())
240  return F*G;
241  if (F.inCoeffDomain())
242  return mod (F*G, power (G.mvar(), m));
243  if (G.inCoeffDomain())
244  return mod (F*G, power (F.mvar(), m));
245  Variable alpha;
246  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
247  return mulFLINTQaTrunc (F, G, alpha, m);
248 
249  CanonicalForm A= F;
250  CanonicalForm B= G;
251 
252  CanonicalForm denA= bCommonDen (A);
253  CanonicalForm denB= bCommonDen (B);
254 
255  A *= denA;
256  B *= denB;
257  fmpz_poly_t FLINTA,FLINTB;
258  convertFacCF2Fmpz_poly_t (FLINTA, A);
259  convertFacCF2Fmpz_poly_t (FLINTB, B);
260  fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, m);
261  denA *= denB;
262  A= convertFmpz_poly_t2FacCF (FLINTA, F.mvar());
263  A /= denA;
264  fmpz_poly_clear (FLINTA);
265  fmpz_poly_clear (FLINTB);
266 
267  return A;
268 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
Variable alpha
Definition: facAbsBiFact.cc:52
static TreeM * G
Definition: janet.cc:32
#define A
Definition: sirandom.c:23
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm mulFLINTQaTrunc(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, int m)
Definition: facMul.cc:206
int m
Definition: cfEzgcd.cc:121
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
bool inCoeffDomain() const

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

2949 {
2950  if (A.isZero() || B.isZero())
2951  return 0;
2952 
2953  if (MOD.length() == 1)
2954  return mulMod2 (A, B, MOD.getLast());
2955 
2956  CanonicalForm M= MOD.getLast();
2957  CanonicalForm F= mod (A, M);
2958  CanonicalForm G= mod (B, M);
2959  if (F.inCoeffDomain())
2960  return G*F;
2961  if (G.inCoeffDomain())
2962  return F*G;
2963 
2964  int sizeF= size (F);
2965  int sizeG= size (G);
2966 
2967  if (sizeF / MOD.length() < 100 || sizeG / MOD.length() < 100)
2968  {
2969  if (sizeF < sizeG)
2970  return mod (G*F, MOD);
2971  else
2972  return mod (F*G, MOD);
2973  }
2974 
2975  Variable y= M.mvar();
2976  int degF= degree (F, y);
2977  int degG= degree (G, y);
2978 
2979  if ((degF <= 1 && F.level() <= M.level()) &&
2980  (degG <= 1 && G.level() <= M.level()))
2981  {
2982  CFList buf= MOD;
2983  buf.removeLast();
2984  if (degF == 1 && degG == 1)
2985  {
2986  CanonicalForm F0= mod (F, y);
2987  CanonicalForm F1= div (F, y);
2988  CanonicalForm G0= mod (G, y);
2989  CanonicalForm G1= div (G, y);
2990  if (degree (M) > 2)
2991  {
2992  CanonicalForm H00= mulMod (F0, G0, buf);
2993  CanonicalForm H11= mulMod (F1, G1, buf);
2994  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, buf);
2995  return H11*y*y + (H01 - H00 - H11)*y + H00;
2996  }
2997  else //here degree (M) == 2
2998  {
2999  buf.append (y);
3000  CanonicalForm F0G1= mulMod (F0, G1, buf);
3001  CanonicalForm F1G0= mulMod (F1, G0, buf);
3002  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3003  CanonicalForm result= F0G0 + y*(F0G1 + F1G0);
3004  return result;
3005  }
3006  }
3007  else if (degF == 1 && degG == 0)
3008  return mulMod (div (F, y), G, buf)*y + mulMod (mod (F, y), G, buf);
3009  else if (degF == 0 && degG == 1)
3010  return mulMod (div (G, y), F, buf)*y + mulMod (mod (G, y), F, buf);
3011  else
3012  return mulMod (F, G, buf);
3013  }
3014  int m= (int) ceil (degree (M)/2.0);
3015  if (degF >= m || degG >= m)
3016  {
3017  CanonicalForm MLo= power (y, m);
3018  CanonicalForm MHi= power (y, degree (M) - m);
3019  CanonicalForm F0= mod (F, MLo);
3020  CanonicalForm F1= div (F, MLo);
3021  CanonicalForm G0= mod (G, MLo);
3022  CanonicalForm G1= div (G, MLo);
3023  CFList buf= MOD;
3024  buf.removeLast();
3025  buf.append (MHi);
3026  CanonicalForm F0G1= mulMod (F0, G1, buf);
3027  CanonicalForm F1G0= mulMod (F1, G0, buf);
3028  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3029  return F0G0 + MLo*(F0G1 + F1G0);
3030  }
3031  else
3032  {
3033  m= (tmax(degF, degG)+1)/2;
3034  CanonicalForm yToM= power (y, m);
3035  CanonicalForm F0= mod (F, yToM);
3036  CanonicalForm F1= div (F, yToM);
3037  CanonicalForm G0= mod (G, yToM);
3038  CanonicalForm G1= div (G, yToM);
3039  CanonicalForm H00= mulMod (F0, G0, MOD);
3040  CanonicalForm H11= mulMod (F1, G1, MOD);
3041  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, MOD);
3042  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3043  }
3044  DEBOUTLN (cerr, "fatal end in mulMod");
3045 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:32
#define M
Definition: sirandom.c:24
void removeLast()
Definition: ftmpl_list.cc:317
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:789
int status int void * buf
Definition: si_signals.h:59
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
int m
Definition: cfEzgcd.cc:121
T getLast() const
Definition: ftmpl_list.cc:309
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
int length() const
Definition: ftmpl_list.cc:273
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
int level() const
level() returns the level of CO.
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

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

2855 {
2856  if (A.isZero() || B.isZero())
2857  return 0;
2858 
2859  ASSERT (M.isUnivariate(), "M must be univariate");
2860 
2861  CanonicalForm F= mod (A, M);
2862  CanonicalForm G= mod (B, M);
2863  if (F.inCoeffDomain())
2864  return G*F;
2865  if (G.inCoeffDomain())
2866  return F*G;
2867 
2868  Variable y= M.mvar();
2869  int degF= degree (F, y);
2870  int degG= degree (G, y);
2871 
2872  if ((degF < 1 && degG < 1) && (F.isUnivariate() && G.isUnivariate()) &&
2873  (F.level() == G.level()))
2874  {
2875  CanonicalForm result= mulNTL (F, G);
2876  return mod (result, M);
2877  }
2878  else if (degF <= 1 && degG <= 1)
2879  {
2880  CanonicalForm result= F*G;
2881  return mod (result, M);
2882  }
2883 
2884  int sizeF= size (F);
2885  int sizeG= size (G);
2886 
2887  int fallBackToNaive= 50;
2888  if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
2889  {
2890  if (sizeF < sizeG)
2891  return mod (G*F, M);
2892  else
2893  return mod (F*G, M);
2894  }
2895 
2896 #ifdef HAVE_FLINT
2897  if (getCharacteristic() == 0)
2898  return mulMod2FLINTQa (F, G, M);
2899 #endif
2900 
2902  (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
2903  return mulMod2NTLFq (F, G, M);
2904 
2905  int m= (int) ceil (degree (M)/2.0);
2906  if (degF >= m || degG >= m)
2907  {
2908  CanonicalForm MLo= power (y, m);
2909  CanonicalForm MHi= power (y, degree (M) - m);
2910  CanonicalForm F0= mod (F, MLo);
2911  CanonicalForm F1= div (F, MLo);
2912  CanonicalForm G0= mod (G, MLo);
2913  CanonicalForm G1= div (G, MLo);
2914  CanonicalForm F0G1= mulMod2 (F0, G1, MHi);
2915  CanonicalForm F1G0= mulMod2 (F1, G0, MHi);
2916  CanonicalForm F0G0= mulMod2 (F0, G0, M);
2917  return F0G0 + MLo*(F0G1 + F1G0);
2918  }
2919  else
2920  {
2921  m= (int) ceil (tmax (degF, degG)/2.0);
2922  CanonicalForm yToM= power (y, m);
2923  CanonicalForm F0= mod (F, yToM);
2924  CanonicalForm F1= div (F, yToM);
2925  CanonicalForm G0= mod (G, yToM);
2926  CanonicalForm G1= div (G, yToM);
2927  CanonicalForm H00= mulMod2 (F0, G0, M);
2928  CanonicalForm H11= mulMod2 (F1, G1, M);
2929  CanonicalForm H01= mulMod2 (F0 + F1, G0 + G1, M);
2930  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
2931  }
2932  DEBOUTLN (cerr, "fatal end in mulMod2");
2933 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:32
int getCharacteristic()
Definition: cf_char.cc:51
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&#39;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).
Definition: facMul.cc:407
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:789
bool isUnivariate() const
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
int m
Definition: cfEzgcd.cc:121
CanonicalForm mulMod2FLINTQa(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2199
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
static int gettype()
Definition: cf_factory.h:28
CanonicalForm mulMod2NTLFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2793
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
#define GaloisFieldDomain
Definition: cf_defs.h:22
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

◆ mulMod2FLINTFp()

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

Definition at line 1995 of file facMul.cc.

1997 {
1998  CanonicalForm A= F;
1999  CanonicalForm B= G;
2000 
2001  int degAx= degree (A, 1);
2002  int degAy= degree (A, 2);
2003  int degBx= degree (B, 1);
2004  int degBy= degree (B, 2);
2005  int d1= degAx + 1 + degBx;
2006  int d2= tmax (degAy, degBy);
2007 
2008  if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy > degree (M)))
2009  return mulMod2FLINTFpReci (A, B, M);
2010 
2011  nmod_poly_t FLINTA, FLINTB;
2012  kronSubFp (FLINTA, A, d1);
2013  kronSubFp (FLINTB, B, d1);
2014 
2015  int k= d1*degree (M);
2016  nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k);
2017 
2018  A= reverseSubstFp (FLINTA, d1);
2019 
2020  nmod_poly_clear (FLINTA);
2021  nmod_poly_clear (FLINTB);
2022  return A;
2023 }
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
void kronSubFp(nmod_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:1115
CanonicalForm mulMod2FLINTFpReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:1957
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
CanonicalForm reverseSubstFp(const nmod_poly_t F, int d)
Definition: facMul.cc:1921
int k
Definition: cfEzgcd.cc:92
static TreeM * G
Definition: janet.cc:32
#define A
Definition: sirandom.c:23
b *CanonicalForm B
Definition: facBivar.cc:52
int degree(const CanonicalForm &f)

◆ mulMod2FLINTFpReci()

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

Definition at line 1957 of file facMul.cc.

1959 {
1960  int d1= degree (F, 1) + degree (G, 1) + 1;
1961  d1 /= 2;
1962  d1 += 1;
1963 
1964  nmod_poly_t F1, F2;
1965  kronSubReciproFp (F1, F2, F, d1);
1966 
1967  nmod_poly_t G1, G2;
1968  kronSubReciproFp (G1, G2, G, d1);
1969 
1970  int k= d1*degree (M);
1971  nmod_poly_mullow (F1, F1, G1, (long) k);
1972 
1973  int degtailF= degree (tailcoeff (F), 1);;
1974  int degtailG= degree (tailcoeff (G), 1);
1975  int taildegF= taildegree (F);
1976  int taildegG= taildegree (G);
1977 
1978  int b= nmod_poly_degree (F2) + nmod_poly_degree (G2) - k - degtailF - degtailG
1979  + d1*(2+taildegF + taildegG);
1980  nmod_poly_mulhigh (F2, F2, G2, b);
1981  nmod_poly_shift_right (F2, F2, b);
1982  int d2= tmax (nmod_poly_degree (F2)/d1, nmod_poly_degree (F1)/d1);
1983 
1984 
1985  CanonicalForm result= reverseSubstReciproFp (F1, F2, d1, d2);
1986 
1987  nmod_poly_clear (F1);
1988  nmod_poly_clear (F2);
1989  nmod_poly_clear (G1);
1990  nmod_poly_clear (G2);
1991  return result;
1992 }
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
int k
Definition: cfEzgcd.cc:92
void kronSubReciproFp(nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm &A, int d)
Definition: facMul.cc:1255
int taildegree(const CanonicalForm &f)
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm reverseSubstReciproFp(const nmod_poly_t F, const nmod_poly_t G, int d, int k)
Definition: facMul.cc:1529
CanonicalForm tailcoeff(const CanonicalForm &f)
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

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

2072 {
2073  CanonicalForm A= F;
2074  CanonicalForm B= G;
2075 
2076  int degAx= degree (A, 1);
2077  int degAy= degree (A, 2);
2078  int degBx= degree (B, 1);
2079  int degBy= degree (B, 2);
2080  int d1= degAx + 1 + degBx;
2081  int d2= tmax (degAy, degBy);
2082 
2083  if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy > degree (M)))
2084  return mulMod2FLINTFqReci (A, B, M, alpha, fq_con);
2085 
2086  fq_nmod_poly_t FLINTA, FLINTB;
2087  kronSubFq (FLINTA, A, d1, fq_con);
2088  kronSubFq (FLINTB, B, d1, fq_con);
2089 
2090  int k= d1*degree (M);
2091  fq_nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k, fq_con);
2092 
2093  A= reverseSubstFq (FLINTA, d1, alpha, fq_con);
2094 
2095  fq_nmod_poly_clear (FLINTA, fq_con);
2096  fq_nmod_poly_clear (FLINTB, fq_con);
2097  return A;
2098 }
void kronSubFq(fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1138
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s main class
Definition: canonicalform.h:77
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
int k
Definition: cfEzgcd.cc:92
static TreeM * G
Definition: janet.cc:32
#define A
Definition: sirandom.c:23
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm reverseSubstFq(const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1886
b *CanonicalForm B
Definition: facBivar.cc:52
int degree(const CanonicalForm &f)
CanonicalForm mulMod2FLINTFqReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:2027

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

2030 {
2031  int d1= degree (F, 1) + degree (G, 1) + 1;
2032  d1 /= 2;
2033  d1 += 1;
2034 
2035  fq_nmod_poly_t F1, F2;
2036  kronSubReciproFq (F1, F2, F, d1, fq_con);
2037 
2038  fq_nmod_poly_t G1, G2;
2039  kronSubReciproFq (G1, G2, G, d1, fq_con);
2040 
2041  int k= d1*degree (M);
2042  fq_nmod_poly_mullow (F1, F1, G1, (long) k, fq_con);
2043 
2044  int degtailF= degree (tailcoeff (F), 1);
2045  int degtailG= degree (tailcoeff (G), 1);
2046  int taildegF= taildegree (F);
2047  int taildegG= taildegree (G);
2048 
2049  int b= k + degtailF + degtailG - d1*(2+taildegF + taildegG);
2050 
2051  fq_nmod_poly_reverse (F2, F2, fq_nmod_poly_length (F2, fq_con), fq_con);
2052  fq_nmod_poly_reverse (G2, G2, fq_nmod_poly_length (G2, fq_con), fq_con);
2053  fq_nmod_poly_mullow (F2, F2, G2, b+1, fq_con);
2054  fq_nmod_poly_reverse (F2, F2, b+1, fq_con);
2055 
2056  int d2= tmax (fq_nmod_poly_degree (F2, fq_con)/d1,
2057  fq_nmod_poly_degree (F1, fq_con)/d1);
2058 
2059  CanonicalForm result= reverseSubstReciproFq (F1, F2, d1, d2, alpha, fq_con);
2060 
2061  fq_nmod_poly_clear (F1, fq_con);
2062  fq_nmod_poly_clear (F2, fq_con);
2063  fq_nmod_poly_clear (G1, fq_con);
2064  fq_nmod_poly_clear (G2, fq_con);
2065  return result;
2066 }
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:1648
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s main class
Definition: canonicalform.h:77
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
int k
Definition: cfEzgcd.cc:92
int taildegree(const CanonicalForm &f)
CanonicalForm b
Definition: cfModGcd.cc:4044
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm tailcoeff(const CanonicalForm &f)
int degree(const CanonicalForm &f)
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:1296
return result
Definition: facAbsBiFact.cc:76

◆ mulMod2FLINTQ()

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

Definition at line 2139 of file facMul.cc.

2141 {
2142  CanonicalForm A= F;
2143  CanonicalForm B= G;
2144 
2145  int degAx= degree (A, 1);
2146  int degBx= degree (B, 1);
2147  int d1= degAx + 1 + degBx;
2148 
2149  CanonicalForm f= bCommonDen (F);
2150  CanonicalForm g= bCommonDen (G);
2151  A *= f;
2152  B *= g;
2153 
2154  fmpz_poly_t FLINTA, FLINTB;
2155  kronSubQa (FLINTA, A, d1);
2156  kronSubQa (FLINTB, B, d1);
2157  int k= d1*degree (M);
2158 
2159  fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k);
2160  A= reverseSubstQ (FLINTA, d1);
2161  fmpz_poly_clear (FLINTA);
2162  fmpz_poly_clear (FLINTB);
2163  return A/(f*g);
2164 }
factory&#39;s main class
Definition: canonicalform.h:77
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:92
CanonicalForm reverseSubstQ(const fmpz_poly_t F, int d)
Definition: facMul.cc:1366
static TreeM * G
Definition: janet.cc:32
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:42
#define A
Definition: sirandom.c:23
FILE * f
Definition: checklibs.c:9
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
b *CanonicalForm B
Definition: facBivar.cc:52
int degree(const CanonicalForm &f)

◆ mulMod2FLINTQa()

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

Definition at line 2199 of file facMul.cc.

2201 {
2202  Variable a;
2203  if (!hasFirstAlgVar (F,a) && !hasFirstAlgVar (G, a))
2204  return mulMod2FLINTQ (F, G, M);
2205  CanonicalForm A= F, B= G;
2206 
2207  int degFx= degree (F, 1);
2208  int degFa= degree (F, a);
2209  int degGx= degree (G, 1);
2210  int degGa= degree (G, a);
2211 
2212  int d2= degFa+degGa+1;
2213  int d1= degFx + 1 + degGx;
2214  d1 *= d2;
2215 
2216  CanonicalForm f= bCommonDen (F);
2217  CanonicalForm g= bCommonDen (G);
2218  A *= f;
2219  B *= g;
2220 
2221  fmpz_poly_t FLINTF, FLINTG;
2222  kronSubQa (FLINTF, A, d1, d2);
2223  kronSubQa (FLINTG, B, d1, d2);
2224 
2225  fmpz_poly_mullow (FLINTF, FLINTF, FLINTG, d1*degree (M));
2226 
2227  fmpq_poly_t mipo;
2228  convertFacCF2Fmpq_poly_t (mipo, getMipo (a));
2229  A= reverseSubstQa (FLINTF, d1, d2, a, mipo);
2230  fmpz_poly_clear (FLINTF);
2231  fmpz_poly_clear (FLINTG);
2232  return A/(f*g);
2233 }
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
Definition: facMul.cc:62
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
g
Definition: cfModGcd.cc:4031
static TreeM * G
Definition: janet.cc:32
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:42
#define A
Definition: sirandom.c:23
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
FILE * f
Definition: checklibs.c:9
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
CanonicalForm mipo
Definition: facAlgExt.cc:57
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mulMod2FLINTQ(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2139
int degree(const CanonicalForm &f)

◆ mulMod2FLINTQReci()

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

Definition at line 2102 of file facMul.cc.

2104 {
2105  int d1= degree (F, 1) + degree (G, 1) + 1;
2106  d1 /= 2;
2107  d1 += 1;
2108 
2109  fmpz_poly_t F1, F2;
2110  kronSubReciproQ (F1, F2, F, d1);
2111 
2112  fmpz_poly_t G1, G2;
2113  kronSubReciproQ (G1, G2, G, d1);
2114 
2115  int k= d1*degree (M);
2116  fmpz_poly_mullow (F1, F1, G1, (long) k);
2117 
2118  int degtailF= degree (tailcoeff (F), 1);;
2119  int degtailG= degree (tailcoeff (G), 1);
2120  int taildegF= taildegree (F);
2121  int taildegG= taildegree (G);
2122 
2123  int b= fmpz_poly_degree (F2) + fmpz_poly_degree (G2) - k - degtailF - degtailG
2124  + d1*(2+taildegF + taildegG);
2125  fmpz_poly_mulhigh_n (F2, F2, G2, b);
2126  fmpz_poly_shift_right (F2, F2, b);
2127  int d2= tmax (fmpz_poly_degree (F2)/d1, fmpz_poly_degree (F1)/d1);
2128 
2129  CanonicalForm result= reverseSubstReciproQ (F1, F2, d1, d2);
2130 
2131  fmpz_poly_clear (F1);
2132  fmpz_poly_clear (F2);
2133  fmpz_poly_clear (G1);
2134  fmpz_poly_clear (G2);
2135  return result;
2136 }
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s main class
Definition: canonicalform.h:77
int k
Definition: cfEzgcd.cc:92
int taildegree(const CanonicalForm &f)
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm reverseSubstReciproQ(const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
Definition: facMul.cc:1752
void kronSubReciproQ(fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm &A, int d)
Definition: facMul.cc:1341
CanonicalForm tailcoeff(const CanonicalForm &f)
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

◆ mulMod2NTLFq()

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

Definition at line 2793 of file facMul.cc.

2795 {
2796  Variable alpha;
2797  CanonicalForm A= F;
2798  CanonicalForm B= G;
2799 
2800  if (hasFirstAlgVar (A, alpha) || hasFirstAlgVar (B, alpha))
2801  {
2802 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
2803  nmod_poly_t FLINTmipo;
2804  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
2805 
2806  fq_nmod_ctx_t fq_con;
2807  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
2808 
2809  A= mulMod2FLINTFq (A, B, M, alpha, fq_con);
2810  nmod_poly_clear (FLINTmipo);
2811  fq_nmod_ctx_clear (fq_con);
2812 #else
2813  int degAx= degree (A, 1);
2814  int degAy= degree (A, 2);
2815  int degBx= degree (B, 1);
2816  int degBy= degree (B, 2);
2817  int d1= degAx + degBx + 1;
2818  int d2= tmax (degAy, degBy);
2820  {
2822  zz_p::init (getCharacteristic());
2823  }
2824  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
2825  zz_pE::init (NTLMipo);
2826 
2827  int degMipo= degree (getMipo (alpha));
2828  if ((d1 > 128/degMipo) && (d2 > 160/degMipo) && (degAy == degBy) &&
2829  (2*degAy > degree (M)))
2830  return mulMod2NTLFqReci (A, B, M, alpha);
2831 
2832  zz_pEX NTLA= kronSubFq (A, d1, alpha);
2833  zz_pEX NTLB= kronSubFq (B, d1, alpha);
2834 
2835  int k= d1*degree (M);
2836 
2837  MulTrunc (NTLA, NTLA, NTLB, (long) k);
2838 
2839  A= reverseSubstFq (NTLA, d1, alpha);
2840 #endif
2841  }
2842  else
2843  {
2844 #ifdef HAVE_FLINT
2845  A= mulMod2FLINTFp (A, B, M);
2846 #else
2847  A= mulMod2NTLFp (A, B, M);
2848 #endif
2849  }
2850  return A;
2851 }
void kronSubFq(fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1138
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
int k
Definition: cfEzgcd.cc:92
Variable alpha
Definition: facAbsBiFact.cc:52
static TreeM * G
Definition: janet.cc:32
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
CanonicalForm mulMod2FLINTFp(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:1995
convertFacCF2nmod_poly_t(FLINTmipo, M)
#define A
Definition: sirandom.c:23
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm reverseSubstFq(const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1886
CanonicalForm mulMod2FLINTFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:2069
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
b *CanonicalForm B
Definition: facBivar.cc:52
long fac_NTL_char
Definition: NTLconvert.cc:41
int degree(const CanonicalForm &f)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

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

408 {
410  return F*G;
411  if (getCharacteristic() == 0)
412  {
413  Variable alpha;
414  if ((!F.inCoeffDomain() && !G.inCoeffDomain()) &&
415  (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha)))
416  {
417  if (b.getp() != 0)
418  {
419  CanonicalForm mipo= getMipo (alpha);
420  bool is_rat= isOn (SW_RATIONAL);
421  if (!is_rat)
422  On (SW_RATIONAL);
423  mipo *=bCommonDen (mipo);
424  if (!is_rat)
425  Off (SW_RATIONAL);
426 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
427  fmpz_t FLINTp;
428  fmpz_mod_poly_t FLINTmipo;
429  fq_ctx_t fq_con;
430  fq_poly_t FLINTF, FLINTG;
431 
432  fmpz_init (FLINTp);
433 
434  convertCF2Fmpz (FLINTp, b.getpk());
435 
436  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
437 
438  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
439 
440  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
441  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
442 
443  fq_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
444 
446  alpha, fq_con);
447 
448  fmpz_clear (FLINTp);
449  fmpz_mod_poly_clear (FLINTmipo);
450  fq_poly_clear (FLINTF, fq_con);
451  fq_poly_clear (FLINTG, fq_con);
452  fq_ctx_clear (fq_con);
453  return b (result);
454 #else
455  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
456  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (mipo));
457  ZZ_pE::init (NTLmipo);
458  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
459  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
460  mul (NTLf, NTLf, NTLg);
461 
462  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
463 #endif
464  }
465 #ifdef HAVE_FLINT
466  CanonicalForm result= mulFLINTQa (F, G, alpha);
467  return result;
468 #else
469  return F*G;
470 #endif
471  }
472  else if (!F.inCoeffDomain() && !G.inCoeffDomain())
473  {
474 #ifdef HAVE_FLINT
475  if (b.getp() != 0)
476  {
477  fmpz_t FLINTpk;
478  fmpz_init (FLINTpk);
479  convertCF2Fmpz (FLINTpk, b.getpk());
480  fmpz_mod_poly_t FLINTF, FLINTG;
481  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
482  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
483  fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
484  CanonicalForm result= convertFmpz_mod_poly_t2FacCF (FLINTF, F.mvar(),b);
485  fmpz_mod_poly_clear (FLINTG);
486  fmpz_mod_poly_clear (FLINTF);
487  fmpz_clear (FLINTpk);
488  return result;
489  }
490  return mulFLINTQ (F, G);
491 #else
492  if (b.getp() != 0)
493  {
494  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
495  ZZX ZZf= convertFacCF2NTLZZX (F);
496  ZZX ZZg= convertFacCF2NTLZZX (G);
497  ZZ_pX NTLf= to_ZZ_pX (ZZf);
498  ZZ_pX NTLg= to_ZZ_pX (ZZg);
499  mul (NTLf, NTLf, NTLg);
500  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
501  }
502  return F*G;
503 #endif
504  }
505  if (b.getp() != 0)
506  {
507  if (!F.inBaseDomain() && !G.inBaseDomain())
508  {
509  if (hasFirstAlgVar (G, alpha) || hasFirstAlgVar (F, alpha))
510  {
511 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
512  fmpz_t FLINTp;
513  fmpz_mod_poly_t FLINTmipo;
514  fq_ctx_t fq_con;
515 
516  fmpz_init (FLINTp);
517  convertCF2Fmpz (FLINTp, b.getpk());
518 
519  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
520 
521  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
522 
524 
525  if (F.inCoeffDomain() && !G.inCoeffDomain())
526  {
527  fq_poly_t FLINTG;
528  fmpz_poly_t FLINTF;
529  convertFacCF2Fmpz_poly_t (FLINTF, F);
530  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
531 
532  fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF, fq_con);
533 
534  result= convertFq_poly_t2FacCF (FLINTG, G.mvar(), alpha, fq_con);
535  fmpz_poly_clear (FLINTF);
536  fq_poly_clear (FLINTG, fq_con);
537  }
538  else if (!F.inCoeffDomain() && G.inCoeffDomain())
539  {
540  fq_poly_t FLINTF;
541  fmpz_poly_t FLINTG;
542 
543  convertFacCF2Fmpz_poly_t (FLINTG, G);
544  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
545 
546  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
547 
548  result= convertFq_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
549  fmpz_poly_clear (FLINTG);
550  fq_poly_clear (FLINTF, fq_con);
551  }
552  else
553  {
554  fq_t FLINTF, FLINTG;
555 
556  convertFacCF2Fq_t (FLINTF, F, fq_con);
557  convertFacCF2Fq_t (FLINTG, G, fq_con);
558 
559  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
560 
561  result= convertFq_t2FacCF (FLINTF, alpha);
562  fq_clear (FLINTF, fq_con);
563  fq_clear (FLINTG, fq_con);
564  }
565 
566  fmpz_clear (FLINTp);
567  fmpz_mod_poly_clear (FLINTmipo);
568  fq_ctx_clear (fq_con);
569 
570  return b (result);
571 #else
572  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
573  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
574  ZZ_pE::init (NTLmipo);
575 
576  if (F.inCoeffDomain() && !G.inCoeffDomain())
577  {
578  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
579  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
580  mul (NTLg, to_ZZ_pE (NTLf), NTLg);
581  return b (convertNTLZZ_pEX2CF (NTLg, G.mvar(), alpha));
582  }
583  else if (!F.inCoeffDomain() && G.inCoeffDomain())
584  {
585  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
586  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
587  mul (NTLf, NTLf, to_ZZ_pE (NTLg));
588  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
589  }
590  else
591  {
592  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
593  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
594  ZZ_pE result;
595  mul (result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
596  return b (convertNTLZZpX2CF (rep (result), alpha));
597  }
598 #endif
599  }
600  }
601  return b (F*G);
602  }
603  return F*G;
604  }
605  else if (F.inCoeffDomain() || G.inCoeffDomain())
606  return F*G;
607  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
608  ASSERT (F.level() == G.level(), "expected polys of same level");
610  {
612  zz_p::init (getCharacteristic());
613  }
614  Variable alpha;
616  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
617  {
618  if (!getReduce (alpha))
619  {
620  result= 0;
621  for (CFIterator i= F; i.hasTerms(); i++)
622  result += i.coeff()*G*power (F.mvar(),i.exp());
623  return result;
624  }
625 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
626  nmod_poly_t FLINTmipo;
627  fq_nmod_ctx_t fq_con;
628 
629  nmod_poly_init (FLINTmipo, getCharacteristic());
630  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
631 
632  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
633 
634  fq_nmod_poly_t FLINTF, FLINTG;
635  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
636  convertFacCF2Fq_nmod_poly_t (FLINTG, G, fq_con);
637 
638  fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
639 
640  result= convertFq_nmod_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
641 
642  fq_nmod_poly_clear (FLINTF, fq_con);
643  fq_nmod_poly_clear (FLINTG, fq_con);
644  nmod_poly_clear (FLINTmipo);
645  fq_nmod_ctx_clear (fq_con);
646 #else
647  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
648  zz_pE::init (NTLMipo);
649  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
650  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
651  mul (NTLF, NTLF, NTLG);
652  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
653 #endif
654  }
655  else
656  {
657 #ifdef HAVE_FLINT
658  nmod_poly_t FLINTF, FLINTG;
659  convertFacCF2nmod_poly_t (FLINTF, F);
660  convertFacCF2nmod_poly_t (FLINTG, G);
661  nmod_poly_mul (FLINTF, FLINTF, FLINTG);
662  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
663  nmod_poly_clear (FLINTF);
664  nmod_poly_clear (FLINTG);
665 #else
666  zz_pX NTLF= convertFacCF2NTLzzpX (F);
667  zz_pX NTLG= convertFacCF2NTLzzpX (G);
668  mul (NTLF, NTLF, NTLG);
669  result= convertNTLzzpX2CF(NTLF, F.mvar());
670 #endif
671  }
672  return result;
673 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
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...
nmod_poly_init(FLINTmipo, getCharacteristic())
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:664
void convertCF2Fmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t
Definition: FLINTconvert.cc:61
void Off(int sw)
switches
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
factory&#39;s class for variables
Definition: factory.h:117
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
Definition: NTLconvert.cc:243
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
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
Definition: NTLconvert.cc:1036
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
CanonicalForm mulFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:129
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
Variable alpha
Definition: facAbsBiFact.cc:52
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...
static TreeM * G
Definition: janet.cc:32
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
CanonicalForm b
Definition: cfModGcd.cc:4044
bool inBaseDomain() const
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1114
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
Definition: NTLconvert.cc:59
convertFacCF2nmod_poly_t(FLINTmipo, M)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
bool isUnivariate() const
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm mulFLINTQa(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
Definition: facMul.cc:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:125
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
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) ...
static int gettype()
Definition: cf_factory.h:28
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
CanonicalForm mipo
Definition: facAlgExt.cc:57
CanonicalForm getpk() const
Definition: fac_util.h:38
#define GaloisFieldDomain
Definition: cf_defs.h:22
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 ...
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
long fac_NTL_char
Definition: NTLconvert.cc:41
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 ...
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:278
return result
Definition: facAbsBiFact.cc:76
int getp() const
Definition: fac_util.h:35
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. variable alpha and polynomial variable x
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

◆ newtonDiv() [1/2]

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

Definition at line 376 of file facMul.cc.

377 {
378  ASSERT (F.level() == G.level(), "F and G have different level");
379  CanonicalForm A= F;
380  CanonicalForm B= G;
381  Variable x= A.mvar();
382  int degA= degree (A);
383  int degB= degree (B);
384  int m= degA - degB;
385 
386  if (m < 0)
387  {
388  Q= 0;
389  return;
390  }
391 
392  if (degB <= 1)
393  Q= div (A, B);
394  else
395  {
396  CanonicalForm R= uniReverse (A, degA, x);
397  CanonicalForm revB= uniReverse (B, degB, x);
398  revB= newtonInverse (revB, m + 1, x);
399  Q= mulFLINTQTrunc (R, revB, m + 1);
400  Q= uniReverse (Q, m, x);
401  }
402 }
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:32
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
Definition: facMul.cc:237
#define A
Definition: sirandom.c:23
int m
Definition: cfEzgcd.cc:121
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
b *CanonicalForm B
Definition: facBivar.cc:52
#define R
Definition: sirandom.c:26
Variable x
Definition: cfModGcd.cc:4023
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
Definition: facMul.cc:270
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:287

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

3182 {
3183  ASSERT (getCharacteristic() > 0, "positive characteristic expected");
3184 
3185  CanonicalForm A= mod (F, M);
3186  CanonicalForm B= mod (G, M);
3187 
3188  Variable x= Variable (1);
3189  int degA= degree (A, x);
3190  int degB= degree (B, x);
3191  int m= degA - degB;
3192  if (m < 0)
3193  return 0;
3194 
3195  Variable v;
3196  CanonicalForm Q;
3197  if (degB < 1 || CFFactory::gettype() == GaloisFieldDomain)
3198  {
3199  CanonicalForm R;
3200  divrem2 (A, B, Q, R, M);
3201  }
3202  else
3203  {
3204  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3205  {
3206  CanonicalForm R= reverse (A, degA);
3207  CanonicalForm revB= reverse (B, degB);
3208  revB= newtonInverse (revB, m + 1, M);
3209  Q= mulMod2 (R, revB, M);
3210  Q= mod (Q, power (x, m + 1));
3211  Q= reverse (Q, m);
3212  }
3213  else
3214  {
3215  Variable y= Variable (2);
3216 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3217  nmod_poly_t FLINTmipo;
3218  fq_nmod_ctx_t fq_con;
3219 
3220  nmod_poly_init (FLINTmipo, getCharacteristic());
3221  convertFacCF2nmod_poly_t (FLINTmipo, M);
3222 
3223  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3224 
3225 
3226  fq_nmod_poly_t FLINTA, FLINTB;
3227  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3228  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3229 
3230  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3231 
3232  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3233 
3234  fq_nmod_poly_clear (FLINTA, fq_con);
3235  fq_nmod_poly_clear (FLINTB, fq_con);
3236  nmod_poly_clear (FLINTmipo);
3237  fq_nmod_ctx_clear (fq_con);
3238 #else
3239  bool zz_pEbak= zz_pE::initialized();
3240  zz_pEBak bak;
3241  if (zz_pEbak)
3242  bak.save();
3243  zz_pX mipo= convertFacCF2NTLzzpX (M);
3244  zz_pEX NTLA, NTLB;
3245  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3246  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3247  div (NTLA, NTLA, NTLB);
3248  Q= convertNTLzz_pEX2CF (NTLA, x, y);
3249  if (zz_pEbak)
3250  bak.restore();
3251 #endif
3252  }
3253  }
3254 
3255  return Q;
3256 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
nmod_poly_init(FLINTmipo, getCharacteristic())
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:117
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
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
#define Q
Definition: sirandom.c:25
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...
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
convertFacCF2nmod_poly_t(FLINTmipo, M)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
#define A
Definition: sirandom.c:23
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
int m
Definition: cfEzgcd.cc:121
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
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:3516
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
static int gettype()
Definition: cf_factory.h:28
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
CanonicalForm mipo
Definition: facAlgExt.cc:57
b *CanonicalForm B
Definition: facBivar.cc:52
#define R
Definition: sirandom.c:26
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm reverse(const CanonicalForm &F, int d)
Definition: facMul.cc:3101
int degree(const CanonicalForm &f)
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:287
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

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

344 {
345  ASSERT (F.level() == G.level(), "F and G have different level");
346  CanonicalForm A= F;
347  CanonicalForm B= G;
348  Variable x= A.mvar();
349  int degA= degree (A);
350  int degB= degree (B);
351  int m= degA - degB;
352 
353  if (m < 0)
354  {
355  R= A;
356  Q= 0;
357  return;
358  }
359 
360  if (degB <= 1)
361  divrem (A, B, Q, R);
362  else
363  {
364  R= uniReverse (A, degA, x);
365 
366  CanonicalForm revB= uniReverse (B, degB, x);
367  revB= newtonInverse (revB, m + 1, x);
368  Q= mulFLINTQTrunc (R, revB, m + 1);
369  Q= uniReverse (Q, m, x);
370 
371  R= A - mulNTL (Q, B);
372  }
373 }
factory&#39;s class for variables
Definition: factory.h:117
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:3583
factory&#39;s main class
Definition: canonicalform.h:77
static TreeM * G
Definition: janet.cc:32
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&#39;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).
Definition: facMul.cc:407
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
Definition: facMul.cc:237
#define A
Definition: sirandom.c:23
int m
Definition: cfEzgcd.cc:121
b *CanonicalForm B
Definition: facBivar.cc:52
Variable x
Definition: cfModGcd.cc:4023
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
Definition: facMul.cc:270
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:287

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

3261 {
3262  CanonicalForm A= mod (F, M);
3263  CanonicalForm B= mod (G, M);
3264  Variable x= Variable (1);
3265  int degA= degree (A, x);
3266  int degB= degree (B, x);
3267  int m= degA - degB;
3268 
3269  if (m < 0)
3270  {
3271  R= A;
3272  Q= 0;
3273  return;
3274  }
3275 
3276  Variable v;
3277  if (degB <= 1 || CFFactory::gettype() == GaloisFieldDomain)
3278  {
3279  divrem2 (A, B, Q, R, M);
3280  }
3281  else
3282  {
3283  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3284  {
3285  R= reverse (A, degA);
3286 
3287  CanonicalForm revB= reverse (B, degB);
3288  revB= newtonInverse (revB, m + 1, M);
3289  Q= mulMod2 (R, revB, M);
3290 
3291  Q= mod (Q, power (x, m + 1));
3292  Q= reverse (Q, m);
3293 
3294  R= A - mulMod2 (Q, B, M);
3295  }
3296  else
3297  {
3298  Variable y= Variable (2);
3299 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3300  nmod_poly_t FLINTmipo;
3301  fq_nmod_ctx_t fq_con;
3302 
3303  nmod_poly_init (FLINTmipo, getCharacteristic());
3304  convertFacCF2nmod_poly_t (FLINTmipo, M);
3305 
3306  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3307 
3308  fq_nmod_poly_t FLINTA, FLINTB;
3309  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3310  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3311 
3312  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3313 
3314  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3315  R= convertFq_nmod_poly_t2FacCF (FLINTB, x, y, fq_con);
3316 
3317  fq_nmod_poly_clear (FLINTA, fq_con);
3318  fq_nmod_poly_clear (FLINTB, fq_con);
3319  nmod_poly_clear (FLINTmipo);
3320  fq_nmod_ctx_clear (fq_con);
3321 #else
3322  zz_pX mipo= convertFacCF2NTLzzpX (M);
3323  zz_pEX NTLA, NTLB;
3324  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3325  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3326  zz_pEX NTLQ, NTLR;
3327  DivRem (NTLQ, NTLR, NTLA, NTLB);
3328  Q= convertNTLzz_pEX2CF (NTLQ, x, y);
3329  R= convertNTLzz_pEX2CF (NTLR, x, y);
3330 #endif
3331  }
3332  }
3333 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
nmod_poly_init(FLINTmipo, getCharacteristic())
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:117
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
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
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...
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
convertFacCF2nmod_poly_t(FLINTmipo, M)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
#define A
Definition: sirandom.c:23
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
int m
Definition: cfEzgcd.cc:121
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
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:3516
static int gettype()
Definition: cf_factory.h:28
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
CanonicalForm mipo
Definition: facAlgExt.cc:57
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CanonicalForm reverse(const CanonicalForm &F, int d)
Definition: facMul.cc:3101
int degree(const CanonicalForm &f)
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:287
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

◆ newtonInverse() [1/2]

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

Definition at line 287 of file facMul.cc.

288 {
289  int l= ilog2(n);
290 
292  if (F.inCoeffDomain())
293  g= F;
294  else
295  g= F [0];
296 
297  if (!F.inCoeffDomain())
298  ASSERT (F.mvar() == x, "main variable of F and x differ");
299  ASSERT (!g.isZero(), "expected a unit");
300 
301  if (!g.isOne())
302  g = 1/g;
304  int exp= 0;
305  if (n & 1)
306  {
307  result= g;
308  exp= 1;
309  }
311 
312  for (int i= 1; i <= l; i++)
313  {
314  h= mulNTL (g, mod (F, power (x, (1 << i))));
315  h= mod (h, power (x, (1 << i)) - 1);
316  h= div (h, power (x, (1 << (i - 1))));
317  g -= power (x, (1 << (i - 1)))*
318  mulFLINTQTrunc (g, h, 1 << (i-1));
319 
320  if (n & (1 << i))
321  {
322  if (exp)
323  {
324  h= mulNTL (result, mod (F, power (x, exp + (1 << i))));
325  h= mod (h, power (x, exp + (1 << i)) - 1);
326  h= div (h, power (x, exp));
327  result -= power(x, exp)*mulFLINTQTrunc (g, h, 1 << i);
328  exp += (1 << i);
329  }
330  else
331  {
332  exp= (1 << i);
333  result= g;
334  }
335  }
336  }
337 
338  return result;
339 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
g
Definition: cfModGcd.cc:4031
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&#39;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).
Definition: facMul.cc:407
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
Definition: facMul.cc:237
int i
Definition: cfEzgcd.cc:125
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int ilog2(const CanonicalForm &a)
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static Poly * h
Definition: janet.cc:972
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:93
bool inCoeffDomain() const

◆ newtonInverse() [2/2]

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

Definition at line 3125 of file facMul.cc.

3126 {
3127  int l= ilog2(n);
3128 
3129  CanonicalForm g= mod (F, M)[0] [0];
3130 
3131  ASSERT (!g.isZero(), "expected a unit");
3132 
3133  Variable alpha;
3134 
3135  if (!g.isOne())
3136  g = 1/g;
3137  Variable x= Variable (1);
3139  int exp= 0;
3140  if (n & 1)
3141  {
3142  result= g;
3143  exp= 1;
3144  }
3145  CanonicalForm h;
3146 
3147  for (int i= 1; i <= l; i++)
3148  {
3149  h= mulMod2 (g, mod (F, power (x, (1 << i))), M);
3150  h= mod (h, power (x, (1 << i)) - 1);
3151  h= div (h, power (x, (1 << (i - 1))));
3152  h= mod (h, M);
3153  g -= power (x, (1 << (i - 1)))*
3154  mod (mulMod2 (g, h, M), power (x, (1 << (i - 1))));
3155 
3156  if (n & (1 << i))
3157  {
3158  if (exp)
3159  {
3160  h= mulMod2 (result, mod (F, power (x, exp + (1 << i))), M);
3161  h= mod (h, power (x, exp + (1 << i)) - 1);
3162  h= div (h, power (x, exp));
3163  h= mod (h, M);
3164  result -= power(x, exp)*mod (mulMod2 (g, h, M),
3165  power (x, (1 << i)));
3166  exp += (1 << i);
3167  }
3168  else
3169  {
3170  exp= (1 << i);
3171  result= g;
3172  }
3173  }
3174  }
3175 
3176  return result;
3177 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:77
g
Definition: cfModGcd.cc:4031
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
int i
Definition: cfEzgcd.cc:125
int ilog2(const CanonicalForm &a)
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
Variable x
Definition: cfModGcd.cc:4023
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static Poly * h
Definition: janet.cc:972
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:93

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

3048 {
3049  if (L.isEmpty())
3050  return 1;
3051  int l= L.length();
3052  if (l == 1)
3053  return mod (L.getFirst(), M);
3054  else if (l == 2) {
3056  return result;
3057  }
3058  else
3059  {
3060  l /= 2;
3061  CFList tmp1, tmp2;
3062  CFListIterator i= L;
3064  for (int j= 1; j <= l; j++, i++)
3065  tmp1.append (i.getItem());
3066  tmp2= Difference (L, tmp1);
3067  buf1= prodMod (tmp1, M);
3068  buf2= prodMod (tmp2, M);
3069  CanonicalForm result= mulMod2 (buf1, buf2, M);
3070  return result;
3071  }
3072 }
int j
Definition: facHensel.cc:105
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm buf1
Definition: facFqBivar.cc:71
factory&#39;s main class
Definition: canonicalform.h:77
T getFirst() const
Definition: ftmpl_list.cc:279
#define M
Definition: sirandom.c:24
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
int i
Definition: cfEzgcd.cc:125
T getLast() const
Definition: ftmpl_list.cc:309
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm buf2
Definition: facFqBivar.cc:71
int length() const
Definition: ftmpl_list.cc:273
CFList tmp1
Definition: facFqBivar.cc:70
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:93
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047

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

3075 {
3076  if (L.isEmpty())
3077  return 1;
3078  else if (L.length() == 1)
3079  return L.getFirst();
3080  else if (L.length() == 2)
3081  return mulMod (L.getFirst(), L.getLast(), M);
3082  else
3083  {
3084  int l= L.length()/2;
3085  CFListIterator i= L;
3086  CFList tmp1, tmp2;
3088  for (int j= 1; j <= l; j++, i++)
3089  tmp1.append (i.getItem());
3090  tmp2= Difference (L, tmp1);
3091  buf1= prodMod (tmp1, M);
3092  buf2= prodMod (tmp2, M);
3093  return mulMod (buf1, buf2, M);
3094  }
3095 }
int j
Definition: facHensel.cc:105
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm buf1
Definition: facFqBivar.cc:71
factory&#39;s main class
Definition: canonicalform.h:77
T getFirst() const
Definition: ftmpl_list.cc:279
#define M
Definition: sirandom.c:24
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:125
T getLast() const
Definition: ftmpl_list.cc:309
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm buf2
Definition: facFqBivar.cc:71
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
int length() const
Definition: ftmpl_list.cc:273
CFList tmp1
Definition: facFqBivar.cc:70
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int l
Definition: cfEzgcd.cc:93
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047

◆ reverse()

CanonicalForm reverse ( const CanonicalForm F,
int  d 
)

Definition at line 3101 of file facMul.cc.

3102 {
3103  if (d == 0)
3104  return F;
3105  CanonicalForm A= F;
3106  Variable y= Variable (2);
3107  Variable x= Variable (1);
3108  if (degree (A, x) > 0)
3109  {
3110  A= swapvar (A, x, y);
3111  CanonicalForm result= 0;
3112  CFIterator i= A;
3113  while (d - i.exp() < 0)
3114  i++;
3115 
3116  for (; i.hasTerms() && (d - i.exp() >= 0); i++)
3117  result += swapvar (i.coeff(),x,y)*power (x, d - i.exp());
3118  return result;
3119  }
3120  else
3121  return A*power (x, d);
3122 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:77
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

◆ reverseSubstFp()

CanonicalForm reverseSubstFp ( const nmod_poly_t  F,
int  d 
)

Definition at line 1921 of file facMul.cc.

1922 {
1923  Variable y= Variable (2);
1924  Variable x= Variable (1);
1925 
1926  mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1927 
1928  nmod_poly_t buf;
1929  CanonicalForm result= 0;
1930  int i= 0;
1931  int degf= nmod_poly_degree(F);
1932  int k= 0;
1933  int degfSubK, repLength, j;
1934  while (degf >= k)
1935  {
1936  degfSubK= degf - k;
1937  if (degfSubK >= d)
1938  repLength= d;
1939  else
1940  repLength= degfSubK + 1;
1941 
1942  nmod_poly_init2_preinv (buf, getCharacteristic(), ninv, repLength);
1943  for (j= 0; j < repLength; j++)
1944  nmod_poly_set_coeff_ui (buf, j, nmod_poly_get_coeff_ui (F, j + k));
1945  _nmod_poly_normalise (buf);
1946 
1947  result += convertnmod_poly_t2FacCF (buf, x)*power (y, i);
1948  i++;
1949  k= d*i;
1950  nmod_poly_clear (buf);
1951  }
1952 
1953  return result;
1954 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
int j
Definition: facHensel.cc:105
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
int k
Definition: cfEzgcd.cc:92
int getCharacteristic()
Definition: cf_char.cc:51
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
Variable x
Definition: cfModGcd.cc:4023
return result
Definition: facAbsBiFact.cc:76
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm

◆ reverseSubstFq()

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

Definition at line 1886 of file facMul.cc.

1888 {
1889  Variable y= Variable (2);
1890  Variable x= Variable (1);
1891 
1892  fq_nmod_poly_t buf;
1893  CanonicalForm result= 0;
1894  int i= 0;
1895  int degf= fq_nmod_poly_degree(F, fq_con);
1896  int k= 0;
1897  int degfSubK, repLength;
1898  while (degf >= k)
1899  {
1900  degfSubK= degf - k;
1901  if (degfSubK >= d)
1902  repLength= d;
1903  else
1904  repLength= degfSubK + 1;
1905 
1906  fq_nmod_poly_init2 (buf, repLength, fq_con);
1907  _fq_nmod_poly_set_length (buf, repLength, fq_con);
1908  _fq_nmod_vec_set (buf->coeffs, F->coeffs+k, repLength, fq_con);
1909  _fq_nmod_poly_normalise (buf, fq_con);
1910 
1911  result += convertFq_nmod_poly_t2FacCF (buf, x, alpha, fq_con)*power (y, i);
1912  i++;
1913  k= d*i;
1914  fq_nmod_poly_clear (buf, fq_con);
1915  }
1916 
1917  return result;
1918 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
int k
Definition: cfEzgcd.cc:92
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...
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
fq_nmod_poly_clear(prod, fq_con)
Variable x
Definition: cfModGcd.cc:4023
return result
Definition: facAbsBiFact.cc:76

◆ reverseSubstQ()

CanonicalForm reverseSubstQ ( const fmpz_poly_t  F,
int  d 
)

Definition at line 1366 of file facMul.cc.

1367 {
1368  Variable y= Variable (2);
1369  Variable x= Variable (1);
1370 
1371  fmpz_poly_t buf;
1372  CanonicalForm result= 0;
1373  int i= 0;
1374  int degf= fmpz_poly_degree(F);
1375  int k= 0;
1376  int degfSubK, repLength;
1377  while (degf >= k)
1378  {
1379  degfSubK= degf - k;
1380  if (degfSubK >= d)
1381  repLength= d;
1382  else
1383  repLength= degfSubK + 1;
1384 
1385  fmpz_poly_init2 (buf, repLength);
1386  _fmpz_poly_set_length (buf, repLength);
1387  _fmpz_vec_set (buf->coeffs, F->coeffs+k, repLength);
1388  _fmpz_poly_normalise (buf);
1389 
1390  result += convertFmpz_poly_t2FacCF (buf, x)*power (y, i);
1391  i++;
1392  k= d*i;
1393  fmpz_poly_clear (buf);
1394  }
1395 
1396  return result;
1397 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
int k
Definition: cfEzgcd.cc:92
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
Variable x
Definition: cfModGcd.cc:4023
return result
Definition: facAbsBiFact.cc:76

◆ reverseSubstQa() [1/2]

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

Definition at line 62 of file facMul.cc.

64 {
66  int i= 0;
67  int degf= fmpz_poly_degree (F);
68  int k= 0;
69  int degfSubK;
70  int repLength;
71  fmpq_poly_t buf;
72  fmpq_poly_t mipo;
73  convertFacCF2Fmpq_poly_t (mipo, getMipo(alpha));
74  while (degf >= k)
75  {
76  degfSubK= degf - k;
77  if (degfSubK >= d)
78  repLength= d;
79  else
80  repLength= degfSubK + 1;
81 
82  fmpq_poly_init2 (buf, repLength);
83  _fmpq_poly_set_length (buf, repLength);
84  _fmpz_vec_set (buf->coeffs, F->coeffs + k, repLength);
85  _fmpq_poly_normalise (buf);
86  fmpq_poly_rem (buf, buf, mipo);
87 
88  result += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, i);
89  fmpq_poly_clear (buf);
90  i++;
91  k= d*i;
92  }
93  fmpq_poly_clear (mipo);
94  result /= den;
95  return result;
96 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s main class
Definition: canonicalform.h:77
int k
Definition: cfEzgcd.cc:92
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
CanonicalForm den(const CanonicalForm &f)
CanonicalForm mipo
Definition: facAlgExt.cc:57
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
return result
Definition: facAbsBiFact.cc:76

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

1474 {
1475  Variable y= Variable (2);
1476  Variable x= Variable (1);
1477 
1478  fmpq_poly_t buf;
1479  CanonicalForm result= 0, result2;
1480  int i= 0;
1481  int degf= fmpz_poly_degree(F);
1482  int k= 0;
1483  int degfSubK;
1484  int repLength;
1485  while (degf >= k)
1486  {
1487  degfSubK= degf - k;
1488  if (degfSubK >= d1)
1489  repLength= d1;
1490  else
1491  repLength= degfSubK + 1;
1492 
1493  int j= 0;
1494  result2= 0;
1495  while (j*d2 < repLength)
1496  {
1497  fmpq_poly_init2 (buf, d2);
1498  _fmpq_poly_set_length (buf, d2);
1499  _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, d2);
1500  _fmpq_poly_normalise (buf);
1501  fmpq_poly_rem (buf, buf, mipo);
1502  result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1503  j++;
1504  fmpq_poly_clear (buf);
1505  }
1506  if (repLength - j*d2 != 0 && j*d2 - repLength < d2)
1507  {
1508  j--;
1509  repLength -= j*d2;
1510  fmpq_poly_init2 (buf, repLength);
1511  _fmpq_poly_set_length (buf, repLength);
1512  j++;
1513  _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, repLength);
1514  _fmpq_poly_normalise (buf);
1515  fmpq_poly_rem (buf, buf, mipo);
1516  result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1517  fmpq_poly_clear (buf);
1518  }
1519 
1520  result += result2*power (y, i);
1521  i++;
1522  k= d1*i;
1523  }
1524 
1525  return result;
1526 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
int j
Definition: facHensel.cc:105
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
int k
Definition: cfEzgcd.cc:92
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:125
CanonicalForm mipo
Definition: facAlgExt.cc:57
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
return result
Definition: facAbsBiFact.cc:76

◆ reverseSubstReciproFp()

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

Definition at line 1529 of file facMul.cc.

1530 {
1531  Variable y= Variable (2);
1532  Variable x= Variable (1);
1533 
1534  nmod_poly_t f, g;
1535  mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1536  nmod_poly_init_preinv (f, getCharacteristic(), ninv);
1537  nmod_poly_init_preinv (g, getCharacteristic(), ninv);
1538  nmod_poly_set (f, F);
1539  nmod_poly_set (g, G);
1540  int degf= nmod_poly_degree(f);
1541  int degg= nmod_poly_degree(g);
1542 
1543 
1544  nmod_poly_t buf1,buf2, buf3;
1545 
1546  if (nmod_poly_length (f) < (long) d*(k+1)) //zero padding
1547  nmod_poly_fit_length (f,(long)d*(k+1));
1548 
1549  CanonicalForm result= 0;
1550  int i= 0;
1551  int lf= 0;
1552  int lg= d*k;
1553  int degfSubLf= degf;
1554  int deggSubLg= degg-lg;
1555  int repLengthBuf2, repLengthBuf1, ind, tmp;
1556  while (degf >= lf || lg >= 0)
1557  {
1558  if (degfSubLf >= d)
1559  repLengthBuf1= d;
1560  else if (degfSubLf < 0)
1561  repLengthBuf1= 0;
1562  else
1563  repLengthBuf1= degfSubLf + 1;
1564  nmod_poly_init2_preinv (buf1, getCharacteristic(), ninv, repLengthBuf1);
1565 
1566  for (ind= 0; ind < repLengthBuf1; ind++)
1567  nmod_poly_set_coeff_ui (buf1, ind, nmod_poly_get_coeff_ui (f, ind+lf));
1568  _nmod_poly_normalise (buf1);
1569 
1570  repLengthBuf1= nmod_poly_length (buf1);
1571 
1572  if (deggSubLg >= d - 1)
1573  repLengthBuf2= d - 1;
1574  else if (deggSubLg < 0)
1575  repLengthBuf2= 0;
1576  else
1577  repLengthBuf2= deggSubLg + 1;
1578 
1579  nmod_poly_init2_preinv (buf2, getCharacteristic(), ninv, repLengthBuf2);
1580  for (ind= 0; ind < repLengthBuf2; ind++)
1581  nmod_poly_set_coeff_ui (buf2, ind, nmod_poly_get_coeff_ui (g, ind + lg));
1582 
1583  _nmod_poly_normalise (buf2);
1584  repLengthBuf2= nmod_poly_length (buf2);
1585 
1586  nmod_poly_init2_preinv (buf3, getCharacteristic(), ninv, repLengthBuf2 + d);
1587  for (ind= 0; ind < repLengthBuf1; ind++)
1588  nmod_poly_set_coeff_ui (buf3, ind, nmod_poly_get_coeff_ui (buf1, ind));
1589  for (ind= repLengthBuf1; ind < d; ind++)
1590  nmod_poly_set_coeff_ui (buf3, ind, 0);
1591  for (ind= 0; ind < repLengthBuf2; ind++)
1592  nmod_poly_set_coeff_ui (buf3, ind+d, nmod_poly_get_coeff_ui (buf2, ind));
1593  _nmod_poly_normalise (buf3);
1594 
1595  result += convertnmod_poly_t2FacCF (buf3, x)*power (y, i);
1596  i++;
1597 
1598 
1599  lf= i*d;
1600  degfSubLf= degf - lf;
1601 
1602  lg= d*(k-i);
1603  deggSubLg= degg - lg;
1604 
1605  if (lg >= 0 && deggSubLg > 0)
1606  {
1607  if (repLengthBuf2 > degfSubLf + 1)
1608  degfSubLf= repLengthBuf2 - 1;
1609  tmp= tmin (repLengthBuf1, deggSubLg + 1);
1610  for (ind= 0; ind < tmp; ind++)
1611  nmod_poly_set_coeff_ui (g, ind + lg,
1612  n_submod (nmod_poly_get_coeff_ui (g, ind + lg),
1613  nmod_poly_get_coeff_ui (buf1, ind),
1615  )
1616  );
1617  }
1618  if (lg < 0)
1619  {
1620  nmod_poly_clear (buf1);
1621  nmod_poly_clear (buf2);
1622  nmod_poly_clear (buf3);
1623  break;
1624  }
1625  if (degfSubLf >= 0)
1626  {
1627  for (ind= 0; ind < repLengthBuf2; ind++)
1628  nmod_poly_set_coeff_ui (f, ind + lf,
1629  n_submod (nmod_poly_get_coeff_ui (f, ind + lf),
1630  nmod_poly_get_coeff_ui (buf2, ind),
1632  )
1633  );
1634  }
1635  nmod_poly_clear (buf1);
1636  nmod_poly_clear (buf2);
1637  nmod_poly_clear (buf3);
1638  }
1639 
1640  nmod_poly_clear (f);
1641  nmod_poly_clear (g);
1642 
1643  return result;
1644 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm buf1
Definition: facFqBivar.cc:71
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:92
static TreeM * G
Definition: janet.cc:32
int getCharacteristic()
Definition: cf_char.cc:51
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
CanonicalForm buf2
Definition: facFqBivar.cc:71
Variable x
Definition: cfModGcd.cc:4023
mipo *int degg
Definition: facAlgExt.cc:61
return result
Definition: facAbsBiFact.cc:76
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
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 1648 of file facMul.cc.

1650 {
1651  Variable y= Variable (2);
1652  Variable x= Variable (1);
1653 
1654  fq_nmod_poly_t f, g;
1655  int degf= fq_nmod_poly_degree(F, fq_con);
1656  int degg= fq_nmod_poly_degree(G, fq_con);
1657 
1658  fq_nmod_poly_t buf1,buf2, buf3;
1659 
1662  fq_nmod_poly_set (f, F, fq_con);
1663  fq_nmod_poly_set (g, G, fq_con);
1664  if (fq_nmod_poly_length (f, fq_con) < (long) d*(k + 1)) //zero padding
1665  fq_nmod_poly_fit_length (f, (long) d*(k + 1), fq_con);
1666 
1667  CanonicalForm result= 0;
1668  int i= 0;
1669  int lf= 0;
1670  int lg= d*k;
1671  int degfSubLf= degf;
1672  int deggSubLg= degg-lg;
1673  int repLengthBuf2, repLengthBuf1, tmp;
1674  while (degf >= lf || lg >= 0)
1675  {
1676  if (degfSubLf >= d)
1677  repLengthBuf1= d;
1678  else if (degfSubLf < 0)
1679  repLengthBuf1= 0;
1680  else
1681  repLengthBuf1= degfSubLf + 1;
1682  fq_nmod_poly_init2 (buf1, repLengthBuf1, fq_con);
1683  _fq_nmod_poly_set_length (buf1, repLengthBuf1, fq_con);
1684 
1685  _fq_nmod_vec_set (buf1->coeffs, f->coeffs + lf, repLengthBuf1, fq_con);
1686  _fq_nmod_poly_normalise (buf1, fq_con);
1687 
1688  repLengthBuf1= fq_nmod_poly_length (buf1, fq_con);
1689 
1690  if (deggSubLg >= d - 1)
1691  repLengthBuf2= d - 1;
1692  else if (deggSubLg < 0)
1693  repLengthBuf2= 0;
1694  else
1695  repLengthBuf2= deggSubLg + 1;
1696 
1697  fq_nmod_poly_init2 (buf2, repLengthBuf2, fq_con);
1698  _fq_nmod_poly_set_length (buf2, repLengthBuf2, fq_con);
1699  _fq_nmod_vec_set (buf2->coeffs, g->coeffs + lg, repLengthBuf2, fq_con);
1700 
1701  _fq_nmod_poly_normalise (buf2, fq_con);
1702  repLengthBuf2= fq_nmod_poly_length (buf2, fq_con);
1703 
1704  fq_nmod_poly_init2 (buf3, repLengthBuf2 + d, fq_con);
1705  _fq_nmod_poly_set_length (buf3, repLengthBuf2 + d, fq_con);
1706  _fq_nmod_vec_set (buf3->coeffs, buf1->coeffs, repLengthBuf1, fq_con);
1707  _fq_nmod_vec_set (buf3->coeffs + d, buf2->coeffs, repLengthBuf2, fq_con);
1708 
1709  _fq_nmod_poly_normalise (buf3, fq_con);
1710 
1711  result += convertFq_nmod_poly_t2FacCF (buf3, x, alpha, fq_con)*power (y, i);
1712  i++;
1713 
1714 
1715  lf= i*d;
1716  degfSubLf= degf - lf;
1717 
1718  lg= d*(k - i);
1719  deggSubLg= degg - lg;
1720 
1721  if (lg >= 0 && deggSubLg > 0)
1722  {
1723  if (repLengthBuf2 > degfSubLf + 1)
1724  degfSubLf= repLengthBuf2 - 1;
1725  tmp= tmin (repLengthBuf1, deggSubLg + 1);
1726  _fq_nmod_vec_sub (g->coeffs + lg, g->coeffs + lg, buf1-> coeffs,
1727  tmp, fq_con);
1728  }
1729  if (lg < 0)
1730  {
1731  fq_nmod_poly_clear (buf1, fq_con);
1732  fq_nmod_poly_clear (buf2, fq_con);
1733  fq_nmod_poly_clear (buf3, fq_con);
1734  break;
1735  }
1736  if (degfSubLf >= 0)
1737  _fq_nmod_vec_sub (f->coeffs + lf, f->coeffs + lf, buf2->coeffs,
1738  repLengthBuf2, fq_con);
1739  fq_nmod_poly_clear (buf1, fq_con);
1740  fq_nmod_poly_clear (buf2, fq_con);
1741  fq_nmod_poly_clear (buf3, fq_con);
1742  }
1743 
1746 
1747  return result;
1748 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm buf1
Definition: facFqBivar.cc:71
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:92
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...
static TreeM * G
Definition: janet.cc:32
The main handler for Singular numbers which are suitable for Singular polynomials.
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm buf2
Definition: facFqBivar.cc:71
fq_nmod_poly_init(prod, fq_con)
Variable x
Definition: cfModGcd.cc:4023
mipo *int degg
Definition: facAlgExt.cc:61
return result
Definition: facAbsBiFact.cc:76
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)

◆ reverseSubstReciproQ()

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

Definition at line 1752 of file facMul.cc.

1753 {
1754  Variable y= Variable (2);
1755  Variable x= Variable (1);
1756 
1757  fmpz_poly_t f, g;
1758  fmpz_poly_init (f);
1759  fmpz_poly_init (g);
1760  fmpz_poly_set (f, F);
1761  fmpz_poly_set (g, G);
1762  int degf= fmpz_poly_degree(f);
1763  int degg= fmpz_poly_degree(g);
1764 
1765  fmpz_poly_t buf1,buf2, buf3;
1766 
1767  if (fmpz_poly_length (f) < (long) d*(k+1)) //zero padding
1768  fmpz_poly_fit_length (f,(long)d*(k+1));
1769 
1770  CanonicalForm result= 0;
1771  int i= 0;
1772  int lf= 0;
1773  int lg= d*k;
1774  int degfSubLf= degf;
1775  int deggSubLg= degg-lg;
1776  int repLengthBuf2, repLengthBuf1, ind, tmp;
1777  fmpz_t tmp1, tmp2;
1778  while (degf >= lf || lg >= 0)
1779  {
1780  if (degfSubLf >= d)
1781  repLengthBuf1= d;
1782  else if (degfSubLf < 0)
1783  repLengthBuf1= 0;
1784  else
1785  repLengthBuf1= degfSubLf + 1;
1786 
1787  fmpz_poly_init2 (buf1, repLengthBuf1);
1788 
1789  for (ind= 0; ind < repLengthBuf1; ind++)
1790  {
1791  fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
1792  fmpz_poly_set_coeff_fmpz (buf1, ind, tmp1);
1793  }
1794  _fmpz_poly_normalise (buf1);
1795 
1796  repLengthBuf1= fmpz_poly_length (buf1);
1797 
1798  if (deggSubLg >= d - 1)
1799  repLengthBuf2= d - 1;
1800  else if (deggSubLg < 0)
1801  repLengthBuf2= 0;
1802  else
1803  repLengthBuf2= deggSubLg + 1;
1804 
1805  fmpz_poly_init2 (buf2, repLengthBuf2);
1806 
1807  for (ind= 0; ind < repLengthBuf2; ind++)
1808  {
1809  fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1810  fmpz_poly_set_coeff_fmpz (buf2, ind, tmp1);
1811  }
1812 
1813  _fmpz_poly_normalise (buf2);
1814  repLengthBuf2= fmpz_poly_length (buf2);
1815 
1816  fmpz_poly_init2 (buf3, repLengthBuf2 + d);
1817  for (ind= 0; ind < repLengthBuf1; ind++)
1818  {
1819  fmpz_poly_get_coeff_fmpz (tmp1, buf1, ind);
1820  fmpz_poly_set_coeff_fmpz (buf3, ind, tmp1);
1821  }
1822  for (ind= repLengthBuf1; ind < d; ind++)
1823  fmpz_poly_set_coeff_ui (buf3, ind, 0);
1824  for (ind= 0; ind < repLengthBuf2; ind++)
1825  {
1826  fmpz_poly_get_coeff_fmpz (tmp1, buf2, ind);
1827  fmpz_poly_set_coeff_fmpz (buf3, ind + d, tmp1);
1828  }
1829  _fmpz_poly_normalise (buf3);
1830 
1831  result += convertFmpz_poly_t2FacCF (buf3, x)*power (y, i);
1832  i++;
1833 
1834 
1835  lf= i*d;
1836  degfSubLf= degf - lf;
1837 
1838  lg= d*(k-i);
1839  deggSubLg= degg - lg;
1840 
1841  if (lg >= 0 && deggSubLg > 0)
1842  {
1843  if (repLengthBuf2 > degfSubLf + 1)
1844  degfSubLf= repLengthBuf2 - 1;
1845  tmp= tmin (repLengthBuf1, deggSubLg + 1);
1846  for (ind= 0; ind < tmp; ind++)
1847  {
1848  fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1849  fmpz_poly_get_coeff_fmpz (tmp2, buf1, ind);
1850  fmpz_sub (tmp1, tmp1, tmp2);
1851  fmpz_poly_set_coeff_fmpz (g, ind + lg, tmp1);
1852  }
1853  }
1854  if (lg < 0)
1855  {
1856  fmpz_poly_clear (buf1);
1857  fmpz_poly_clear (buf2);
1858  fmpz_poly_clear (buf3);
1859  break;
1860  }
1861  if (degfSubLf >= 0)
1862  {
1863  for (ind= 0; ind < repLengthBuf2; ind++)
1864  {
1865  fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
1866  fmpz_poly_get_coeff_fmpz (tmp2, buf2, ind);
1867  fmpz_sub (tmp1, tmp1, tmp2);
1868  fmpz_poly_set_coeff_fmpz (f, ind + lf, tmp1);
1869  }
1870  }
1871  fmpz_poly_clear (buf1);
1872  fmpz_poly_clear (buf2);
1873  fmpz_poly_clear (buf3);
1874  }
1875 
1876  fmpz_poly_clear (f);
1877  fmpz_poly_clear (g);
1878  fmpz_clear (tmp1);
1879  fmpz_clear (tmp2);
1880 
1881  return result;
1882 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm buf1
Definition: facFqBivar.cc:71
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:92
static TreeM * G
Definition: janet.cc:32
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm buf2
Definition: facFqBivar.cc:71
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
CFList tmp1
Definition: facFqBivar.cc:70
Variable x
Definition: cfModGcd.cc:4023
mipo *int degg
Definition: facAlgExt.cc:61
return result
Definition: facAbsBiFact.cc:76
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)

◆ split()

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

Definition at line 3336 of file facMul.cc.

3337 {
3338  CanonicalForm A= F;
3339  CanonicalForm buf= 0;
3340  bool swap= false;
3341  if (degree (A, x) <= 0)
3342  return CFList(A);
3343  else if (x.level() != A.level())
3344  {
3345  swap= true;
3346  A= swapvar (A, x, A.mvar());
3347  }
3348 
3349  int j= (int) floor ((double) degree (A)/ m);
3350  CFList result;
3351  CFIterator i= A;
3352  for (; j >= 0; j--)
3353  {
3354  while (i.hasTerms() && i.exp() - j*m >= 0)
3355  {
3356  if (swap)
3357  buf += i.coeff()*power (A.mvar(), i.exp() - j*m);
3358  else
3359  buf += i.coeff()*power (x, i.exp() - j*m);
3360  i++;
3361  }
3362  if (swap)
3363  result.append (swapvar (buf, x, F.mvar()));
3364  else
3365  result.append (buf);
3366  buf= 0;
3367  }
3368  return result;
3369 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
int j
Definition: facHensel.cc:105
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:77
const signed long floor(const ampf< Precision > &x)
Definition: amp.h:774
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:134
#define A
Definition: sirandom.c:23
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
#define swap(_i, _j)
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

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

3627 {
3628  if (B.isZero())
3629  return true;
3630  if (A.isZero())
3631  return false;
3633  return fdivides (A, B);
3634  int p= getCharacteristic();
3635  if (A.inCoeffDomain() || B.inCoeffDomain())
3636  {
3637  if (A.inCoeffDomain())
3638  return true;
3639  else
3640  return false;
3641  }
3642  if (p > 0)
3643  {
3644  if (fac_NTL_char != p)
3645  {
3646  fac_NTL_char= p;
3647  zz_p::init (p);
3648  }
3649  Variable alpha;
3650  if (hasFirstAlgVar (A, alpha) || hasFirstAlgVar (B, alpha))
3651  {
3652 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3653  nmod_poly_t FLINTmipo;
3654  fq_nmod_ctx_t fq_con;
3655 
3656  nmod_poly_init (FLINTmipo, getCharacteristic());
3657  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
3658 
3659  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3660 
3661  fq_nmod_poly_t FLINTA, FLINTB;
3662  convertFacCF2Fq_nmod_poly_t (FLINTA, A, fq_con);
3663  convertFacCF2Fq_nmod_poly_t (FLINTB, B, fq_con);
3664  int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA, fq_con);
3665  fq_nmod_poly_clear (FLINTA, fq_con);
3666  fq_nmod_poly_clear (FLINTB, fq_con);
3667  nmod_poly_clear (FLINTmipo);
3668  fq_nmod_ctx_clear (fq_con);
3669  return result;
3670 #else
3671  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3672  zz_pE::init (NTLMipo);
3673  zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
3674  zz_pEX NTLB= convertFacCF2NTLzz_pEX (B, NTLMipo);
3675  return divide (NTLB, NTLA);
3676 #endif
3677  }
3678 #ifdef HAVE_FLINT
3679  nmod_poly_t FLINTA, FLINTB;
3680  convertFacCF2nmod_poly_t (FLINTA, A);
3681  convertFacCF2nmod_poly_t (FLINTB, B);
3682  nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3683  bool result= nmod_poly_is_zero (FLINTA);
3684  nmod_poly_clear (FLINTA);
3685  nmod_poly_clear (FLINTB);
3686  return result;
3687 #else
3688  zz_pX NTLA= convertFacCF2NTLzzpX (A);
3689  zz_pX NTLB= convertFacCF2NTLzzpX (B);
3690  return divide (NTLB, NTLA);
3691 #endif
3692  }
3693 #ifdef HAVE_FLINT
3694  Variable alpha;
3695  bool isRat= isOn (SW_RATIONAL);
3696  if (!isRat)
3697  On (SW_RATIONAL);
3698  if (!hasFirstAlgVar (A, alpha) && !hasFirstAlgVar (B, alpha))
3699  {
3700  fmpq_poly_t FLINTA,FLINTB;
3701  convertFacCF2Fmpq_poly_t (FLINTA, A);
3702  convertFacCF2Fmpq_poly_t (FLINTB, B);
3703  fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3704  bool result= fmpq_poly_is_zero (FLINTA);
3705  fmpq_poly_clear (FLINTA);
3706  fmpq_poly_clear (FLINTB);
3707  if (!isRat)
3708  Off (SW_RATIONAL);
3709  return result;
3710  }
3711  CanonicalForm Q, R;
3712  newtonDivrem (B, A, Q, R);
3713  if (!isRat)
3714  Off (SW_RATIONAL);
3715  return R.isZero();
3716 #else
3717  bool isRat= isOn (SW_RATIONAL);
3718  if (!isRat)
3719  On (SW_RATIONAL);
3720  bool result= fdivides (A, B);
3721  if (!isRat)
3722  Off (SW_RATIONAL);
3723  return result; //maybe NTL?
3724 #endif
3725 }
nmod_poly_init(FLINTmipo, getCharacteristic())
void Off(int sw)
switches
factory&#39;s class for variables
Definition: factory.h:117
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
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
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
factory&#39;s main class
Definition: canonicalform.h:77
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
Variable alpha
Definition: facAbsBiFact.cc:52
#define Q
Definition: sirandom.c:25
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
convertFacCF2nmod_poly_t(FLINTmipo, M)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
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)
Definition: facMul.cc:342
fq_nmod_poly_clear(prod, fq_con)
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
static int gettype()
Definition: cf_factory.h:28
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
#define R
Definition: sirandom.c:26
#define GaloisFieldDomain
Definition: cf_defs.h:22
long fac_NTL_char
Definition: NTLconvert.cc:41
int p
Definition: cfModGcd.cc:4019
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

◆ uniReverse()

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

Definition at line 270 of file facMul.cc.

271 {
272  if (d == 0)
273  return F;
274  if (F.inCoeffDomain())
275  return F*power (x,d);
277  CFIterator i= F;
278  while (d - i.exp() < 0)
279  i++;
280 
281  for (; i.hasTerms() && (d - i.exp() >= 0); i++)
282  result += i.coeff()*power (x, d - i.exp());
283  return result;
284 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:77
int i
Definition: cfEzgcd.cc:125
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const