include/cryptopp/polynomi.h

0001 // polynomi.h - originally written and placed in the public domain by Wei Dai

0002
0003 /// \file polynomi.h

0004 /// \brief Classes for polynomial basis and operations

0005
0006 #ifndef CRYPTOPP_POLYNOMI_H
0007 #define CRYPTOPP_POLYNOMI_H
0008
0009 #include "cryptlib.h"
0010 #include "secblock.h"
0011 #include "algebra.h"
0012 #include "misc.h"
0013
0014 #include <iosfwd>
0015 #include <vector>
0016
0017 NAMESPACE_BEGIN(CryptoPP)
0018
0019 /// represents single-variable polynomials over arbitrary rings

0020 /*! \nosubgrouping */
0021 template <class T> class PolynomialOver
0022 {
0023 public:
0024     /// \name ENUMS, EXCEPTIONS, and TYPEDEFS

0025     //@{

0026         /// division by zero exception

0027         class DivideByZero : public Exception
0028         {
0029         public:
0030             DivideByZero() : Exception(OTHER_ERROR, "PolynomialOver<T>: division by zero") {}
0031         };
0032
0033         /// specify the distribution for randomization functions

0034         class RandomizationParameter
0035         {
0036         public:
0037             RandomizationParameter(unsigned int coefficientCount, const typename T::RandomizationParameter &coefficientParameter )
0038                 : m_coefficientCount(coefficientCount), m_coefficientParameter(coefficientParameter) {}
0039
0040         private:
0041             unsigned int m_coefficientCount;
0042             typename T::RandomizationParameter m_coefficientParameter;
0043             friend class PolynomialOver<T>;
0044         };
0045
0046         typedef T Ring;
0047         typedef typename T::Element CoefficientType;
0048     //@}

0049
0050     /// \name CREATORS

0051     //@{

0052         /// creates the zero polynomial

0053         PolynomialOver() {}
0054
0055         ///

0056         PolynomialOver(const Ring &ring, unsigned int count)
0057             : m_coefficients((size_t)count, ring.Identity()) {}
0058
0059         /// copy constructor

0060         PolynomialOver(const PolynomialOver<Ring> &t)
0061             : m_coefficients(t.m_coefficients.size()) {*this = t;}
0062
0063         /// construct constant polynomial

0064         PolynomialOver(const CoefficientType &element)
0065             : m_coefficients(1, element) {}
0066
0067         /// construct polynomial with specified coefficients, starting from coefficient of x^0

0068         template <typename Iterator> PolynomialOver(Iterator begin, Iterator end)
0069             : m_coefficients(begin, end) {}
0070
0071         /// convert from string

0072         PolynomialOver(const char *str, const Ring &ring) {FromStr(str, ring);}
0073
0074         /// convert from big-endian byte array

0075         PolynomialOver(const byte *encodedPolynomialOver, unsigned int byteCount);
0076
0077         /// convert from Basic Encoding Rules encoded byte array

0078         explicit PolynomialOver(const byte *BEREncodedPolynomialOver);
0079
0080         /// convert from BER encoded byte array stored in a BufferedTransformation object

0081         explicit PolynomialOver(BufferedTransformation &bt);
0082
0083         /// create a random PolynomialOver<T>

0084         PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring)
0085             {Randomize(rng, parameter, ring);}
0086     //@}

0087
0088     /// \name ACCESSORS

0089     //@{

0090         /// the zero polynomial will return a degree of -1

0091         int Degree(const Ring &ring) const {return int(CoefficientCount(ring))-1;}
0092         ///

0093         unsigned int CoefficientCount(const Ring &ring) const;
0094         /// return coefficient for x^i

0095         CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const;
0096     //@}

0097
0098     /// \name MANIPULATORS

0099     //@{

0100         ///

0101         PolynomialOver<Ring>&  operator=(const PolynomialOver<Ring>& t);
0102
0103         ///

0104         void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring);
0105
0106         /// set the coefficient for x^i to value

0107         void SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring);
0108
0109         ///

0110         void Negate(const Ring &ring);
0111
0112         ///

0113         void swap(PolynomialOver<Ring> &t);
0114     //@}

0115
0116
0117     /// \name BASIC ARITHMETIC ON POLYNOMIALS

0118     //@{

