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