polynomi.h Source File

00001 #ifndef CRYPTOPP_POLYNOMI_H
00002 #define CRYPTOPP_POLYNOMI_H
00003 
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 
00016 
00017 template <class T> class PolynomialOver
00018 {
00019 public:
00021 
00022 
00023                 class DivideByZero : public Exception 
00024                 {
00025                 public: 
00026                         DivideByZero() : Exception("PolynomialOver<T>: division by zero") {}
00027                 };
00028 
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;
00045 
00047 
00048 
00049                 PolynomialOver() {}
00050 
00052                 PolynomialOver(const Ring &ring, unsigned int count)
00053                         : m_coefficients((size_t)count, ring.Zero()) {}
00054 
00056                 PolynomialOver(const PolynomialOver<Ring> &t)
00057                         : m_coefficients(t.m_coefficients.size()) {*this = t;}
00058 
00060                 PolynomialOver(const CoefficientType &element)
00061                         : m_coefficients(1, element) {}
00062 
00064                 template <typename Iterator> PolynomialOver(Iterator begin, Iterator end)
00065                         : m_coefficients(begin, end) {}
00066 
00068                 PolynomialOver(const char *str, const Ring &ring) {FromStr(str, ring);}
00069 
00071                 PolynomialOver(const byte *encodedPolynomialOver, unsigned int byteCount);
00072 
00074                 explicit PolynomialOver(const byte *BEREncodedPolynomialOver);
00075 
00077                 explicit PolynomialOver(BufferedTransformation &bt);
00078 
00080                 PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring)
00081                         {Randomize(rng, parameter, ring);}
00083 
00085 
00086 
00087                 int Degree(const Ring &ring) const {return int(CoefficientCount(ring))-1;}
00089                 unsigned int CoefficientCount(const Ring &ring) const;
00091                 CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const;
00093 
00095 
00096 
00097                 PolynomialOver<Ring>&  operator=(const PolynomialOver<Ring>& t);
00098 
00100                 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring);
00101 
00103                 void SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring);
00104 
00106                 void Negate(const Ring &ring);
00107 
00109                 void swap(PolynomialOver<Ring> &t);
00111 
00112 
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 
00132                 PolynomialOver<Ring> Doubled(const Ring &ring) const {return Plus(*this, ring);}
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 
00142                 static void Divide(PolynomialOver<Ring> &r, PolynomialOver<Ring> &q, const PolynomialOver<Ring> &a, const PolynomialOver<Ring> &d, const Ring &ring);
00144 
00146 
00147                 std::istream& Input(std::istream &in, const Ring &ring);
00148                 std::ostream& Output(std::ostream &out, const Ring &ring) const;
00150 
00151 private:
00152         void FromStr(const char *str, const Ring &ring);
00153 
00154         std::vector<CoefficientType> m_coefficients;
00155 };
00156 
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 B::DivideByZero DivideByZero;
00168         typedef B::RandomizationParameter RandomizationParameter;
00169 
00171 
00172 
00173                 PolynomialOverFixedRing(unsigned int count = 0) : B(fixedRing, count) {}
00174 
00176                 PolynomialOverFixedRing(const ThisType &t) : B(t) {}
00177 
00178                 explicit PolynomialOverFixedRing(const B &t) : B(t) {}
00179 
00181                 PolynomialOverFixedRing(const CoefficientType &element) : B(element) {}
00182 
00184                 template <typename Iterator> PolynomialOverFixedRing(Iterator first, Iterator last)
00185                         : B(first, last) {}
00186 
00188                 explicit PolynomialOverFixedRing(const char *str) : B(str, fixedRing) {}
00189 
00191                 PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount) : B(encodedPoly, byteCount) {}
00192 
00194                 explicit PolynomialOverFixedRing(const byte *BEREncodedPoly) : B(BEREncodedPoly) {}
00195 
00197                 explicit PolynomialOverFixedRing(BufferedTransformation &bt) : B(bt) {}
00198 
00200                 PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter &parameter) : B(rng, parameter, fixedRing) {}
00201 
00202                 static const ThisType &Zero();
00203                 static const ThisType &One();
00205 
00207 
00208 
00209                 int Degree() const {return B::Degree(fixedRing);}
00211                 unsigned int CoefficientCount() const {return B::CoefficientCount(fixedRing);}
00213                 CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, fixedRing);}
00215                 CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, fixedRing);}
00217 
00219 
00220 
00221                 ThisType&  operator=(const ThisType& t) {B::operator=(t); return *this;}
00223                 ThisType&  operator+=(const ThisType& t) {Accumulate(t, fixedRing); return *this;}
00225                 ThisType&  operator-=(const ThisType& t) {Reduce(t, fixedRing); return *this;}
00227                 ThisType&  operator*=(const ThisType& t) {return *this = *this*t;}
00229                 ThisType&  operator/=(const ThisType& t) {return *this = *this/t;}
00231                 ThisType&  operator%=(const ThisType& t) {return *this = *this%t;}
00232 
00234                 ThisType&  operator<<=(unsigned int n) {ShiftLeft(n, fixedRing); return *this;}
00236                 ThisType&  operator>>=(unsigned int n) {ShiftRight(n, fixedRing); return *this;}
00237 
00239                 void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, fixedRing);}
00240 
00242                 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter) {B::Randomize(rng, parameter, fixedRing);}
00243 
00245                 void Negate() {B::Negate(fixedRing);}
00246 
00247                 void swap(ThisType &t) {B::swap(t);}
00249 
00251 
00252 
00253                 bool operator!() const {return CoefficientCount()==0;}
00255                 ThisType operator+() const {return *this;}
00257                 ThisType operator-() const {return ThisType(Inverse(fixedRing));}
00259 
00261 
00262 
00263                 friend ThisType operator>>(ThisType a, unsigned int n)  {return ThisType(a>>=n);}
00265                 friend ThisType operator<<(ThisType a, unsigned int n)  {return ThisType(a<<=n);}
00267 
00269 
00270 
00271                 ThisType MultiplicativeInverse() const {return ThisType(B::MultiplicativeInverse(fixedRing));}
00273                 bool IsUnit() const {return B::IsUnit(fixedRing);}
00274 
00276                 ThisType Doubled() const {return ThisType(B::Doubled(fixedRing));}
00278                 ThisType Squared() const {return ThisType(B::Squared(fixedRing));}
00279 
00280                 CoefficientType EvaluateAt(const CoefficientType &x) const {return B::EvaluateAt(x, fixedRing);}
00281 
00283                 static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d)
00284                         {B::Divide(r, q, a, d, fixedRing);}
00286 
00288 
00289 
00290                 friend std::istream& operator>>(std::istream& in, ThisType &a)
00291                         {return a.Input(in, fixedRing);}
00293                 friend std::ostream& operator<<(std::ostream& out, const ThisType &a)
00294                         {return a.Output(out, fixedRing);}
00296 
00297 private:
00298         static const Ring fixedRing;
00299 };
00300 
00302 template <class T> class RingOfPolynomialsOver : public AbstractEuclideanDomain<PolynomialOver<T> >
00303 {
00304 public:
00305         typedef T CoefficientRing;
00306         typedef PolynomialOver<T> Element;
00307         typedef Element::CoefficientType CoefficientType;
00308         typedef 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& Zero() const
00319                 {static const Element zero; return zero;}
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 // VC50 workaround
00340         const Element& One() const
00341                 {return result = Element(m_ring.One());}
00342 
00343         const Element& Multiply(const Element &a, const Element &b) const
00344                 {return result = a.Times(b, m_ring);}
00345 
00346         const Element& Square(const Element &a) const
00347                 {return result = a.Squared(m_ring);}
00348 
00349         bool IsUnit(const Element &a) const
00350                 {return a.IsUnit(m_ring);}
00351 
00352         const Element& MultiplicativeInverse(const Element &a) const
00353                 {return result = a.MultiplicativeInverse(m_ring);}
00354 
00355         const Element& Divide(const Element &a, const Element &b) const
00356                 {return result = a.DividedBy(b, m_ring);}
00357 
00358         const Element& Mod(const Element &a, const Element &b) const
00359                 {return result = a.Modulo(b, m_ring);}
00360 
00361         void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
00362                 {Element::Divide(r, q, a, d, m_ring);}
00363 
00364         class InterpolationFailed : public Exception
00365         {
00366         public:
00367                 InterpolationFailed() : Exception("RingOfPolynomialsOver<T>: interpolation failed") {}
00368         };
00369 
00370         Element Interpolate(const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
00371 
00372         // a faster version of Interpolate(x, y, n).EvaluateAt(position)
00373         CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
00374 /*
00375         void PrepareBulkInterpolation(CoefficientType *w, const CoefficientType x[], unsigned int n) const;
00376         void PrepareBulkInterpolationAt(CoefficientType *v, const CoefficientType &position, const CoefficientType x[], const CoefficientType w[], unsigned int n) const;
00377         CoefficientType BulkInterpolateAt(const CoefficientType y[], const CoefficientType v[], unsigned int n) const;
00378 */
00379 protected:
00380         void CalculateAlpha(std::vector<CoefficientType> &alpha, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
00381 
00382         CoefficientRing m_ring;
00383 };
00384 
00385 template <class Ring, class Element>
00386 void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n);
00387 template <class Ring, class Element>
00388 void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n);
00389 template <class Ring, class Element>
00390 Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n);
00391 
00392 NAMESPACE_END
00393 
00394 // declaring these overloaded operators inside the CryptoPP namespace
00395 // causes problems with GCC 2.95.2
00396 
00398 template <class T, int instance>
00399 inline bool operator==(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00400         {return a.Equals(b, fixedRing);}
00402 template <class T, int instance>
00403 inline bool operator!=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00404         {return !(a==b);}
00405 
00407 template <class T, int instance>
00408 inline bool operator> (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00409         {return a.Degree() > b.Degree();}
00411 template <class T, int instance>
00412 inline bool operator>=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00413         {return a.Degree() >= b.Degree();}
00415 template <class T, int instance>
00416 inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00417         {return a.Degree() < b.Degree();}
00419 template <class T, int instance>
00420 inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00421         {return a.Degree() <= b.Degree();}
00422 
00424 template <class T, int instance>
00425 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00426         {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, fixedRing));}
00428 template <class T, int instance>
00429 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00430         {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, fixedRing));}
00432 template <class T, int instance>
00433 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator*(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00434         {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Times(b, fixedRing));}
00436 template <class T, int instance>
00437 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00438         {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, fixedRing));}
00440 template <class T, int instance>
00441 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00442         {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, fixedRing));}
00443 
00444 NAMESPACE_BEGIN(std)
00445 template<class T> inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b)
00446 {
00447         a.swap(b);
00448 }
00449 template<class T, int i> inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
00450 {
00451         a.swap(b);
00452 }
00453 NAMESPACE_END
00454 
00455 #endif