1#ifndef CRYPTOPP_POLYNOMI_H 2#define CRYPTOPP_POLYNOMI_H 3 4/*! \file */ 5 6#include "cryptlib.h" 7#include "misc.h" 8#include "algebra.h" 9 10#include <iosfwd> 11#include <vector> 12 13NAMESPACE_BEGIN(CryptoPP) 14 15//! represents single-variable polynomials over arbitrary rings 16/*! \nosubgrouping */ 17template <class T> class PolynomialOver 18{ 19public: 20 //! \name ENUMS, EXCEPTIONS, and TYPEDEFS 21 //@{ 22 //! division by zero exception 23 class DivideByZero : public Exception 24 { 25 public: 26 DivideByZero() : Exception(OTHER_ERROR, "PolynomialOver<T>: division by zero") {} 27 }; 28 29 //! specify the distribution for randomization functions 30 class RandomizationParameter 31 { 32 public: 33 RandomizationParameter(unsigned int coefficientCount, const typename T::RandomizationParameter &coefficientParameter ) 34 : m_coefficientCount(coefficientCount), m_coefficientParameter(coefficientParameter) {} 35 36 private: 37 unsigned int m_coefficientCount; 38 typename T::RandomizationParameter m_coefficientParameter; 39 friend class PolynomialOver<T>; 40 }; 41 42 typedef T Ring; 43 typedef typename T::Element CoefficientType; 44 //@} 45 46 //! \name CREATORS 47 //@{ 48 //! creates the zero polynomial 49 PolynomialOver() {} 50 51 //! 52 PolynomialOver(const Ring &ring, unsigned int count) 53 : m_coefficients((size_t)count, ring.Identity()) {} 54 55 //! copy constructor 56 PolynomialOver(const PolynomialOver<Ring> &t) 57 : m_coefficients(t.m_coefficients.size()) {*this = t;} 58 59 //! construct constant polynomial 60 PolynomialOver(const CoefficientType &element) 61 : m_coefficients(1, element) {} 62 63 //! construct polynomial with specified coefficients, starting from coefficient of x^0 64 template <typename Iterator> PolynomialOver(Iterator begin, Iterator end) 65 : m_coefficients(begin, end) {} 66 67 //! convert from string 68 PolynomialOver(const char *str, const Ring &ring) {FromStr(str, ring);} 69 70 //! convert from big-endian byte array 71 PolynomialOver(const byte *encodedPolynomialOver, unsigned int byteCount); 72 73 //! convert from Basic Encoding Rules encoded byte array 74 explicit PolynomialOver(const byte *BEREncodedPolynomialOver); 75 76 //! convert from BER encoded byte array stored in a BufferedTransformation object 77 explicit PolynomialOver(BufferedTransformation &bt); 78 79 //! create a random PolynomialOver<T> 80 PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter ¶meter, const Ring &ring) 81 {Randomize(rng, parameter, ring);} 82 //@} 83 84 //! \name ACCESSORS 85 //@{ 86 //! the zero polynomial will return a degree of -1 87 int Degree(const Ring &ring) const {return int(CoefficientCount(ring))-1;} 88 //! 89 unsigned int CoefficientCount(const Ring &ring) const; 90 //! return coefficient for x^i 91 CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const; 92 //@} 93 94 //! \name MANIPULATORS 95 //@{ 96 //! 97 PolynomialOver<Ring>& operator=(const PolynomialOver<Ring>& t); 98 99 //! 100 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter ¶meter, const Ring &ring); 101 102 //! set the coefficient for x^i to value 103 void SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring); 104 105 //! 106 void Negate(const Ring &ring); 107 108 //! 109 void swap(PolynomialOver<Ring> &t); 110 //@} 111 112 113 //! \name BASIC ARITHMETIC ON POLYNOMIALS 114 //@{ 115 bool Equals(const PolynomialOver<Ring> &t, const Ring &ring) const; 116 bool IsZero(const Ring &ring) const {return CoefficientCount(ring)==0;} 117 118 PolynomialOver<Ring> Plus(const PolynomialOver<Ring>& t, const Ring &ring) const; 119 PolynomialOver<Ring> Minus(const PolynomialOver<Ring>& t, const Ring &ring) const; 120 PolynomialOver<Ring> Inverse(const Ring &ring) const; 121 122 PolynomialOver<Ring> Times(const PolynomialOver<Ring>& t, const Ring &ring) const; 123 PolynomialOver<Ring> DividedBy(const PolynomialOver<Ring>& t, const Ring &ring) const; 124 PolynomialOver<Ring> Modulo(const PolynomialOver<Ring>& t, const Ring &ring) const; 125 PolynomialOver<Ring> MultiplicativeInverse(const Ring &ring) const; 126 bool IsUnit(const Ring &ring) const; 127 128 PolynomialOver<Ring>& Accumulate(const PolynomialOver<Ring>& t, const Ring &ring); 129 PolynomialOver<Ring>& Reduce(const PolynomialOver<Ring>& t, const Ring &ring); 130 131 //! 132 PolynomialOver<Ring> Doubled(const Ring &ring) const {return Plus(*this, ring);} 133 //! 134 PolynomialOver<Ring> Squared(const Ring &ring) const {return Times(*this, ring);} 135 136 CoefficientType EvaluateAt(const CoefficientType &x, const Ring &ring) const; 137 138 PolynomialOver<Ring>& ShiftLeft(unsigned int n, const Ring &ring); 139 PolynomialOver<Ring>& ShiftRight(unsigned int n, const Ring &ring); 140 141 //! calculate r and q such that (a == d*q + r) && (0 <= degree of r < degree of d) 142 static void Divide(PolynomialOver<Ring> &r, PolynomialOver<Ring> &q, const PolynomialOver<Ring> &a, const PolynomialOver<Ring> &d, const Ring &ring); 143 //@} 144 145 //! \name INPUT/OUTPUT 146 //@{ 147 std::istream& Input(std::istream &in, const Ring &ring); 148 std::ostream& Output(std::ostream &out, const Ring &ring) const; 149 //@} 150 151private: 152 void FromStr(const char *str, const Ring &ring); 153 154 std::vector<CoefficientType> m_coefficients; 155}; 156 157//! Polynomials over a fixed ring 158/*! Having a fixed ring allows overloaded operators */ 159template <class T, int instance> class PolynomialOverFixedRing : private PolynomialOver<T> 160{ 161 typedef PolynomialOver<T> B; 162 typedef PolynomialOverFixedRing<T, instance> ThisType; 163 164public: 165 typedef T Ring; 166 typedef typename T::Element CoefficientType; 167 typedef typename B::DivideByZero DivideByZero; 168 typedef typename B::RandomizationParameter RandomizationParameter; 169 170 //! \name CREATORS 171 //@{ 172 //! creates the zero polynomial 173 PolynomialOverFixedRing(unsigned int count = 0) : B(ms_fixedRing, count) {} 174 175 //! copy constructor 176 PolynomialOverFixedRing(const ThisType &t) : B(t) {} 177 178 explicit PolynomialOverFixedRing(const B &t) : B(t) {} 179 180 //! construct constant polynomial 181 PolynomialOverFixedRing(const CoefficientType &element) : B(element) {} 182 183 //! construct polynomial with specified coefficients, starting from coefficient of x^0 184 template <typename Iterator> PolynomialOverFixedRing(Iterator first, Iterator last) 185 : B(first, last) {} 186 187 //! convert from string 188 explicit PolynomialOverFixedRing(const char *str) : B(str, ms_fixedRing) {} 189 190 //! convert from big-endian byte array 191 PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount) : B(encodedPoly, byteCount) {} 192 193 //! convert from Basic Encoding Rules encoded byte array 194 explicit PolynomialOverFixedRing(const byte *BEREncodedPoly) : B(BEREncodedPoly) {} 195 196 //! convert from BER encoded byte array stored in a BufferedTransformation object 197 explicit PolynomialOverFixedRing(BufferedTransformation &bt) : B(bt) {} 198 199 //! create a random PolynomialOverFixedRing 200 PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter ¶meter) : B(rng, parameter, ms_fixedRing) {} 201 202 static const ThisType &Zero(); 203 static const ThisType &One(); 204 //@} 205 206 //! \name ACCESSORS 207 //@{ 208 //! the zero polynomial will return a degree of -1 209 int Degree() const {return B::Degree(ms_fixedRing);} 210 //! degree + 1 211 unsigned int CoefficientCount() const {return B::CoefficientCount(ms_fixedRing);} 212 //! return coefficient for x^i 213 CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);} 214 //! return coefficient for x^i 215 CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);} 216 //@} 217 218 //! \name MANIPULATORS 219 //@{ 220 //! 221 ThisType& operator=(const ThisType& t) {B::operator=(t); return *this;} 222 //! 223 ThisType& operator+=(const ThisType& t) {Accumulate(t, ms_fixedRing); return *this;} 224 //! 225 ThisType& operator-=(const ThisType& t) {Reduce(t, ms_fixedRing); return *this;} 226 //! 227 ThisType& operator*=(const ThisType& t) {return *this = *this*t;} 228 //! 229 ThisType& operator/=(const ThisType& t) {return *this = *this/t;} 230 //! 231 ThisType& operator%=(const ThisType& t) {return *this = *this%t;} 232 233 //! 234 ThisType& operator<<=(unsigned int n) {ShiftLeft(n, ms_fixedRing); return *this;} 235 //! 236 ThisType& operator>>=(unsigned int n) {ShiftRight(n, ms_fixedRing); return *this;} 237 238 //! set the coefficient for x^i to value 239 void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, ms_fixedRing);} 240 241 //! 242 void Randomize(RandomNumberGenerator &rng, const RandomizationParameter ¶meter) {B::Randomize(rng, parameter, ms_fixedRing);} 243 244 //! 245 void Negate() {B::Negate(ms_fixedRing);} 246 247 void swap(ThisType &t) {B::swap(t);} 248 //@} 249 250 //! \name UNARY OPERATORS 251 //@{ 252 //! 253 bool operator!() const {return CoefficientCount()==0;} 254 //! 255 ThisType operator+() const {return *this;} 256 //! 257 ThisType operator-() const {return ThisType(Inverse(ms_fixedRing));} 258 //@} 259 260 //! \name BINARY OPERATORS 261 //@{ 262 //! 263 friend ThisType operator>>(ThisType a, unsigned int n) {return ThisType(a>>=n);} 264 //! 265 friend ThisType operator<<(ThisType a, unsigned int n) {return ThisType(a<<=n);} 266 //@} 267 268 //! \name OTHER ARITHMETIC FUNCTIONS 269 //@{ 270 //! 271 ThisType MultiplicativeInverse() const {return ThisType(B::MultiplicativeInverse(ms_fixedRing));} 272 //! 273 bool IsUnit() const {return B::IsUnit(ms_fixedRing);} 274 275 //! 276 ThisType Doubled() const {return ThisType(B::Doubled(ms_fixedRing));} 277 //! 278 ThisType Squared() const {return ThisType(B::Squared(ms_fixedRing));} 279 280 CoefficientType EvaluateAt(const CoefficientType &x) const {return B::EvaluateAt(x, ms_fixedRing);} 281 282 //! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d)) 283 static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d) 284 {B::Divide(r, q, a, d, ms_fixedRing);} 285 //@} 286 287 //! \name INPUT/OUTPUT 288 //@{ 289 //! 290 friend std::istream& operator>>(std::istream& in, ThisType &a) 291 {return a.Input(in, ms_fixedRing);} 292 //! 293 friend std::ostream& operator<<(std::ostream& out, const ThisType &a) 294 {return a.Output(out, ms_fixedRing);} 295 //@} 296 297private: 298 struct NewOnePolynomial 299 { 300 ThisType * operator()() const 301 { 302 return new ThisType(ms_fixedRing.MultiplicativeIdentity()); 303 } 304 }; 305 306 static const Ring ms_fixedRing; 307}; 308 309//! Ring of polynomials over another ring 310template <class T> class RingOfPolynomialsOver : public AbstractEuclideanDomain<PolynomialOver<T> > 311{ 312public: 313 typedef T CoefficientRing; 314 typedef PolynomialOver<T> Element; 315 typedef typename Element::CoefficientType CoefficientType; 316 typedef typename Element::RandomizationParameter RandomizationParameter; 317 318 RingOfPolynomialsOver(const CoefficientRing &ring) : m_ring(ring) {} 319 320 Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter ¶meter) 321 {return Element(rng, parameter, m_ring);} 322 323 bool Equal(const Element &a, const Element &b) const 324 {return a.Equals(b, m_ring);} 325 326 const Element& Identity() const 327 {return this->result = m_ring.Identity();} 328 329 const Element& Add(const Element &a, const Element &b) const 330 {return this->result = a.Plus(b, m_ring);} 331 332 Element& Accumulate(Element &a, const Element &b) const 333 {a.Accumulate(b, m_ring); return a;} 334 335 const Element& Inverse(const Element &a) const 336 {return this->result = a.Inverse(m_ring);} 337 338 const Element& Subtract(const Element &a, const Element &b) const 339 {return this->result = a.Minus(b, m_ring);} 340 341 Element& Reduce(Element &a, const Element &b) const 342 {return a.Reduce(b, m_ring);} 343 344 const Element& Double(const Element &a) const 345 {return this->result = a.Doubled(m_ring);} 346 347 const Element& MultiplicativeIdentity() const 348 {return this->result = m_ring.MultiplicativeIdentity();} 349 350 const Element& Multiply(const Element &a, const Element &b) const 351 {return this->result = a.Times(b, m_ring);} 352 353 const Element& Square(const Element &a) const 354 {return this->result = a.Squared(m_ring);} 355 356 bool IsUnit(const Element &a) const 357 {return a.IsUnit(m_ring);} 358 359 const Element& MultiplicativeInverse(const Element &a) const 360 {return this->result = a.MultiplicativeInverse(m_ring);} 361 362 const Element& Divide(const Element &a, const Element &b) const 363 {return this->result = a.DividedBy(b, m_ring);} 364 365 const Element& Mod(const Element &a, const Element &b) const 366 {return this->result = a.Modulo(b, m_ring);} 367 368 void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const 369 {Element::Divide(r, q, a, d, m_ring);} 370 371 class InterpolationFailed : public Exception 372 { 373 public: 374 InterpolationFailed() : Exception(OTHER_ERROR, "RingOfPolynomialsOver<T>: interpolation failed") {} 375 }; 376 377 Element Interpolate(const CoefficientType x[], const CoefficientType y[], unsigned int n) const; 378 379 // a faster version of Interpolate(x, y, n).EvaluateAt(position) 380 CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const; 381/* 382 void PrepareBulkInterpolation(CoefficientType *w, const CoefficientType x[], unsigned int n) const; 383 void PrepareBulkInterpolationAt(CoefficientType *v, const CoefficientType &position, const CoefficientType x[], const CoefficientType w[], unsigned int n) const; 384 CoefficientType BulkInterpolateAt(const CoefficientType y[], const CoefficientType v[], unsigned int n) const; 385*/ 386protected: 387 void CalculateAlpha(std::vector<CoefficientType> &alpha, const CoefficientType x[], const CoefficientType y[], unsigned int n) const; 388 389 CoefficientRing m_ring; 390}; 391 392template <class Ring, class Element> 393void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n); 394template <class Ring, class Element> 395void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n); 396template <class Ring, class Element> 397Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n); 398 399//! 400template <class T, int instance> 401inline bool operator==(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 402 {return a.Equals(b, a.ms_fixedRing);} 403//! 404template <class T, int instance> 405inline bool operator!=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 406 {return !(a==b);} 407 408//! 409template <class T, int instance> 410inline bool operator> (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 411 {return a.Degree() > b.Degree();} 412//! 413template <class T, int instance> 414inline bool operator>=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 415 {return a.Degree() >= b.Degree();} 416//! 417template <class T, int instance> 418inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 419 {return a.Degree() < b.Degree();} 420//! 421template <class T, int instance> 422inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 423 {return a.Degree() <= b.Degree();} 424 425//! 426template <class T, int instance> 427inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 428 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, a.ms_fixedRing));} 429//! 430template <class T, int instance> 431inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 432 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, a.ms_fixedRing));} 433//! 434template <class T, int instance> 435inline CryptoPP::PolynomialOverFixedRing<T, instance> operator*(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 436 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Times(b, a.ms_fixedRing));} 437//! 438template <class T, int instance> 439inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 440 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, a.ms_fixedRing));} 441//! 442template <class T, int instance> 443inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b) 444 {return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, a.ms_fixedRing));} 445 446NAMESPACE_END 447 448NAMESPACE_BEGIN(std) 449template<class T> inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b) 450{ 451 a.swap(b); 452} 453template<class T, int i> inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b) 454{ 455 a.swap(b); 456} 457NAMESPACE_END 458 459#endif 460