0119         bool Equals(const PolynomialOver<Ring> &t, const Ring &ring) const;
0120         bool IsZero(const Ring &ring) const {return CoefficientCount(ring)==0;}
0121
0122         PolynomialOver<Ring> Plus(const PolynomialOver<Ring>& t, const Ring &ring) const;
0123         PolynomialOver<Ring> Minus(const PolynomialOver<Ring>& t, const Ring &ring) const;
0124         PolynomialOver<Ring> Inverse(const Ring &ring) const;
0125
0126         PolynomialOver<Ring> Times(const PolynomialOver<Ring>& t, const Ring &ring) const;
0127         PolynomialOver<Ring> DividedBy(const PolynomialOver<Ring>& t, const Ring &ring) const;
0128         PolynomialOver<Ring> Modulo(const PolynomialOver<Ring>& t, const Ring &ring) const;
0129         PolynomialOver<Ring> MultiplicativeInverse(const Ring &ring) const;
0130         bool IsUnit(const Ring &ring) const;
0131
0132         PolynomialOver<Ring>& Accumulate(const PolynomialOver<Ring>& t, const Ring &ring);
0133         PolynomialOver<Ring>& Reduce(const PolynomialOver<Ring>& t, const Ring &ring);
0134
0135         ///

0136         PolynomialOver<Ring> Doubled(const Ring &ring) const {return Plus(*this, ring);}
0137         ///

0138         PolynomialOver<Ring> Squared(const Ring &ring) const {return Times(*this, ring);}
0139
0140         CoefficientType EvaluateAt(const CoefficientType &x, const Ring &ring) const;
0141
0142         PolynomialOver<Ring>& ShiftLeft(unsigned int n, const Ring &ring);
0143         PolynomialOver<Ring>& ShiftRight(unsigned int n, const Ring &ring);
0144
0145         /// calculate r and q such that (a == d*q + r) && (0 <= degree of r < degree of d)

0146         static void Divide(PolynomialOver<Ring> &r, PolynomialOver<Ring> &q, const PolynomialOver<Ring> &a, const PolynomialOver<Ring> &d, const Ring &ring);
0147     //@}

0148
0149     /// \name INPUT/OUTPUT

0150     //@{

0151         std::istream& Input(std::istream &in, const Ring &ring);
0152         std::ostream& Output(std::ostream &out, const Ring &ring) const;
0153     //@}

0154
0155 private:
0156     void FromStr(const char *str, const Ring &ring);
0157
0158     std::vector<CoefficientType> m_coefficients;
0159 };
0160
0161 /// Polynomials over a fixed ring

0162 /*! Having a fixed ring allows overloaded operators */
0163 template <class T, int instance> class PolynomialOverFixedRing : private PolynomialOver<T>
0164 {
0165     typedef PolynomialOver<T> B;
0166     typedef PolynomialOverFixedRing<T, instance> ThisType;
0167
0168 public:
0169     typedef T Ring;
0170     typedef typename T::Element CoefficientType;
0171     typedef typename B::DivideByZero DivideByZero;
0172     typedef typename B::RandomizationParameter RandomizationParameter;
0173
0174     /// \name CREATORS

0175     //@{

0176         /// creates the zero polynomial

0177         PolynomialOverFixedRing(unsigned int count = 0) : B(ms_fixedRing, count) {}
0178
0179         /// copy constructor

0180         PolynomialOverFixedRing(const ThisType &t) : B(t) {}
0181
0182         explicit PolynomialOverFixedRing(const B &t) : B(t) {}
0183
0184         /// construct constant polynomial

0185         PolynomialOverFixedRing(const CoefficientType &element) : B(element) {}
0186
0187         /// construct polynomial with specified coefficients, starting from coefficient of x^0

0188         template <typename Iterator> PolynomialOverFixedRing(Iterator first, Iterator last)
0189             : B(first, last) {}
0190
0191         /// convert from string

0192         explicit PolynomialOverFixedRing(const char *str) : B(str, ms_fixedRing) {}
0193
0194         /// convert from big-endian byte array

0195         PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount) : B(encodedPoly, byteCount) {}
0196
0197         /// convert from Basic Encoding Rules encoded byte array

0198         explicit PolynomialOverFixedRing(const byte *BEREncodedPoly) : B(BEREncodedPoly) {}
0199
0200         /// convert from BER encoded byte array stored in a BufferedTransformation object

0201         explicit PolynomialOverFixedRing(BufferedTransformation &bt) : B(bt) {}
0202
0203         /// create a random PolynomialOverFixedRing

0204         PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter &parameter) : B(rng, parameter, ms_fixedRing) {}
0205
0206         static const ThisType &Zero();
0207         static const ThisType &One();
0208     //@}

0209
0210     /// \name ACCESSORS

0211     //@{

0212         /// the zero polynomial will return a degree of -1

0213         int Degree() const {return B::Degree(ms_fixedRing);}
0214         /// degree + 1

