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