My Project
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 /// multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
21 /// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
22 /// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
23 /// considered as elements over Z/p^k or Z/p^k[t]/(f).
24 ///
25 /// @return @a mulNTL returns F*G
27 mulNTL (const CanonicalForm& F, ///< [in] a univariate poly
28  const CanonicalForm& G, ///< [in] a univariate poly
29  const modpk& b= modpk() ///< [in] coeff bound
30  );
31 
32 /// mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
33 /// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
34 /// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
35 /// considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity
36 /// of Lc(G) is not checked
37 ///
38 /// @return @a modNTL returns F mod G
40 modNTL (const CanonicalForm& F, ///< [in] a univariate poly
41  const CanonicalForm& G, ///< [in] a univariate poly
42  const modpk& b= modpk() ///< [in] coeff bound
43  );
44 
45 /// division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
46 /// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
47 /// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
48 /// considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity
49 /// of Lc(G) is not checked
50 ///
51 /// @return @a divNTL returns F/G
53 divNTL (const CanonicalForm& F, ///< [in] a univariate poly
54  const CanonicalForm& G, ///< [in] a univariate poly
55  const modpk& b= modpk() ///< [in] coeff bound
56  );
57 
58 /// division with remainder of @a F by @a G wrt Variable (1) modulo @a M.
59 /// Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
60 ///
61 /// @return @a Q returns the dividend, @a R returns the remainder.
62 /// @sa divrem()
63 void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
64  const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
65  CanonicalForm& Q, ///< [in,out] dividend
66  CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) <
67  ///< degree (G, 1)
68  const CanonicalForm& M ///< [in] power of Variable (2)
69  );
70 
71 /// division with remainder of @a F by @a G wrt Variable (1) modulo @a MOD.
72 /// Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
73 ///
74 /// @sa divrem2()
76  const CanonicalForm& F, ///< [in] multivariate, compressed polynomial
77  const CanonicalForm& G, ///< [in] multivariate, compressed polynomial
78  CanonicalForm& Q, ///< [in,out] dividend
79  CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) <
80  ///< degree (G, 1)
81  const CFList& MOD ///< [in] only contains powers of
82  ///< Variables of level higher than 1
83  );
84 
85 
86 /// division with remainder of @a F by
87 /// @a G wrt Variable (1) modulo @a M using Newton inversion
88 ///
89 /// @return @a Q returns the dividend, @a R returns the remainder.
90 /// @sa divrem2(), newtonDiv()
91 void
92 newtonDivrem (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
93  const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
94  ///< which is monic in Variable (1)
95  CanonicalForm& Q, ///< [in,out] dividend
96  CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) <
97  ///< degree (G, 1)
98  const CanonicalForm& M ///< [in] power of Variable (2)
99  );
100 
101 /// division of @a F by
102 /// @a G wrt Variable (1) modulo @a M using Newton inversion
103 ///
104 /// @return @a newtonDiv returns the dividend
105 /// @sa divrem2(), newtonDivrem()
107 newtonDiv (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
108  const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
109  ///< which is monic in Variable (1)
110  const CanonicalForm& M ///< [in] power of Variable (2)
111  );
112 
113 /// divisibility test for univariate polys
114 ///
115 /// @return @a uniFdivides returns true if A divides B
116 bool
117 uniFdivides (const CanonicalForm& A, ///< [in] univariate poly
118  const CanonicalForm& B ///< [in] univariate poly
119  );
120 
121 /// Karatsuba style modular multiplication for bivariate polynomials.
122 ///
123 /// @return @a mulMod2 returns @a A * @a B mod @a M.
125 mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial
126  const CanonicalForm& B, ///< [in] bivariate, compressed polynomial
127  const CanonicalForm& M ///< [in] power of Variable (2)
128  );
129 
130 /// Karatsuba style modular multiplication for multivariate polynomials.
131 ///
132 /// @return @a mulMod2 returns @a A * @a B mod @a MOD.
134 mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial
135  const CanonicalForm& B, ///< [in] multivariate, compressed polynomial
136  const CFList& MOD ///< [in] only contains powers of
137  ///< Variables of level higher than 1
138  );
139 
140 /// reduce @a F modulo elements in @a M.
141 ///
142 /// @return @a mod returns @a F modulo @a M
143 CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial
144  const CFList& M ///< [in] list containing only
145  ///< univariate polynomials
146  );
147 
148 /// product of all elements in @a L modulo @a M via divide-and-conquer.
149 ///
150 /// @return @a prodMod returns product of all elements in @a L modulo @a M.
152 prodMod (const CFList& L, ///< [in] contains only bivariate, compressed
153  ///< polynomials
154  const CanonicalForm& M ///< [in] power of Variable (2)
155  );
156 
157 /// product of all elements in @a L modulo @a M via divide-and-conquer.
158 ///
159 /// @return @a prodMod returns product of all elements in @a L modulo @a M.
161 prodMod (const CFList& L, ///< [in] contains multivariate, compressed
162  ///< polynomials
163  const CFList& M ///< [in] contains only powers of Variables
164  );
165 
166 #ifdef HAVE_FLINT
167 /// division with remainder of univariate polynomials over Q and Q(a) using
168 /// Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)
169 void
170 newtonDivrem (const CanonicalForm& F, ///<[in] univariate poly
171  const CanonicalForm& G, ///<[in] univariate poly
172  CanonicalForm& Q, ///<[in, out] quotient
173  CanonicalForm& R ///<[in, out] remainder
174  );
175 #endif
176 
177 #endif
178 /* FAC_MUL_H */
179 
Header for factory's main class CanonicalForm.
CanonicalForm b
Definition: cfModGcd.cc:4105
factory's main class
Definition: canonicalform.h:86
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
return modpk(p, k)
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:3072
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:731
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition: facMul.cc:3759
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),...
Definition: facMul.cc:411
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2986
void FACTORY_PUBLIC divrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &MOD)
division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel,...
Definition: facMul.cc:3716
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:3080
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:3392
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:3649
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3180
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:3313
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,...
Definition: facMul.cc:936
operations mod p^k and some other useful functions for factorization
#define FACTORY_PUBLIC
Definition: globaldefs.h:25
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR jList * Q
Definition: janet.cc:30
#define R
Definition: sirandom.c:27
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25