• 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

Generated on Tue Jun 30 2015 19:07:05 for Crypto++ by  doxygen 1.7.1