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