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(ms_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, ms_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, ms_fixedRing) {}
00201
00202 static const ThisType &Zero();
00203 static const ThisType &One();
00204
00205
00206
00207
00208
00209 int Degree() const {return B::Degree(ms_fixedRing);}
00210
00211 unsigned int CoefficientCount() const {return B::CoefficientCount(ms_fixedRing);}
00212
00213 CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);}
00214
00215 CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, ms_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, ms_fixedRing); return *this;}
00224
00225 ThisType& operator-=(const ThisType& t) {Reduce(t, ms_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, ms_fixedRing); return *this;}
00235
00236 ThisType& operator>>=(unsigned int n) {ShiftRight(n, ms_fixedRing); return *this;}
00237
00238
00239 void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, ms_fixedRing);}
00240
00241
00242 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter ¶meter) {B::Randomize(rng, parameter, ms_fixedRing);}
00243
00244
00245 void Negate() {B::Negate(ms_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(ms_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(ms_fixedRing));}
00272
00273 bool IsUnit() const {return B::IsUnit(ms_fixedRing);}
00274
00275
00276 ThisType Doubled() const {return ThisType(B::Doubled(ms_fixedRing));}
00277
00278 ThisType Squared() const {return ThisType(B::Squared(ms_fixedRing));}
00279
00280 CoefficientType EvaluateAt(const CoefficientType &x) const {return B::EvaluateAt(x, ms_fixedRing);}
00281
00282
00283 static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d)
00284 {B::Divide(r, q, a, d, ms_fixedRing);}
00285
00286
00287
00288
00289
00290 friend std::istream& operator>>(std::istream& in, ThisType &a)
00291 {return a.Input(in, ms_fixedRing);}
00292
00293 friend std::ostream& operator<<(std::ostream& out, const ThisType &a)
00294 {return a.Output(out, ms_fixedRing);}
00295
00296
00297 private:
00298 struct NewOnePolynomial
00299 {
00300 ThisType * operator()() const
00301 {
00302 return new ThisType(ms_fixedRing.MultiplicativeIdentity());
00303 }
00304 };
00305
00306 static const Ring ms_fixedRing;
00307 };
00308
00309
00310 template <class T> class RingOfPolynomialsOver : public AbstractEuclideanDomain<PolynomialOver<T> >
00311 {
00312 public:
00313 typedef T CoefficientRing;
00314 typedef PolynomialOver<T> Element;
00315 typedef typename Element::CoefficientType CoefficientType;
00316 typedef typename Element::RandomizationParameter RandomizationParameter;
00317
00318 RingOfPolynomialsOver(const CoefficientRing &ring) : m_ring(ring) {}
00319
00320 Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter ¶meter)
00321 {return Element(rng, parameter, m_ring);}
00322
00323 bool Equal(const Element &a, const Element &b) const
00324 {return a.Equals(b, m_ring);}
00325
00326 const Element& Identity() const
00327 {return this->result = m_ring.Identity();}
00328
00329 const Element& Add(const Element &a, const Element &b) const
00330 {return this->result = a.Plus(b, m_ring);}
00331
00332 Element& Accumulate(Element &a, const Element &b) const
00333 {a.Accumulate(b, m_ring); return a;}
00334
00335 const Element& Inverse(const Element &a) const
00336 {return this->result = a.Inverse(m_ring);}
00337
00338 const Element& Subtract(const Element &a, const Element &b) const
00339 {return this->result = a.Minus(b, m_ring);}
00340
00341 Element& Reduce(Element &a, const Element &b) const
00342 {return a.Reduce(b, m_ring);}
00343
00344 const Element& Double(const Element &a) const
00345 {return this->result = a.Doubled(m_ring);}
00346
00347 const Element& MultiplicativeIdentity() const
00348 {return this->result = m_ring.MultiplicativeIdentity();}
00349
00350 const Element& Multiply(const Element &a, const Element &b) const
00351 {return this->result = a.Times(b, m_ring);}
00352
00353 const Element& Square(const Element &a) const
00354 {return this->result = a.Squared(m_ring);}
00355
00356 bool IsUnit(const Element &a) const
00357 {return a.IsUnit(m_ring);}
00358
00359 const Element& MultiplicativeInverse(const Element &a) const
00360 {return this->result = a.MultiplicativeInverse(m_ring);}
00361
00362 const Element& Divide(const Element &a, const Element &b) const
00363 {return this->result = a.DividedBy(b, m_ring);}
00364
00365 const Element& Mod(const Element &a, const Element &b) const
00366 {return this->result = a.Modulo(b, m_ring);}
00367
00368 void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
00369 {Element::Divide(r, q, a, d, m_ring);}
00370
00371 class InterpolationFailed : public Exception
00372 {
00373 public:
00374 InterpolationFailed() : Exception(OTHER_ERROR, "RingOfPolynomialsOver<T>: interpolation failed") {}
00375 };
00376
00377 Element Interpolate(const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
00378
00379
00380 CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
00381
00382
00383
00384
00385
00386 protected:
00387 void CalculateAlpha(std::vector<CoefficientType> &alpha, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
00388
00389 CoefficientRing m_ring;
00390 };
00391
00392 template <class Ring, class Element>
00393 void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n);
00394 template <class Ring, class Element>
00395 void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n);
00396 template <class Ring, class Element>
00397 Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n);
00398
00399
00400 template <class T, int instance>
00401 inline bool operator==(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00402 {return a.Equals(b, a.ms_fixedRing);}
00403
00404 template <class T, int instance>
00405 inline bool operator!=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00406 {return !(a==b);}
00407
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 template <class T, int instance>
00418 inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00419 {return a.Degree() < b.Degree();}
00420
00421 template <class T, int instance>
00422 inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00423 {return a.Degree() <= b.Degree();}
00424
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.Plus(b, a.ms_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.Minus(b, a.ms_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.Times(b, a.ms_fixedRing));}
00437
00438 template <class T, int instance>
00439 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00440 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, a.ms_fixedRing));}
00441
00442 template <class T, int instance>
00443 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00444 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, a.ms_fixedRing));}
00445
00446 NAMESPACE_END
00447
00448 NAMESPACE_BEGIN(std)
00449 template<class T> inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b)
00450 {
00451 a.swap(b);
00452 }
00453 template<class T, int i> inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
00454 {
00455 a.swap(b);
00456 }
00457 NAMESPACE_END
00458
00459 #endif