facMul.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facMul.h
5  *
6  * This file defines functions for fast multiplication and division with
7  * remainder
8  *
9  * @author Martin Lee
10  *
11  **/
12 /*****************************************************************************/
13 
14 #ifndef FAC_MUL_H
15 #define FAC_MUL_H
16 
17 #include "canonicalform.h"
18 #include "fac_util.h"
19 
20 #ifdef HAVE_NTL
21 /// multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
22 /// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
23 /// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
24 /// considered as elements over Z/p^k or Z/p^k[t]/(f).
25 ///
26 /// @return @a mulNTL returns F*G
28 mulNTL (const CanonicalForm& F, ///< [in] a univariate poly
29  const CanonicalForm& G, ///< [in] a univariate poly
30  const modpk& b= modpk() ///< [in] coeff bound
31  );
32 
33 /// mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
34 /// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
35 /// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
36 /// considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity
37 /// of Lc(G) is not checked
38 ///
39 /// @return @a modNTL returns F mod G
41 modNTL (const CanonicalForm& F, ///< [in] a univariate poly
42  const CanonicalForm& G, ///< [in] a univariate poly
43  const modpk& b= modpk() ///< [in] coeff bound
44  );
45 
46 /// division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
47 /// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
48 /// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
49 /// considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity
50 /// of Lc(G) is not checked
51 ///
52 /// @return @a divNTL returns F/G
54 divNTL (const CanonicalForm& F, ///< [in] a univariate poly
55  const CanonicalForm& G, ///< [in] a univariate poly
56  const modpk& b= modpk() ///< [in] coeff bound
57  );
58 
59 /// division with remainder of @a F by @a G wrt Variable (1) modulo @a M.
60 /// Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
61 ///
62 /// @return @a Q returns the dividend, @a R returns the remainder.
63 /// @sa divrem()
64 void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
65  const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
66  CanonicalForm& Q, ///< [in,out] dividend
67  CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) <
68  ///< degree (G, 1)
69  const CanonicalForm& M ///< [in] power of Variable (2)
70  );
71 
72 /// division with remainder of @a F by @a G wrt Variable (1) modulo @a MOD.
73 /// Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
74 ///
75 /// @sa divrem2()
76 void divrem (
77  const CanonicalForm& F, ///< [in] multivariate, compressed polynomial
78  const CanonicalForm& G, ///< [in] multivariate, compressed polynomial
79  CanonicalForm& Q, ///< [in,out] dividend
80  CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) <
81  ///< degree (G, 1)
82  const CFList& MOD ///< [in] only contains powers of
83  ///< Variables of level higher than 1
84  );
85 
86 
87 /// division with remainder of @a F by
88 /// @a G wrt Variable (1) modulo @a M using Newton inversion
89 ///
90 /// @return @a Q returns the dividend, @a R returns the remainder.
91 /// @sa divrem2(), newtonDiv()
92 void
93 newtonDivrem (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
94  const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
95  ///< which is monic in Variable (1)
96  CanonicalForm& Q, ///< [in,out] dividend
97  CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) <
98  ///< degree (G, 1)
99  const CanonicalForm& M ///< [in] power of Variable (2)
100  );
101 
102 /// division of @a F by
103 /// @a G wrt Variable (1) modulo @a M using Newton inversion
104 ///
105 /// @return @a newtonDiv returns the dividend
106 /// @sa divrem2(), newtonDivrem()
108 newtonDiv (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
109  const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
110  ///< which is monic in Variable (1)
111  const CanonicalForm& M ///< [in] power of Variable (2)
112  );
113 
114 /// divisibility test for univariate polys
115 ///
116 /// @return @a uniFdivides returns true if A divides B
117 bool
118 uniFdivides (const CanonicalForm& A, ///< [in] univariate poly
119  const CanonicalForm& B ///< [in] univariate poly
120  );
121 
122 /// Karatsuba style modular multiplication for bivariate polynomials.
123 ///
124 /// @return @a mulMod2 returns @a A * @a B mod @a M.
126 mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial
127  const CanonicalForm& B, ///< [in] bivariate, compressed polynomial
128  const CanonicalForm& M ///< [in] power of Variable (2)
129  );
130 
131 /// Karatsuba style modular multiplication for multivariate polynomials.
132 ///
133 /// @return @a mulMod2 returns @a A * @a B mod @a MOD.
135 mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial
136  const CanonicalForm& B, ///< [in] multivariate, compressed polynomial
137  const CFList& MOD ///< [in] only contains powers of
138  ///< Variables of level higher than 1
139  );
140 
141 /// reduce @a F modulo elements in @a M.
142 ///
143 /// @return @a mod returns @a F modulo @a M
144 CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial
145  const CFList& M ///< [in] list containing only
146  ///< univariate polynomials
147  );
148 
149 /// product of all elements in @a L modulo @a M via divide-and-conquer.
150 ///
151 /// @return @a prodMod returns product of all elements in @a L modulo @a M.
153 prodMod (const CFList& L, ///< [in] contains only bivariate, compressed
154  ///< polynomials
155  const CanonicalForm& M ///< [in] power of Variable (2)
156  );
157 
158 /// product of all elements in @a L modulo @a M via divide-and-conquer.
159 ///
160 /// @return @a prodMod returns product of all elements in @a L modulo @a M.
162 prodMod (const CFList& L, ///< [in] contains multivariate, compressed
163  ///< polynomials
164  const CFList& M ///< [in] contains only powers of Variables
165  );
166 
167 #ifdef HAVE_FLINT
168 /// division with remainder of univariate polynomials over Q and Q(a) using
169 /// Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)
170 void
171 newtonDivrem (const CanonicalForm& F, ///<[in] univariate poly
172  const CanonicalForm& G, ///<[in] univariate poly
173  CanonicalForm& Q, ///<[in, out] quotient
174  CanonicalForm& R ///<[in, out] remainder
175  );
176 #endif
177 #endif
178 
179 #endif
180 /* FAC_MUL_H */
181 
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition: facMul.cc:3626
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)...
Definition: facMul.cc:676
factory&#39;s main class
Definition: canonicalform.h:75
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 ...
Definition: facMul.cc:3259
#define Q
Definition: sirandom.c:25
static TreeM * G
Definition: janet.cc:38
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&#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
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
return modpk(p, k)
#define M
Definition: sirandom.c:24
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&#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); in this case invertiblity of Lc(G) is not checked
Definition: facMul.cc:850
#define A
Definition: sirandom.c:23
const ring R
Definition: DebugPrint.cc:36
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
CanonicalForm newtonDiv(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
division of F by G wrt Variable (1) modulo M using Newton inversion
Definition: facMul.cc:3180
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
b *CanonicalForm B
Definition: facBivar.cc:51
operations mod p^k and some other useful functions for factorization
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
const poly b
Definition: syzextra.cc:213
class to do operations mod p^k for int&#39;s p and k
Definition: fac_util.h:22
Header for factory&#39;s main class CanonicalForm.