source: git/factory/facMul.h @ 86faff

spielwiese
Last change on this file since 86faff was c2aeb9, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: typo
  • Property mode set to 100644
File size: 6.0 KB
Line 
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
24CanonicalForm
25mulNTL (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
34CanonicalForm
35modNTL (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
44CanonicalForm
45divNTL (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()
55void 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()
67void 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()
83void
84newtonDivrem (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()
98CanonicalForm
99newtonDiv (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
108bool
109uniFdivides (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.
116CanonicalForm
117mulMod2 (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.
125CanonicalForm
126mulMod (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
135CanonicalForm 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.
143CanonicalForm
144prodMod (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.
152CanonicalForm
153prodMod (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
Note: See TracBrowser for help on using the repository browser.