Crypto++

- Main Page
- Namespaces
- Classes
- Files

- File List
- 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