Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class 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 typename B::DivideByZero DivideByZero;
    00168         typedef typename B::RandomizationParameter RandomizationParameter;
    00169
    00170         //! \name CREATORS
    00171         //@{
    00172                 //! creates the zero polynomial
    00173                 PolynomialOverFixedRing(unsigned int count = 0) : B(ms_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, ms_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, ms_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(ms_fixedRing);}
    00210                 //! degree + 1
    00211                 unsigned int CoefficientCount() const {return B::CoefficientCount(ms_fixedRing);}
    00212                 //! return coefficient for x^i
    00213                 CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);}
    00214                 //! return coefficient for x^i
    00215                 CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, ms_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, 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                 //! set the coefficient for x^i to value
    00239                 void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, ms_fixedRing);}
    00240
    00241                 //!
    00242                 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter) {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         //! \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(ms_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(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                 //! 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, ms_fixedRing);}
    00285         //@}
    00286
    00287         //! \name INPUT/OUTPUT
    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 //! Ring of polynomials over another ring
    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 &parameter)
    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         // a faster version of Interpolate(x, y, n).EvaluateAt(position)
    00380         CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
    00381 /*
    00382         void PrepareBulkInterpolation(CoefficientType *w, const CoefficientType x[], unsigned int n) const;
    00383         void PrepareBulkInterpolationAt(CoefficientType *v, const CoefficientType &position, const CoefficientType x[], const CoefficientType w[], unsigned int n) const;
    00384         CoefficientType BulkInterpolateAt(const CoefficientType y[], const CoefficientType v[], unsigned int n) const;
    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