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 over a finite field using NTL, if we are |
---|
21 | /// in GF factory's default multiplication is used. |
---|
22 | /// |
---|
23 | /// @return @a mulNTL returns F*G |
---|
24 | CanonicalForm |
---|
25 | mulNTL (const CanonicalForm& F, ///< [in] a univariate poly |
---|
26 | const CanonicalForm& G, ///< [in] a univariate poly |
---|
27 | const modpk& b= modpk() ///< [in] coeff bound |
---|
28 | ); |
---|
29 | |
---|
30 | /// mod of univariate polys over a finite field using NTL, if we are |
---|
31 | /// in GF factory's default mod is used. |
---|
32 | /// |
---|
33 | /// @return @a modNTL returns F mod G |
---|
34 | CanonicalForm |
---|
35 | modNTL (const CanonicalForm& F, ///< [in] a univariate poly |
---|
36 | const CanonicalForm& G, ///< [in] a univariate poly |
---|
37 | const modpk& b= modpk() ///< [in] coeff bound |
---|
38 | ); |
---|
39 | |
---|
40 | /// division of univariate polys over a finite field using NTL, if we are |
---|
41 | /// in GF factory's default division is used. |
---|
42 | /// |
---|
43 | /// @return @a divNTL returns F/G |
---|
44 | CanonicalForm |
---|
45 | divNTL (const CanonicalForm& F, ///< [in] a univariate poly |
---|
46 | const CanonicalForm& G, ///< [in] a univariate poly |
---|
47 | const modpk& b= modpk() ///< [in] coeff bound |
---|
48 | ); |
---|
49 | |
---|
50 | /// division with remainder of @a F by |
---|
51 | /// @a G wrt Variable (1) modulo @a M. |
---|
52 | /// |
---|
53 | /// @return @a Q returns the dividend, @a R returns the remainder. |
---|
54 | /// @sa divrem() |
---|
55 | void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial |
---|
56 | const CanonicalForm& G, ///< [in] bivariate, compressed polynomial |
---|
57 | CanonicalForm& Q, ///< [in,out] dividend |
---|
58 | CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < |
---|
59 | ///< degree (G, 1) |
---|
60 | const CanonicalForm& M ///< [in] power of Variable (2) |
---|
61 | ); |
---|
62 | |
---|
63 | /// division with remainder of @a F by |
---|
64 | /// @a G wrt Variable (1) modulo @a MOD. |
---|
65 | /// |
---|
66 | /// @sa divrem2() |
---|
67 | void divrem ( |
---|
68 | const CanonicalForm& F, ///< [in] multivariate, compressed polynomial |
---|
69 | const CanonicalForm& G, ///< [in] multivariate, compressed polynomial |
---|
70 | CanonicalForm& Q, ///< [in,out] dividend |
---|
71 | CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < |
---|
72 | ///< degree (G, 1) |
---|
73 | const CFList& MOD ///< [in] only contains powers of |
---|
74 | ///< Variables of level higher than 1 |
---|
75 | ); |
---|
76 | |
---|
77 | |
---|
78 | /// division with remainder of @a F by |
---|
79 | /// @a G wrt Variable (1) modulo @a M using Newton inversion |
---|
80 | /// |
---|
81 | /// @return @a Q returns the dividend, @a R returns the remainder. |
---|
82 | /// @sa divrem2(), newtonDiv() |
---|
83 | void |
---|
84 | newtonDivrem (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial |
---|
85 | const CanonicalForm& G, ///< [in] bivariate, compressed polynomial |
---|
86 | ///< which is monic in Variable (1) |
---|
87 | CanonicalForm& Q, ///< [in,out] dividend |
---|
88 | CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < |
---|
89 | ///< degree (G, 1) |
---|
90 | const CanonicalForm& M ///< [in] power of Variable (2) |
---|
91 | ); |
---|
92 | |
---|
93 | /// division of @a F by |
---|
94 | /// @a G wrt Variable (1) modulo @a M using Newton inversion |
---|
95 | /// |
---|
96 | /// @return @a newtonDiv returns the dividend |
---|
97 | /// @sa divrem2(), newtonDivrem() |
---|
98 | CanonicalForm |
---|
99 | newtonDiv (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial |
---|
100 | const CanonicalForm& G, ///< [in] bivariate, compressed polynomial |
---|
101 | ///< which is monic in Variable (1) |
---|
102 | const CanonicalForm& M ///< [in] power of Variable (2) |
---|
103 | ); |
---|
104 | |
---|
105 | /// divisibility test for univariate polys |
---|
106 | /// |
---|
107 | /// @return @a uniFdivides returns true if A divides B |
---|
108 | bool |
---|
109 | uniFdivides (const CanonicalForm& A, ///< [in] univariate poly |
---|
110 | const CanonicalForm& B ///< [in] univariate poly |
---|
111 | ); |
---|
112 | |
---|
113 | /// Karatsuba style modular multiplication for bivariate polynomials. |
---|
114 | /// |
---|
115 | /// @return @a mulMod2 returns @a A * @a B mod @a M. |
---|
116 | CanonicalForm |
---|
117 | mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial |
---|
118 | const CanonicalForm& B, ///< [in] bivariate, compressed polynomial |
---|
119 | const CanonicalForm& M ///< [in] power of Variable (2) |
---|
120 | ); |
---|
121 | |
---|
122 | /// Karatsuba style modular multiplication for multivariate polynomials. |
---|
123 | /// |
---|
124 | /// @return @a mulMod2 returns @a A * @a B mod @a MOD. |
---|
125 | CanonicalForm |
---|
126 | mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial |
---|
127 | const CanonicalForm& B, ///< [in] multivariate, compressed polynomial |
---|
128 | const CFList& MOD ///< [in] only contains powers of |
---|
129 | ///< Variables of level higher than 1 |
---|
130 | ); |
---|
131 | |
---|
132 | /// reduce @a F modulo elements in @a M. |
---|
133 | /// |
---|
134 | /// @return @a mod returns @a F modulo @a M |
---|
135 | CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial |
---|
136 | const CFList& M ///< [in] list containing only |
---|
137 | ///< univariate polynomials |
---|
138 | ); |
---|
139 | |
---|
140 | /// product of all elements in @a L modulo @a M via divide-and-conquer. |
---|
141 | /// |
---|
142 | /// @return @a prodMod returns product of all elements in @a L modulo @a M. |
---|
143 | CanonicalForm |
---|
144 | prodMod (const CFList& L, ///< [in] contains only bivariate, compressed |
---|
145 | ///< polynomials |
---|
146 | const CanonicalForm& M ///< [in] power of Variable (2) |
---|
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. |
---|
152 | CanonicalForm |
---|
153 | prodMod (const CFList& L, ///< [in] contains multivariate, compressed |
---|
154 | ///< polynomials |
---|
155 | const CFList& M ///< [in] contains only powers of Variables |
---|
156 | ); |
---|
157 | #endif |
---|
158 | /* FAC_MUL_H */ |
---|
159 | |
---|