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