Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

polynomi.h

Go to the documentation of this file.
00001 #ifndef CRYPTOPP_POLYNOMI_H 00002 #define CRYPTOPP_POLYNOMI_H 00003 00004 /*! \file */ 00005 00006 #include "cryptlib.h" 00007 #include "misc.h" 00008 #include "algebra.h" 00009 00010 #include <iosfwd> 00011 #include <vector> 00012 00013 NAMESPACE_BEGIN(CryptoPP) 00014 00015 //! represents single-variable polynomials over arbitrary rings 00016 /*! \nosubgrouping */ 00017 template <class T> class PolynomialOver 00018 { 00019 public: 00020 //! \name ENUMS, EXCEPTIONS, and TYPEDEFS 00021 //@{ 00022 //! division by zero exception 00023 class DivideByZero : public Exception 00024 { 00025 public: 00026 DivideByZero() : Exception(OTHER_ERROR, "PolynomialOver<T>: division by zero") {} 00027 }; 00028 00029 //! specify the distribution for randomization functions 00030 class RandomizationParameter 00031 { 00032 public: 00033 RandomizationParameter(unsigned int coefficientCount, const typename T::RandomizationParameter &coefficientParameter ) 00034 : m_coefficientCount(coefficientCount), m_coefficientParameter(coefficientParameter) {} 00035 00036 private: 00037 unsigned int m_coefficientCount; 00038 typename T::RandomizationParameter m_coefficientParameter; 00039 friend class PolynomialOver<T>; 00040 }; 00041 00042 typedef T Ring; 00043 typedef typename T::Element CoefficientType; 00044 //@} 00045 00046 //! \name CREATORS 00047 //@{ 00048 //! creates the zero polynomial 00049 PolynomialOver() {} 00050 00051 //! 00052 PolynomialOver(const Ring &ring, unsigned int count) 00053 : m_coefficients((size_t)count, ring.Identity()) {} 00054 00055 //! copy constructor 00056 PolynomialOver(const PolynomialOver<Ring> &t) 00057 : m_coefficients(t.m_coefficients.size()) {*this = t;} 00058 00059 //! construct constant polynomial 00060 PolynomialOver(const CoefficientType &element) 00061 : m_coefficients(1, element) {} 00062 00063 //! construct polynomial with specified coefficients, starting from coefficient of x^0 00064 template <typename Iterator> PolynomialOver(Iterator begin, Iterator end) 00065 : m_coefficients(begin, end) {} 00066 00067 //! convert from string 00068 PolynomialOver(const char *str, const Ring &ring) {FromStr(str, ring);} 00069 00070 //! convert from big-endian byte array 00071 PolynomialOver(const byte *encodedPolynomialOver, unsigned int byteCount); 00072 00073 //! convert from Basic Encoding Rules encoded byte array 00074 explicit PolynomialOver(const byte *BEREncodedPolynomialOver); 00075 00076 //! convert from BER encoded byte array stored in a BufferedTransformation object 00077 explicit PolynomialOver(BufferedTransformation &bt); 00078 00079 //! create a random PolynomialOver<T> 00080 PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring) 00081 {Randomize(rng, parameter, ring);} 00082 //@} 00083 00084 //! \name ACCESSORS 00085 //@{ 00086 //! the zero polynomial will return a degree of -1 00087 int Degree(const Ring &ring) const {return int(CoefficientCount(ring))-1;} 00088 //! 00089 unsigned int CoefficientCount(const Ring &ring) const; 00090 //! return coefficient for x^i 00091 CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const; 00092 //@} 00093 00094 //! \name MANIPULATORS 00095 //@{ 00096 //! 00097 PolynomialOver<Ring>& operator=(const PolynomialOver<Ring>& t); 00098 00099 //! 00100 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring); 00101 00102 //! set the coefficient for x^i to value 00103 void SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring); 00104 00105 //! 00106 void Negate(const Ring &ring); 00107 00108 //! 00109 void swap(PolynomialOver<Ring> &t); 00110 //@} 00111 00112 00113 //! \name BASIC ARITHMETIC ON POLYNOMIALS 00114 //@{ 00115 bool Equals(const PolynomialOver<Ring> &t, const Ring &ring) const; 00116 bool IsZero(const Ring &ring) const {return CoefficientCount(ring)==0;} 00117 00118 PolynomialOver<Ring> Plus(const PolynomialOver<Ring>& t, const Ring &ring) const; 00119 PolynomialOver<Ring> Minus(const PolynomialOver<Ring>& t, const Ring &ring) const; 00120 PolynomialOver<Ring> Inverse(const Ring &ring) const; 00121 00122 PolynomialOver<Ring> Times(const PolynomialOver<Ring>& t, const Ring &ring) const; 00123 PolynomialOver<Ring> DividedBy(const PolynomialOver<Ring>& t, const Ring &ring) const; 00124 PolynomialOver<Ring> Modulo(const PolynomialOver<Ring>& t, const Ring &ring) const; 00125 PolynomialOver<Ring> MultiplicativeInverse(const Ring &ring) const; 00126 bool IsUnit(const Ring &ring) const; 00127 00128 PolynomialOver<Ring>& Accumulate(const PolynomialOver<Ring>& t, const Ring &ring); 00129 PolynomialOver<Ring>& Reduce(const PolynomialOver<Ring>& t, const Ring &ring); 00130 00131 //! 00132 PolynomialOver<Ring> Doubled(const Ring &ring) const {return Plus(*this, ring);} 00133 //! 00134 PolynomialOver<Ring> Squared(const Ring &ring) const {return Times(*this, ring);} 00135 00136 CoefficientType EvaluateAt(const CoefficientType &x, const Ring &ring) const; 00137 00138 PolynomialOver<Ring>& ShiftLeft(unsigned int n, const Ring &ring); 00139 PolynomialOver<Ring>& ShiftRight(unsigned int n, const Ring &ring); 00140 00141 //! calculate r and q such that (a == d*q + r) && (0 <= degree of r < degree of d) 00142 static void Divide(PolynomialOver<Ring> &r, PolynomialOver<Ring> &q, const PolynomialOver<Ring> &a, const PolynomialOver<Ring> &d, const Ring &ring); 00143 //@} 00144 00145 //! \name INPUT/OUTPUT 00146 //@{ 00147 std::istream& Input(std::istream &in, const Ring &ring); 00148 std::ostream& Output(std::ostream &out, const Ring &ring) const; 00149 //@} 00150 00151 private: 00152 void FromStr(const char *str, const Ring &ring); 00153 00154 std::vector<CoefficientType> m_coefficients; 00155 }; 00156 00157 //! Polynomials over a fixed ring 00158 /*! Having a fixed ring allows overloaded operators */ 00159 template <class T, int instance> class PolynomialOverFixedRing : private PolynomialOver<T> 00160 { 00161 typedef PolynomialOver<T> B; 00162 typedef PolynomialOverFixedRing<T, instance> ThisType; 00163 00164 public: 00165 typedef T Ring; 00166 typedef typename T::Element CoefficientType; 00167 typedef typename B::DivideByZero DivideByZero; 00168 typedef typename B::RandomizationParameter RandomizationParameter; 00169 00170 //! \name CREATORS 00171 //@{ 00172 //! creates the zero polynomial 00173 PolynomialOverFixedRing(unsigned int count = 0) : B(fixedRing, count) {} 00174 00175 //! copy constructor 00176 PolynomialOverFixedRing(const ThisType &t) : B(t) {} 00177 00178 explicit PolynomialOverFixedRing(const B &t) : B(t) {} 00179 00180 //! construct constant polynomial 00181 PolynomialOverFixedRing(const CoefficientType &element) : B(element) {} 00182 00183 //! construct polynomial with specified coefficients, starting from coefficient of x^0 00184 template <typename Iterator> PolynomialOverFixedRing(Iterator first, Iterator last) 00185 : B(first, last) {} 00186 00187 //! convert from string 00188 explicit PolynomialOverFixedRing(const char *str) : B(str, fixedRing) {} 00189 00190 //! convert from big-endian byte array 00191 PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount) : B(encodedPoly, byteCount) {} 00192 00193 //! convert from Basic Encoding Rules encoded byte array 00194 explicit PolynomialOverFixedRing(const byte *BEREncodedPoly) : B(BEREncodedPoly) {} 00195 00196 //! convert from BER encoded byte array stored in a BufferedTransformation object 00197 explicit PolynomialOverFixedRing(BufferedTransformation &bt) : B(bt) {} 00198 00199 //! create a random PolynomialOverFixedRing 00200 PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter &parameter) : B(rng, parameter, fixedRing) {} 00201 00202 static const ThisType &Zero(); 00203 static const ThisType &One(); 00204 //@} 00205 00206 //! \name ACCESSORS 00207 //@{ 00208 //! the zero polynomial will return a degree of -1 00209 int Degree() const {return B::Degree(fixedRing);} 00210 //! degree + 1 00211 unsigned int CoefficientCount() const {return B::CoefficientCount(fixedRing);} 00212 //! return coefficient for x^i 00213 CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, fixedRing);} 00214 //! return coefficient for x^i 00215 CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, fixedRing);} 00216 //@} 00217 00218 //! \name MANIPULATORS 00219 //@{ 00220 //! 00221 ThisType& operator=(const ThisType& t) {B::operator=(t); return *this;} 00222 //! 00223 ThisType& operator+=(const ThisType& t) {Accumulate(t, fixedRing); return *this;} 00224 //! 00225 ThisType& operator-=(const ThisType& t) {Reduce(t, fixedRing); return *this;} 00226 //! 00227 ThisType& operator*=(const ThisType& t) {return *this = *this*t;} 00228 //! 00229 ThisType& operator/=(const ThisType& t) {return *this = *this/t;} 00230 //! 00231 ThisType& operator%=(const ThisType& t) {return *this = *this%t;} 00232 00233 //! 00234 ThisType& operator<<=(unsigned int n) {ShiftLeft(n, fixedRing); return *this;} 00235 //! 00236 ThisType& operator>>=(unsigned int n) {ShiftRight(n, fixedRing); return *this;} 00237 00238 //! set the coefficient for x^i to value 00239 void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, fixedRing);} 00240 00241 //! 00242 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter) {B::Randomize(rng, parameter, fixedRing);} 00243 00244 //! 00245 void Negate() {B::Negate(fixedRing);} 00246 00247 void swap(ThisType &t) {B::swap(t);} 00248 //@} 00249 00250 //! \name UNARY OPERATORS 00251 //@{ 00252 //! 00253 bool operator!() const {return CoefficientCount()==0;} 00254 //! 00255 ThisType operator+() const {return *this;} 00256 //! 00257 ThisType operator-() const {return ThisType(Inverse(fixedRing));} 00258 //@} 00259 00260 //! \name BINARY OPERATORS 00261 //@{ 00262 //! 00263 friend ThisType operator>>(ThisType a, unsigned int n) {return ThisType(a>>=n);} 00264 //! 00265 friend ThisType operator<<(ThisType a, unsigned int n) {return ThisType(a<<=n);} 00266 //@} 00267 00268 //! \name OTHER ARITHMETIC FUNCTIONS 00269 //@{ 00270 //! 00271 ThisType MultiplicativeInverse() const {return ThisType(B::MultiplicativeInverse(fixedRing));} 00272 //! 00273 bool IsUnit() const {return B::IsUnit(fixedRing);} 00274 00275 //! 00276 ThisType Doubled() const {return ThisType(B::Doubled(fixedRing));} 00277 //! 00278 ThisType Squared() const {return ThisType(B::Squared(fixedRing));} 00279 00280 CoefficientType EvaluateAt(const CoefficientType &x) const {return B::EvaluateAt(x, fixedRing);} 00281 00282 //! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d)) 00283 static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d) 00284 {B::Divide(r, q, a, d, fixedRing);} 00285 //@} 00286 00287 //! \name INPUT/OUTPUT 00288 //@{ 00289 //! 00290 friend std::istream& operator>>(std::istream& in, ThisType &a) 00291 {return a.Input(in, fixedRing);} 00292 //! 00293 friend std::ostream& operator<<(std::ostream& out, const ThisType &a) 00294 {return a.Output(out, fixedRing);} 00295 //@} 00296 00297 private: 00298 static const Ring fixedRing; 00299 }; 00300 00301 //! Ring of polynomials over another ring 00302 template <class T> class RingOfPolynomialsOver : public AbstractEuclideanDomain<PolynomialOver<T> > 00303 { 00304 public: 00305 typedef T CoefficientRing; 00306 typedef PolynomialOver<T> Element; 00307 typedef typename Element::CoefficientType CoefficientType; 00308 typedef typename Element::RandomizationParameter RandomizationParameter; 00309 00310 RingOfPolynomialsOver(const CoefficientRing &ring) : m_ring(ring) {} 00311 00312 Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter &parameter) 00313 {return Element(rng, parameter, m_ring);} 00314 00315 bool Equal(const Element &a, const Element &b) const 00316 {return a.Equals(b, m_ring);} 00317 00318 const Element& Identity() const 00319 {return result = m_ring.Identity();} 00320 00321 const Element& Add(const Element &a, const Element &b) const 00322 {return result = a.Plus(b, m_ring);} 00323 00324 Element& Accumulate(Element &a, const Element &b) const 00325 {a.Accumulate(b, m_ring); return a;} 00326 00327 const Element& Inverse(const Element &a) const 00328 {return result = a.Inverse(m_ring);} 00329 00330 const Element& Subtract(const Element &a, const Element &b) const 00331 {return result = a.Minus(b, m_ring);} 00332 00333 Element& Reduce(Element &a, const Element &b) const 00334 {return a.Reduce(b, m_ring);} 00335 00336 const Element& Double(const Element &a) const 00337 {return result = a.Doubled(m_ring);} 00338 00339 const Element& MultiplicativeIdentity() const 00340 {return result = m_ring.MultiplicativeIdentity();} 00341 00342 const Element& Multiply(const Element &a, const Element &b) const 00343 {return result = a.Times(b, m_ring);} 00344 00345 const Element& Square(const Element &a) const 00346 {return result = a.Squared(m_ring);} 00347 00348 bool IsUnit(const Element &a) const 00349 {return a.IsUnit(m_ring);} 00350 00351 const Element& MultiplicativeInverse(const Element &a) const 00352 {return result = a.MultiplicativeInverse(m_ring);} 00353 00354 const Element& Divide(const Element &a, const Element &b) const 00355 {return result = a.DividedBy(b, m_ring);} 00356 00357 const Element& Mod(const Element &a, const Element &b) const 00358 {return result = a.Modulo(b, m_ring);} 00359 00360 void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const 00361 {Element::Divide(r, q, a, d, m_ring);} 00362 00363 class InterpolationFailed : public Exception 00364 { 00365 public: 00366 InterpolationFailed() : Exception(OTHER_ERROR, "RingOfPolynomialsOver<T>: interpolation failed") {} 00367 }; 00368 00369 Element Interpolate(const CoefficientType x[], const CoefficientType y[], unsigned int n) const; 00370 00371 // a faster version of Interpolate(x, y, n).EvaluateAt(position) 00372 CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const; 00373 /* 00374 void PrepareBulkInterpolation(CoefficientType *w, const CoefficientType x[], unsigned int n) const; 00375 void PrepareBulkInterpolationAt(CoefficientType *v, const CoefficientType &position, const CoefficientType x[], const CoefficientType w[], unsigned int n) const; 00376 CoefficientType BulkInterpolateAt(const CoefficientType y[], const CoefficientType v[], unsigned int n) const; 00377 */ 00378 protected: 00379 void CalculateAlpha(std::vector<CoefficientType> &alpha, const CoefficientType x[], const CoefficientType y[], unsigned int n) const; 00380 00381 CoefficientRing m_ring; 00382 }; 00383 00384 template <class Ring, class Element> 00385 void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n); 00386 template <class Ring, class Element> 00387 void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n); 00388 template <class Ring, class Element> 00389 Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n); 00390 00391 //! 00392 template <class T, int instance> 00393 inline bool operator==(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00394 {return a.Equals(b, fixedRing);} 00395 //! 00396 template <class T, int instance> 00397 inline bool operator!=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00398 {return !(a==b);} 00399 00400 //! 00401 template <class T, int instance> 00402 inline bool operator> (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00403 {return a.Degree() > b.Degree();} 00404 //! 00405 template <class T, int instance> 00406 inline bool operator>=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00407 {return a.Degree() >= b.Degree();} 00408 //! 00409 template <class T, int instance> 00410 inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00411 {return a.Degree() < b.Degree();} 00412 //! 00413 template <class T, int instance> 00414 inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00415 {return a.Degree() <= b.Degree();} 00416 00417 //! 00418 template <class T, int instance> 00419 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00420 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, fixedRing));} 00421 //! 00422 template <class T, int instance> 00423 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00424 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, fixedRing));} 00425 //! 00426 template <class T, int instance> 00427 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator*(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00428 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Times(b, fixedRing));} 00429 //! 00430 template <class T, int instance> 00431 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00432 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, fixedRing));} 00433 //! 00434 template <class T, int instance> 00435 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 00436 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, fixedRing));} 00437 00438 NAMESPACE_END 00439 00440 NAMESPACE_BEGIN(std) 00441 template<class T> inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b) 00442 { 00443 a.swap(b); 00444 } 00445 template<class T, int i> inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b) 00446 { 00447 a.swap(b); 00448 } 00449 NAMESPACE_END 00450 00451 #endif

Generated on Fri Aug 13 09:56:54 2004 for Crypto++ by doxygen 1.3.7