Fabcoin Core  0.16.2
P2P Digital Currency
algebra.h
Go to the documentation of this file.
1 // algebra.h - written and placed in the public domain by Wei Dai
2 
5 
6 #ifndef CRYPTOPP_ALGEBRA_H
7 #define CRYPTOPP_ALGEBRA_H
8 
9 #include "config.h"
10 #include "misc.h"
11 #include "integer.h"
12 
14 
15 class Integer;
16 
26 template <class T> class CRYPTOPP_NO_VTABLE AbstractGroup
27 {
28 public:
29  typedef T Element;
30 
31  virtual ~AbstractGroup() {}
32 
38  virtual bool Equal(const Element &a, const Element &b) const =0;
39 
42  virtual const Element& Identity() const =0;
43 
48  virtual const Element& Add(const Element &a, const Element &b) const =0;
49 
53  virtual const Element& Inverse(const Element &a) const =0;
54 
57  virtual bool InversionIsFast() const {return false;}
58 
62  virtual const Element& Double(const Element &a) const;
63 
68  virtual const Element& Subtract(const Element &a, const Element &b) const;
69 
74  virtual Element& Accumulate(Element &a, const Element &b) const;
75 
80  virtual Element& Reduce(Element &a, const Element &b) const;
81 
86  virtual Element ScalarMultiply(const Element &a, const Integer &e) const;
87 
94  virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
95 
106  virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
107 };
108 
118 template <class T> class CRYPTOPP_NO_VTABLE AbstractRing : public AbstractGroup<T>
119 {
120 public:
121  typedef T Element;
122 
124  AbstractRing() {m_mg.m_pRing = this;}
125 
129  {CRYPTOPP_UNUSED(source); m_mg.m_pRing = this;}
130 
134  {CRYPTOPP_UNUSED(source); return *this;}
135 
139  virtual bool IsUnit(const Element &a) const =0;
140 
143  virtual const Element& MultiplicativeIdentity() const =0;
144 
149  virtual const Element& Multiply(const Element &a, const Element &b) const =0;
150 
153  virtual const Element& MultiplicativeInverse(const Element &a) const =0;
154 
158  virtual const Element& Square(const Element &a) const;
159 
164  virtual const Element& Divide(const Element &a, const Element &b) const;
165 
170  virtual Element Exponentiate(const Element &a, const Integer &e) const;
171 
178  virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
179 
190  virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
191 
194  virtual const AbstractGroup<T>& MultiplicativeGroup() const
195  {return m_mg;}
196 
197 private:
199  {
200  public:
201  const AbstractRing<T>& GetRing() const
202  {return *m_pRing;}
203 
204  bool Equal(const Element &a, const Element &b) const
205  {return GetRing().Equal(a, b);}
206 
207  const Element& Identity() const
208  {return GetRing().MultiplicativeIdentity();}
209 
210  const Element& Add(const Element &a, const Element &b) const
211  {return GetRing().Multiply(a, b);}
212 
213  Element& Accumulate(Element &a, const Element &b) const
214  {return a = GetRing().Multiply(a, b);}
215 
216  const Element& Inverse(const Element &a) const
217  {return GetRing().MultiplicativeInverse(a);}
218 
219  const Element& Subtract(const Element &a, const Element &b) const
220  {return GetRing().Divide(a, b);}
221 
222  Element& Reduce(Element &a, const Element &b) const
223  {return a = GetRing().Divide(a, b);}
224 
225  const Element& Double(const Element &a) const
226  {return GetRing().Square(a);}
227 
228  Element ScalarMultiply(const Element &a, const Integer &e) const
229  {return GetRing().Exponentiate(a, e);}
230 
231  Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
232  {return GetRing().CascadeExponentiate(x, e1, y, e2);}
233 
234  void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
235  {GetRing().SimultaneousExponentiate(results, base, exponents, exponentsCount);}
236 
238  };
239 
240  MultiplicativeGroupT m_mg;
241 };
242 
243 // ********************************************************
244 
248 template <class T, class E = Integer>
250 {
251 public:
253  BaseAndExponent(const T &base, const E &exponent) : base(base), exponent(exponent) {}
254  bool operator<(const BaseAndExponent<T, E> &rhs) const {return exponent < rhs.exponent;}
257 };
258 
259 // VC60 workaround: incomplete member template support
260 template <class Element, class Iterator>
261  Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end);
262 template <class Element, class Iterator>
263  Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end);
264 
265 // ********************************************************
266 
276 template <class T> class CRYPTOPP_NO_VTABLE AbstractEuclideanDomain : public AbstractRing<T>
277 {
278 public:
279  typedef T Element;
280 
286  virtual void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const =0;
287 
292  virtual const Element& Mod(const Element &a, const Element &b) const =0;
293 
298  virtual const Element& Gcd(const Element &a, const Element &b) const;
299 
300 protected:
301  mutable Element result;
302 };
303 
304 // ********************************************************
305 
315 template <class T> class EuclideanDomainOf : public AbstractEuclideanDomain<T>
316 {
317 public:
318  typedef T Element;
319 
321 
322  bool Equal(const Element &a, const Element &b) const
323  {return a==b;}
324 
325  const Element& Identity() const
326  {return Element::Zero();}
327 
328  const Element& Add(const Element &a, const Element &b) const
329  {return result = a+b;}
330 
331  Element& Accumulate(Element &a, const Element &b) const
332  {return a+=b;}
333 
334  const Element& Inverse(const Element &a) const
335  {return result = -a;}
336 
337  const Element& Subtract(const Element &a, const Element &b) const
338  {return result = a-b;}
339 
340  Element& Reduce(Element &a, const Element &b) const
341  {return a-=b;}
342 
343  const Element& Double(const Element &a) const
344  {return result = a.Doubled();}
345 
346  const Element& MultiplicativeIdentity() const
347  {return Element::One();}
348 
349  const Element& Multiply(const Element &a, const Element &b) const
350  {return result = a*b;}
351 
352  const Element& Square(const Element &a) const
353  {return result = a.Squared();}
354 
355  bool IsUnit(const Element &a) const
356  {return a.IsUnit();}
357 
358  const Element& MultiplicativeInverse(const Element &a) const
359  {return result = a.MultiplicativeInverse();}
360 
361  const Element& Divide(const Element &a, const Element &b) const
362  {return result = a/b;}
363 
364  const Element& Mod(const Element &a, const Element &b) const
365  {return result = a%b;}
366 
367  void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
368  {Element::Divide(r, q, a, d);}
369 
370  bool operator==(const EuclideanDomainOf<T> &rhs) const
371  {CRYPTOPP_UNUSED(rhs); return true;}
372 
373 private:
374  mutable Element result;
375 };
376 
386 template <class T> class QuotientRing : public AbstractRing<typename T::Element>
387 {
388 public:
390  typedef typename T::Element Element;
391 
392  QuotientRing(const EuclideanDomain &domain, const Element &modulus)
393  : m_domain(domain), m_modulus(modulus) {}
394 
395  const EuclideanDomain & GetDomain() const
396  {return m_domain;}
397 
398  const Element& GetModulus() const
399  {return m_modulus;}
400 
401  bool Equal(const Element &a, const Element &b) const
402  {return m_domain.Equal(m_domain.Mod(m_domain.Subtract(a, b), m_modulus), m_domain.Identity());}
403 
404  const Element& Identity() const
405  {return m_domain.Identity();}
406 
407  const Element& Add(const Element &a, const Element &b) const
408  {return m_domain.Add(a, b);}
409 
410  Element& Accumulate(Element &a, const Element &b) const
411  {return m_domain.Accumulate(a, b);}
412 
413  const Element& Inverse(const Element &a) const
414  {return m_domain.Inverse(a);}
415 
416  const Element& Subtract(const Element &a, const Element &b) const
417  {return m_domain.Subtract(a, b);}
418 
419  Element& Reduce(Element &a, const Element &b) const
420  {return m_domain.Reduce(a, b);}
421 
422  const Element& Double(const Element &a) const
423  {return m_domain.Double(a);}
424 
425  bool IsUnit(const Element &a) const
426  {return m_domain.IsUnit(m_domain.Gcd(a, m_modulus));}
427 
428  const Element& MultiplicativeIdentity() const
429  {return m_domain.MultiplicativeIdentity();}
430 
431  const Element& Multiply(const Element &a, const Element &b) const
432  {return m_domain.Mod(m_domain.Multiply(a, b), m_modulus);}
433 
434  const Element& Square(const Element &a) const
435  {return m_domain.Mod(m_domain.Square(a), m_modulus);}
436 
437  const Element& MultiplicativeInverse(const Element &a) const;
438 
439  bool operator==(const QuotientRing<T> &rhs) const
440  {return m_domain == rhs.m_domain && m_modulus == rhs.m_modulus;}
441 
442 protected:
443  EuclideanDomain m_domain;
444  Element m_modulus;
445 };
446 
448 
449 #ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES
450 #include "algebra.cpp"
451 #endif
452 
453 #endif
PolynomialMod2 Squared() const
Definition: gf2n.cpp:273
const Element & Inverse(const Element &a) const
Inverts the element in the group.
Definition: algebra.h:216
AbstractRing & operator=(const AbstractRing &source)
Assign an AbstractRing.
Definition: algebra.h:133
bool Equal(const Element &a, const Element &b) const
Compare two elements for equality.
Definition: algebra.h:401
const Element & Inverse(const Element &a) const
Inverts the element in the group.
Definition: algebra.h:334
Utility functions for the Crypto++ library.
PolynomialMod2 Doubled() const
is always zero since we&#39;re working modulo 2
Definition: gf2n.h:218
Element m_modulus
Definition: algebra.h:444
const Element & Subtract(const Element &a, const Element &b) const
Subtracts elements in the group.
Definition: algebra.h:416
virtual bool InversionIsFast() const
Determine if inversion is fast.
Definition: algebra.h:57
#define T(i, x)
const Element & Square(const Element &a) const
Square an element in the group.
Definition: algebra.h:434
Element & Reduce(Element &a, const Element &b) const
Reduces an element in the congruence class.
Definition: algebra.h:340
#define NAMESPACE_BEGIN(x)
Definition: config.h:200
void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
Performs the division algorithm on two elements in the ring.
Definition: algebra.h:367
Element & Reduce(Element &a, const Element &b) const
Reduces an element in the congruence class.
Definition: algebra.h:222
Abstract Euclidean domain.
Definition: algebra.h:276
BaseAndExponent(const T &base, const E &exponent)
Definition: algebra.h:253
virtual const AbstractGroup< T > & MultiplicativeGroup() const
Retrieves the multiplicative group.
Definition: algebra.h:194
AbstractRing()
Construct an AbstractRing.
Definition: algebra.h:124
Library configuration file.
const Element & Mod(const Element &a, const Element &b) const
Performs a modular reduction in the ring.
Definition: algebra.h:364
EuclideanDomain m_domain
Definition: algebra.h:443
const Element & Subtract(const Element &a, const Element &b) const
Subtracts elements in the group.
Definition: algebra.h:219
int Add(word *C, const word *A, const word *B, size_t N)
Definition: integer.cpp:2143
const AbstractRing< T > & GetRing() const
Definition: algebra.h:201
Element & Accumulate(Element &a, const Element &b) const
TODO.
Definition: algebra.h:410
Element GeneralCascadeMultiplication(const AbstractGroup< Element > &group, Iterator begin, Iterator end)
Definition: algebra.cpp:172
Quotient ring.
Definition: algebra.h:386
const Element & Identity() const
Provides the Identity element.
Definition: algebra.h:404
const Element & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Definition: algebra.h:428
const Element & Identity() const
Provides the Identity element.
Definition: algebra.h:207
Abstract ring.
Definition: algebra.h:118
Element & Accumulate(Element &a, const Element &b) const
TODO.
Definition: algebra.h:331
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
Definition: gf2n.h:225
#define a(i)
#define x(i)
const Element & Add(const Element &a, const Element &b) const
Adds elements in the group.
Definition: algebra.h:407
const char * source
Definition: rpcconsole.cpp:60
bool IsUnit() const
only 1 is a unit
Definition: gf2n.h:223
const EuclideanDomain & GetDomain() const
Definition: algebra.h:395
QuotientRing(const EuclideanDomain &domain, const Element &modulus)
Definition: algebra.h:392
Element & Accumulate(Element &a, const Element &b) const
TODO.
Definition: algebra.h:213
bool IsUnit(const Element &a) const
Determines whether an element is a unit in the group.
Definition: algebra.h:425
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
Definition: algebra.h:431
Multiple precision integer with arithmetic operations.
Definition: integer.h:43
bool operator==(const QuotientRing< T > &rhs) const
Definition: algebra.h:439
void Divide(word *R, word *Q, word *T, const word *A, size_t NA, const word *B, size_t NB)
Definition: integer.cpp:2692
Element & Reduce(Element &a, const Element &b) const
Reduces an element in the congruence class.
Definition: algebra.h:419
const Element & GetModulus() const
Definition: algebra.h:398
const Element & Identity() const
Provides the Identity element.
Definition: algebra.h:325
Element GeneralCascadeExponentiation(const AbstractRing< Element > &ring, Iterator begin, Iterator end)
Definition: algebra.cpp:328
bool operator==(const EuclideanDomainOf< T > &rhs) const
Definition: algebra.h:370
#define b(i, j)
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
Definition: algebra.h:358
Element ScalarMultiply(const Element &a, const Integer &e) const
Performs a scalar multiplication.
Definition: algebra.h:228
Abstract group.
Definition: algebra.h:26
AbstractRing(const AbstractRing &source)
Copy construct an AbstractRing.
Definition: algebra.h:128
const Element & Inverse(const Element &a) const
Inverts the element in the group.
Definition: algebra.h:413
#define CRYPTOPP_NO_VTABLE
Definition: config.h:369
const Element & Add(const Element &a, const Element &b) const
Adds elements in the group.
Definition: algebra.h:210
MultiplicativeGroupT m_mg
Definition: algebra.h:240
bool Equal(const Element &a, const Element &b) const
Compare two elements for equality.
Definition: algebra.h:322
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
Definition: algebra.h:349
const Element & Subtract(const Element &a, const Element &b) const
Subtracts elements in the group.
Definition: algebra.h:337
#define CRYPTOPP_UNUSED(x)
Definition: config.h:741
void Multiply(word *R, word *T, const word *A, const word *B, size_t N)
Definition: integer.cpp:2324
const Element & Double(const Element &a) const
Doubles an element in the group.
Definition: algebra.h:343
Multiple precision integer with arithmetic operations.
void Square(word *R, word *T, const word *A, size_t N)
Definition: integer.cpp:2329
virtual ~AbstractGroup()
Definition: algebra.h:31
Euclidean domain.
Definition: algebra.h:315
#define NAMESPACE_END
Definition: config.h:201
Base and exponent.
Definition: algebra.h:249
#define e(i)
Definition: sha.cpp:733
Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition: algebra.h:231
const Element & Add(const Element &a, const Element &b) const
Adds elements in the group.
Definition: algebra.h:328
int Subtract(word *C, const word *A, const word *B, size_t N)
Definition: integer.cpp:2152
#define d(i)
Definition: sha.cpp:732
void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
Definition: algebra.h:234
const Element & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Definition: algebra.h:346
Element result
Definition: algebra.h:374
const Element & Square(const Element &a) const
Square an element in the group.
Definition: algebra.h:352
const Element & Divide(const Element &a, const Element &b) const
Divides elements in the group.
Definition: algebra.h:361
const AbstractRing< T > * m_pRing
Definition: algebra.h:237
const Element & Double(const Element &a) const
Doubles an element in the group.
Definition: algebra.h:422
const Element & Double(const Element &a) const
Doubles an element in the group.
Definition: algebra.h:225
T EuclideanDomain
Definition: algebra.h:389
bool Equal(const Element &a, const Element &b) const
Compare two elements for equality.
Definition: algebra.h:204
T::Element Element
Definition: algebra.h:390
bool IsUnit(const Element &a) const
Determines whether an element is a unit in the group.
Definition: algebra.h:355