Crypto++
polynomi.h
Go to the documentation of this file.
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 
13 NAMESPACE_BEGIN(CryptoPP)
14 
15 //! represents single-variable polynomials over arbitrary rings
16 /*! \nosubgrouping */
17 template <class T> class PolynomialOver
18 {
19 public:
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
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
50 
51  //!
52  PolynomialOver(const Ring &ring, unsigned int count)
53  : m_coefficients((size_t)count, ring.Identity()) {}
54 
55  //! copy constructor
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
78 
79  //! create a random PolynomialOver<T>
80  PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter &parameter, 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 &parameter, 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 
151 private:
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 */
159 template <class T, int instance> class PolynomialOverFixedRing : private PolynomialOver<T>
160 {
161  typedef PolynomialOver<T> B;
163 
164 public:
165  typedef T Ring;
166  typedef typename T::Element CoefficientType;
167  typedef typename B::DivideByZero DivideByZero;
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
198 
199  //! create a random PolynomialOverFixedRing
200  PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter &parameter) : 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 &parameter) {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 
297 private:
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
310 template <class T> class RingOfPolynomialsOver : public AbstractEuclideanDomain<PolynomialOver<T> >
311 {
312 public:
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 &parameter)
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 
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 */
386 protected:
387  void CalculateAlpha(std::vector<CoefficientType> &alpha, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
388 
389  CoefficientRing m_ring;
390 };
391 
392 template <class Ring, class Element>
393 void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n);
394 template <class Ring, class Element>
395 void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n);
396 template <class Ring, class Element>
397 Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n);
398 
399 //!
400 template <class T, int instance>
401 inline bool operator==(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
402  {return a.Equals(b, a.ms_fixedRing);}
403 //!
404 template <class T, int instance>
405 inline bool operator!=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
406  {return !(a==b);}
407 
408 //!
409 template <class T, int instance>
410 inline bool operator> (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
411  {return a.Degree() > b.Degree();}
412 //!
413 template <class T, int instance>
414 inline bool operator>=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
415  {return a.Degree() >= b.Degree();}
416 //!
417 template <class T, int instance>
418 inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
419  {return a.Degree() < b.Degree();}
420 //!
421 template <class T, int instance>
422 inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
423  {return a.Degree() <= b.Degree();}
424 
425 //!
426 template <class T, int instance>
427 inline 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 //!
430 template <class T, int instance>
431 inline 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 //!
434 template <class T, int instance>
435 inline 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 //!
438 template <class T, int instance>
439 inline 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 //!
442 template <class T, int instance>
443 inline 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 
446 NAMESPACE_END
447 
448 NAMESPACE_BEGIN(std)
449 template<class T> inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b)
450 {
451  a.swap(b);
452 }
453 template<class T, int i> inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
454 {
455  a.swap(b);
456 }
457 NAMESPACE_END
458 
459 #endif
base class for all exceptions thrown by Crypto++
Definition: cryptlib.h:109
bool operator>=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:249
bool operator>(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:246
PolynomialOverFixedRing(Iterator first, Iterator last)
construct polynomial with specified coefficients, starting from coefficient of x^0 ...
Definition: polynomi.h:184
specify the distribution for randomization functions
Definition: polynomi.h:30
CoefficientType operator[](unsigned int i) const
return coefficient for x^i
Definition: polynomi.h:215
void SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring)
set the coefficient for x^i to value
PolynomialOver(Iterator begin, Iterator end)
construct polynomial with specified coefficients, starting from coefficient of x^0 ...
Definition: polynomi.h:64
PolynomialOver(const PolynomialOver< Ring > &t)
copy constructor
Definition: polynomi.h:56
PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount)
convert from big-endian byte array
Definition: polynomi.h:191
PolynomialOverFixedRing(unsigned int count=0)
creates the zero polynomial
Definition: polynomi.h:173
PolynomialOverFixedRing(const char *str)
convert from string
Definition: polynomi.h:188
unsigned int CoefficientCount() const
degree + 1
Definition: polynomi.h:211
PolynomialOverFixedRing(const ThisType &t)
copy constructor
Definition: polynomi.h:176
Abstract Euclidean Domain.
Definition: algebra.h:138
some error not belong to any of the above categories
Definition: cryptlib.h:127
Square
Definition: square.h:19
PolynomialOverFixedRing(const byte *BEREncodedPoly)
convert from Basic Encoding Rules encoded byte array
Definition: polynomi.h:194
interface for random number generators
Definition: cryptlib.h:668
PolynomialOverFixedRing(const CoefficientType &element)
construct constant polynomial
Definition: polynomi.h:181
interface for buffered transformations
Definition: cryptlib.h:770
represents single-variable polynomials over arbitrary rings
Definition: polynomi.h:17
PolynomialOver(const char *str, const Ring &ring)
convert from string
Definition: polynomi.h:68
Ring of polynomials over another ring.
Definition: polynomi.h:310
int Degree() const
the zero polynomial will return a degree of -1
Definition: polynomi.h:209
Polynomials over a fixed ring.
Definition: polynomi.h:159
CoefficientType GetCoefficient(unsigned int i) const
return coefficient for x^i
Definition: polynomi.h:213
CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const
return coefficient for x^i
PolynomialOver()
creates the zero polynomial
Definition: polynomi.h:49
void SetCoefficient(unsigned int i, const CoefficientType &value)
set the coefficient for x^i to value
Definition: polynomi.h:239
static void Divide(PolynomialOver< Ring > &r, PolynomialOver< Ring > &q, const PolynomialOver< Ring > &a, const PolynomialOver< Ring > &d, const Ring &ring)
calculate r and q such that (a == d*q + r) && (0 <= degree of r < degree of d)
PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring)
create a random PolynomialOver
Definition: polynomi.h:80
PolynomialOver(const CoefficientType &element)
construct constant polynomial
Definition: polynomi.h:60
static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d)
calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
Definition: polynomi.h:283
PolynomialOverFixedRing(BufferedTransformation &bt)
convert from BER encoded byte array stored in a BufferedTransformation object
Definition: polynomi.h:197
division by zero exception
Definition: polynomi.h:23
int Degree(const Ring &ring) const
the zero polynomial will return a degree of -1
Definition: polynomi.h:87
PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter &parameter)
create a random PolynomialOverFixedRing
Definition: polynomi.h:200