0215         unsigned int CoefficientCount() const {return B::CoefficientCount(ms_fixedRing);}
0216         /// return coefficient for x^i

0217         CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);}
0218         /// return coefficient for x^i

0219         CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);}
0220     //@}

0221
0222     /// \name MANIPULATORS

0223     //@{

0224         ///

0225         ThisType&  operator=(const ThisType& t) {B::operator=(t); return *this;}
0226         ///

0227         ThisType&  operator+=(const ThisType& t) {Accumulate(t, ms_fixedRing); return *this;}
0228         ///

0229         ThisType&  operator-=(const ThisType& t) {Reduce(t, ms_fixedRing); return *this;}
0230         ///

0231         ThisType&  operator*=(const ThisType& t) {return *this = *this*t;}
0232         ///

0233         ThisType&  operator/=(const ThisType& t) {return *this = *this/t;}
0234         ///

0235         ThisType&  operator%=(const ThisType& t) {return *this = *this%t;}
0236
0237         ///

0238         ThisType&  operator<<=(unsigned int n) {ShiftLeft(n, ms_fixedRing); return *this;}
0239         ///

0240         ThisType&  operator>>=(unsigned int n) {ShiftRight(n, ms_fixedRing); return *this;}
0241
0242         /// set the coefficient for x^i to value

0243         void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, ms_fixedRing);}
0244
0245         ///

0246         void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter) {B::Randomize(rng, parameter, ms_fixedRing);}
0247
0248         ///

0249         void Negate() {B::Negate(ms_fixedRing);}
0250
0251         void swap(ThisType &t) {B::swap(t);}
0252     //@}

0253
0254     /// \name UNARY OPERATORS

0255     //@{

0256         ///

0257         bool operator!() const {return CoefficientCount()==0;}
0258         ///

0259         ThisType operator+() const {return *this;}
0260         ///

0261         ThisType operator-() const {return ThisType(Inverse(ms_fixedRing));}
0262     //@}

0263
0264     /// \name BINARY OPERATORS

0265     //@{

0266         ///

0267         friend ThisType operator>>(ThisType a, unsigned int n)  {return ThisType(a>>=n);}
0268         ///

0269         friend ThisType operator<<(ThisType a, unsigned int n)  {return ThisType(a<<=n);}
0270     //@}

0271
0272     /// \name OTHER ARITHMETIC FUNCTIONS

0273     //@{

0274         ///

0275         ThisType MultiplicativeInverse() const {return ThisType(B::MultiplicativeInverse(ms_fixedRing));}
0276         ///

0277         bool IsUnit() const {return B::IsUnit(ms_fixedRing);}
0278
0279         ///

0280         ThisType Doubled() const {return ThisType(B::Doubled(ms_fixedRing));}
0281         ///

0282         ThisType Squared() const {return ThisType(B::Squared(ms_fixedRing));}
0283
0284         CoefficientType EvaluateAt(const CoefficientType &x) const {return B::EvaluateAt(x, ms_fixedRing);}
0285
0286         /// calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))

0287         static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d)
0288             {B::Divide(r, q, a, d, ms_fixedRing);}
0289     //@}

0290
0291     /// \name INPUT/OUTPUT

0292     //@{

0293         ///

0294         friend std::istream& operator>>(std::istream& in, ThisType &a)
0295             {return a.Input(in, ms_fixedRing);}
0296         ///

0297         friend std::ostream& operator<<(std::ostream& out, const ThisType &a)
0298             {return a.Output(out, ms_fixedRing);}
0299     //@}

0300
0301 private:
0302     struct NewOnePolynomial
0303     {
0304         ThisType * operator()() const
0305         {
0306             return new ThisType(ms_fixedRing.MultiplicativeIdentity());
0307         }
0308     };
0309
0310     static const Ring ms_fixedRing;
0311 };
0312
0313 /// Ring of polynomials over another ring

