00001 #ifndef CRYPTOPP_POLYNOMI_H
00002 #define CRYPTOPP_POLYNOMI_H
00003
00004
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
00016
00017 template <class T> class PolynomialOver
00018 {
00019 public:
00020
00021
00022
00023 class DivideByZero : public Exception
00024 {
00025 public:
00026 DivideByZero() : Exception(OTHER_ERROR, "PolynomialOver<T>: division by zero") {}
00027 };
00028
00029
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
00047
00048
00049 PolynomialOver() {}
00050
00051
00052 PolynomialOver(const Ring &ring, unsigned int count)
00053 : m_coefficients((size_t)count, ring.Identity()) {}
00054
00055
00056 PolynomialOver(const PolynomialOver<Ring> &t)
00057 : m_coefficients(t.m_coefficients.size()) {*this = t;}
00058
00059
00060 PolynomialOver(const CoefficientType &element)
00061 : m_coefficients(1, element) {}
00062
00063
00064 template <typename Iterator> PolynomialOver(Iterator begin, Iterator end)
00065 : m_coefficients(begin, end) {}
00066
00067
00068 PolynomialOver(const char *str, const Ring &ring) {FromStr(str, ring);}
00069
00070
00071 PolynomialOver(const byte *encodedPolynomialOver, unsigned int byteCount);
00072
00073
00074 explicit PolynomialOver(const byte *BEREncodedPolynomialOver);
00075
00076
00077 explicit PolynomialOver(BufferedTransformation &bt);
00078
00079
00080 PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter ¶meter, const Ring &ring)
00081 {Randomize(rng, parameter, ring);}
00082
00083
00084
00085
00086
00087 int Degree(const Ring &ring) const {return int(CoefficientCount(ring))-1;}
00088
00089 unsigned int CoefficientCount(const Ring &ring) const;
00090
00091 CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const;
00092
00093
00094
00095
00096
00097 PolynomialOver<Ring>& operator=(const PolynomialOver<Ring>& t);
00098
00099
00100 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter ¶meter, const Ring &ring);
00101
00102
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
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
00142 static void Divide(PolynomialOver<Ring> &r, PolynomialOver<Ring> &q, const PolynomialOver<Ring> &a, const PolynomialOver<Ring> &d, const Ring &ring);
00143
00144
00145
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
00158
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
00171
00172
00173 PolynomialOverFixedRing(unsigned int count = 0) : B(fixedRing, count) {}
00174
00175
00176 PolynomialOverFixedRing(const ThisType &t) : B(t) {}
00177
00178 explicit PolynomialOverFixedRing(const B &t) : B(t) {}
00179
00180
00181 PolynomialOverFixedRing(const CoefficientType &element) : B(element) {}
00182
00183
00184 template <typename Iterator> PolynomialOverFixedRing(Iterator first, Iterator last)
00185 : B(first, last) {}
00186
00187
00188 explicit PolynomialOverFixedRing(const char *str) : B(str, fixedRing) {}
00189
00190
00191 PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount) : B(encodedPoly, byteCount) {}
00192
00193
00194 explicit PolynomialOverFixedRing(const byte *BEREncodedPoly) : B(BEREncodedPoly) {}
00195
00196
00197 explicit PolynomialOverFixedRing(BufferedTransformation &bt) : B(bt) {}
00198
00199
00200 PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter ¶meter) : B(rng, parameter, fixedRing) {}
00201
00202 static const ThisType &Zero();
00203 static const ThisType &One();
00204
00205
00206
00207
00208
00209 int Degree() const {return B::Degree(fixedRing);}
00210
00211 unsigned int CoefficientCount() const {return B::CoefficientCount(fixedRing);}
00212
00213 CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, fixedRing);}
00214
00215 CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, fixedRing);}
00216
00217
00218
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
00239 void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, fixedRing);}
00240
00241
00242 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter ¶meter) {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
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
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
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
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
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
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 ¶meter)
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
00372 CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
00373
00374
00375
00376
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