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 |
---|
26 | CanonicalForm |
---|
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 |
---|
39 | CanonicalForm |
---|
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 |
---|
52 | CanonicalForm |
---|
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() |
---|
75 | void FACTORY_PUBLIC divrem ( |
---|
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() |
---|
106 | CanonicalForm |
---|
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. |
---|
124 | CanonicalForm |
---|
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. |
---|
133 | CanonicalForm |
---|
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. |
---|
151 | CanonicalForm |
---|
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. |
---|
160 | CanonicalForm |
---|
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 | |
---|