[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 | |
---|
| 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 |
---|
[64c923] | 26 | const CanonicalForm& G, ///< [in] a univariate poly |
---|
| 27 | const modpk& b= modpk() ///< [in] coeff bound |
---|
[0e2e23] | 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 |
---|
[64c923] | 36 | const CanonicalForm& G, ///< [in] a univariate poly |
---|
| 37 | const modpk& b= modpk() ///< [in] coeff bound |
---|
[0e2e23] | 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 |
---|
[64c923] | 46 | const CanonicalForm& G, ///< [in] a univariate poly |
---|
| 47 | const modpk& b= modpk() ///< [in] coeff bound |
---|
[0e2e23] | 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 | |
---|
[c7c7fe4] | 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 | |
---|
[0e2e23] | 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 | |
---|