0314 template <class T> class RingOfPolynomialsOver : public AbstractEuclideanDomain<PolynomialOver<T> >
0315 {
0316 public:
0317     typedef T CoefficientRing;
0318     typedef PolynomialOver<T> Element;
0319     typedef typename Element::CoefficientType CoefficientType;
0320     typedef typename Element::RandomizationParameter RandomizationParameter;
0321
0322     RingOfPolynomialsOver(const CoefficientRing &ring) : m_ring(ring) {}
0323
0324     Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter &parameter)
0325         {return Element(rng, parameter, m_ring);}
0326
0327     bool Equal(const Element &a, const Element &b) const
0328         {return a.Equals(b, m_ring);}
0329
0330     const Element& Identity() const
0331         {return this->result = m_ring.Identity();}
0332
0333     const Element& Add(const Element &a, const Element &b) const
0334         {return this->result = a.Plus(b, m_ring);}
0335
0336     Element& Accumulate(Element &a, const Element &b) const
0337         {a.Accumulate(b, m_ring); return a;}
0338
0339     const Element& Inverse(const Element &a) const
0340         {return this->result = a.Inverse(m_ring);}
0341
0342     const Element& Subtract(const Element &a, const Element &b) const
0343         {return this->result = a.Minus(b, m_ring);}
0344
0345     Element& Reduce(Element &a, const Element &b) const
0346         {return a.Reduce(b, m_ring);}
0347
0348     const Element& Double(const Element &a) const
0349         {return this->result = a.Doubled(m_ring);}
0350
0351     const Element& MultiplicativeIdentity() const
0352         {return this->result = m_ring.MultiplicativeIdentity();}
0353
0354     const Element& Multiply(const Element &a, const Element &b) const
0355         {return this->result = a.Times(b, m_ring);}
0356
0357     const Element& Square(const Element &a) const
0358         {return this->result = a.Squared(m_ring);}
0359
0360     bool IsUnit(const Element &a) const
0361         {return a.IsUnit(m_ring);}
0362
0363     const Element& MultiplicativeInverse(const Element &a) const
0364         {return this->result = a.MultiplicativeInverse(m_ring);}
0365
0366     const Element& Divide(const Element &a, const Element &b) const
0367         {return this->result = a.DividedBy(b, m_ring);}
0368
0369     const Element& Mod(const Element &a, const Element &b) const
0370         {return this->result = a.Modulo(b, m_ring);}
0371
0372     void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
0373         {Element::Divide(r, q, a, d, m_ring);}
0374
0375     class InterpolationFailed : public Exception
0376     {
0377     public:
0378         InterpolationFailed() : Exception(OTHER_ERROR, "RingOfPolynomialsOver<T>: interpolation failed") {}
0379     };
0380
0381     Element Interpolate(const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
0382
0383     // a faster version of Interpolate(x, y, n).EvaluateAt(position)

0384     CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
0385 /*

0386     void PrepareBulkInterpolation(CoefficientType *w, const CoefficientType x[], unsigned int n) const;

0387     void PrepareBulkInterpolationAt(CoefficientType *v, const CoefficientType &position, const CoefficientType x[], const CoefficientType w[], unsigned int n) const;

0388     CoefficientType BulkInterpolateAt(const CoefficientType y[], const CoefficientType v[], unsigned int n) const;

0389 */
0390 protected:
0391     void CalculateAlpha(std::vector<CoefficientType> &alpha, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
0392
0393     CoefficientRing m_ring;
0394 };
0395
0396 template <class Ring, class Element>
0397 void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n);
0398 template <class Ring, class Element>
0399 void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n);
0400 template <class Ring, class Element>
0401 Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n);
0402
0403 ///

0404 template <class T, int instance>
0405 inline bool operator==(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0406     {return a.Equals(b, a.ms_fixedRing);}
0407 ///

0408 template <class T, int instance>
0409 inline bool operator!=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0410     {return !(a==b);}
0411
0412 ///

0413 template <class T, int instance>
0414 inline bool operator> (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0415     {return a.Degree() > b.Degree();}
0416 ///

0417 template <class T, int instance>
0418 inline bool operator>=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0419     {return a.Degree() >= b.Degree();}
0420 ///

0421 template <class T, int instance>
0422 inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0423     {return a.Degree() < b.Degree();}
0424 ///

0425 template <class T, int instance>
0426 inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0427     {return a.Degree() <= b.Degree();}
0428
0429 ///

0430 template <class T, int instance>
0431 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0432     {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, a.ms_fixedRing));}
0433 ///

0434 template <class T, int instance>
0435 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0436     {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, a.ms_fixedRing));}
0437 ///

0438 template <class T, int instance>
0439 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator*(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0440     {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Times(b, a.ms_fixedRing));}
0441 ///

0442 template <class T, int instance>
0443 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0444     {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, a.ms_fixedRing));}
0445 ///

0446 template <class T, int instance>
0447 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
0448     {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, a.ms_fixedRing));}
0449
0450 NAMESPACE_END
0451
0452 NAMESPACE_BEGIN(std)
0453 template<class T> inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b)
0454 {
0455     a.swap(b);
0456 }
0457 template<class T, int i> inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
0458 {
0459     a.swap(b);
0460 }
0461 NAMESPACE_END
0462
0463 #endif