Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Namespace Members | Compound 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 B::DivideByZero DivideByZero;
    00168         typedef 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 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& 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