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