Crypto++
algebra.h
1 #ifndef CRYPTOPP_ALGEBRA_H
2 #define CRYPTOPP_ALGEBRA_H
3 
4 #include "config.h"
5 
6 NAMESPACE_BEGIN(CryptoPP)
7 
8 class Integer;
9 
10 // "const Element&" returned by member functions are references
11 // to internal data members. Since each object may have only
12 // one such data member for holding results, the following code
13 // will produce incorrect results:
14 // abcd = group.Add(group.Add(a,b), group.Add(c,d));
15 // But this should be fine:
16 // abcd = group.Add(a, group.Add(b, group.Add(c,d));
17 
18 //! Abstract Group
19 template <class T> class CRYPTOPP_NO_VTABLE AbstractGroup
20 {
21 public:
22  typedef T Element;
23 
24  virtual ~AbstractGroup() {}
25 
26  virtual bool Equal(const Element &a, const Element &b) const =0;
27  virtual const Element& Identity() const =0;
28  virtual const Element& Add(const Element &a, const Element &b) const =0;
29  virtual const Element& Inverse(const Element &a) const =0;
30  virtual bool InversionIsFast() const {return false;}
31 
32  virtual const Element& Double(const Element &a) const;
33  virtual const Element& Subtract(const Element &a, const Element &b) const;
34  virtual Element& Accumulate(Element &a, const Element &b) const;
35  virtual Element& Reduce(Element &a, const Element &b) const;
36 
37  virtual Element ScalarMultiply(const Element &a, const Integer &e) const;
38  virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
39 
40  virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
41 };
42 
43 //! Abstract Ring
44 template <class T> class CRYPTOPP_NO_VTABLE AbstractRing : public AbstractGroup<T>
45 {
46 public:
47  typedef T Element;
48 
49  AbstractRing() {m_mg.m_pRing = this;}
50  AbstractRing(const AbstractRing &source) {m_mg.m_pRing = this;}
51  AbstractRing& operator=(const AbstractRing &source) {return *this;}
52 
53  virtual bool IsUnit(const Element &a) const =0;
54  virtual const Element& MultiplicativeIdentity() const =0;
55  virtual const Element& Multiply(const Element &a, const Element &b) const =0;
56  virtual const Element& MultiplicativeInverse(const Element &a) const =0;
57 
58  virtual const Element& Square(const Element &a) const;
59  virtual const Element& Divide(const Element &a, const Element &b) const;
60 
61  virtual Element Exponentiate(const Element &a, const Integer &e) const;
62  virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
63 
64  virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
65 
66  virtual const AbstractGroup<T>& MultiplicativeGroup() const
67  {return m_mg;}
68 
69 private:
70  class MultiplicativeGroupT : public AbstractGroup<T>
71  {
72  public:
73  const AbstractRing<T>& GetRing() const
74  {return *m_pRing;}
75 
76  bool Equal(const Element &a, const Element &b) const
77  {return GetRing().Equal(a, b);}
78 
79  const Element& Identity() const
80  {return GetRing().MultiplicativeIdentity();}
81 
82  const Element& Add(const Element &a, const Element &b) const
83  {return GetRing().Multiply(a, b);}
84 
85  Element& Accumulate(Element &a, const Element &b) const
86  {return a = GetRing().Multiply(a, b);}
87 
88  const Element& Inverse(const Element &a) const
89  {return GetRing().MultiplicativeInverse(a);}
90 
91  const Element& Subtract(const Element &a, const Element &b) const
92  {return GetRing().Divide(a, b);}
93 
94  Element& Reduce(Element &a, const Element &b) const
95  {return a = GetRing().Divide(a, b);}
96 
97  const Element& Double(const Element &a) const
98  {return GetRing().Square(a);}
99 
100  Element ScalarMultiply(const Element &a, const Integer &e) const
101  {return GetRing().Exponentiate(a, e);}
102 
103  Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
104  {return GetRing().CascadeExponentiate(x, e1, y, e2);}
105 
106  void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
107  {GetRing().SimultaneousExponentiate(results, base, exponents, exponentsCount);}
108 
109  const AbstractRing<T> *m_pRing;
110  };
111 
112  MultiplicativeGroupT m_mg;
113 };
114 
115 // ********************************************************
116 
117 //! Base and Exponent
118 template <class T, class E = Integer>
120 {
121 public:
122  BaseAndExponent() {}
123  BaseAndExponent(const T &base, const E &exponent) : base(base), exponent(exponent) {}
124  bool operator<(const BaseAndExponent<T, E> &rhs) const {return exponent < rhs.exponent;}
125  T base;
126  E exponent;
127 };
128 
129 // VC60 workaround: incomplete member template support
130 template <class Element, class Iterator>
131  Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end);
132 template <class Element, class Iterator>
133  Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end);
134 
135 // ********************************************************
136 
137 //! Abstract Euclidean Domain
138 template <class T> class CRYPTOPP_NO_VTABLE AbstractEuclideanDomain : public AbstractRing<T>
139 {
140 public:
141  typedef T Element;
142 
143  virtual void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const =0;
144 
145  virtual const Element& Mod(const Element &a, const Element &b) const =0;
146  virtual const Element& Gcd(const Element &a, const Element &b) const;
147 
148 protected:
149  mutable Element result;
150 };
151 
152 // ********************************************************
153 
154 //! EuclideanDomainOf
155 template <class T> class EuclideanDomainOf : public AbstractEuclideanDomain<T>
156 {
157 public:
158  typedef T Element;
159 
160  EuclideanDomainOf() {}
161 
162  bool Equal(const Element &a, const Element &b) const
163  {return a==b;}
164 
165  const Element& Identity() const
166  {return Element::Zero();}
167 
168  const Element& Add(const Element &a, const Element &b) const
169  {return result = a+b;}
170 
171  Element& Accumulate(Element &a, const Element &b) const
172  {return a+=b;}
173 
174  const Element& Inverse(const Element &a) const
175  {return result = -a;}
176 
177  const Element& Subtract(const Element &a, const Element &b) const
178  {return result = a-b;}
179 
180  Element& Reduce(Element &a, const Element &b) const
181  {return a-=b;}
182 
183  const Element& Double(const Element &a) const
184  {return result = a.Doubled();}
185 
186  const Element& MultiplicativeIdentity() const
187  {return Element::One();}
188 
189  const Element& Multiply(const Element &a, const Element &b) const
190  {return result = a*b;}
191 
192  const Element& Square(const Element &a) const
193  {return result = a.Squared();}
194 
195  bool IsUnit(const Element &a) const
196  {return a.IsUnit();}
197 
198  const Element& MultiplicativeInverse(const Element &a) const
199  {return result = a.MultiplicativeInverse();}
200 
201  const Element& Divide(const Element &a, const Element &b) const
202  {return result = a/b;}
203 
204  const Element& Mod(const Element &a, const Element &b) const
205  {return result = a%b;}
206 
207  void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
208  {Element::Divide(r, q, a, d);}
209 
210  bool operator==(const EuclideanDomainOf<T> &rhs) const
211  {return true;}
212 
213 private:
214  mutable Element result;
215 };
216 
217 //! Quotient Ring
218 template <class T> class QuotientRing : public AbstractRing<typename T::Element>
219 {
220 public:
221  typedef T EuclideanDomain;
222  typedef typename T::Element Element;
223 
224  QuotientRing(const EuclideanDomain &domain, const Element &modulus)
225  : m_domain(domain), m_modulus(modulus) {}
226 
227  const EuclideanDomain & GetDomain() const
228  {return m_domain;}
229 
230  const Element& GetModulus() const
231  {return m_modulus;}
232 
233  bool Equal(const Element &a, const Element &b) const
234  {return m_domain.Equal(m_domain.Mod(m_domain.Subtract(a, b), m_modulus), m_domain.Identity());}
235 
236  const Element& Identity() const
237  {return m_domain.Identity();}
238 
239  const Element& Add(const Element &a, const Element &b) const
240  {return m_domain.Add(a, b);}
241 
242  Element& Accumulate(Element &a, const Element &b) const
243  {return m_domain.Accumulate(a, b);}
244 
245  const Element& Inverse(const Element &a) const
246  {return m_domain.Inverse(a);}
247 
248  const Element& Subtract(const Element &a, const Element &b) const
249  {return m_domain.Subtract(a, b);}
250 
251  Element& Reduce(Element &a, const Element &b) const
252  {return m_domain.Reduce(a, b);}
253 
254  const Element& Double(const Element &a) const
255  {return m_domain.Double(a);}
256 
257  bool IsUnit(const Element &a) const
258  {return m_domain.IsUnit(m_domain.Gcd(a, m_modulus));}
259 
260  const Element& MultiplicativeIdentity() const
261  {return m_domain.MultiplicativeIdentity();}
262 
263  const Element& Multiply(const Element &a, const Element &b) const
264  {return m_domain.Mod(m_domain.Multiply(a, b), m_modulus);}
265 
266  const Element& Square(const Element &a) const
267  {return m_domain.Mod(m_domain.Square(a), m_modulus);}
268 
269  const Element& MultiplicativeInverse(const Element &a) const;
270 
271  bool operator==(const QuotientRing<T> &rhs) const
272  {return m_domain == rhs.m_domain && m_modulus == rhs.m_modulus;}
273 
274 protected:
275  EuclideanDomain m_domain;
276  Element m_modulus;
277 };
278 
279 NAMESPACE_END
280 
281 #ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES
282 #include "algebra.cpp"
283 #endif
284 
285 #endif
Abstract Euclidean Domain.
Definition: algebra.h:138
Square
Definition: square.h:19
Quotient Ring.
Definition: algebra.h:218
Abstract Ring.
Definition: algebra.h:44
multiple precision integer and basic arithmetics
Definition: integer.h:26
Abstract Group.
Definition: algebra.h:19
EuclideanDomainOf.
Definition: algebra.h:155
Base and Exponent.
Definition: algebra.h:119