1 #ifndef CRYPTOPP_ALGEBRA_H
2 #define CRYPTOPP_ALGEBRA_H
6 NAMESPACE_BEGIN(CryptoPP)
24 virtual ~AbstractGroup() {}
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;}
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;
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;
40 virtual void SimultaneousMultiply(Element *results,
const Element &base,
const Integer *exponents,
unsigned int exponentsCount)
const;
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;
58 virtual const Element&
Square(
const Element &a)
const;
59 virtual const Element& Divide(
const Element &a,
const Element &b)
const;
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;
64 virtual void SimultaneousExponentiate(Element *results,
const Element &base,
const Integer *exponents,
unsigned int exponentsCount)
const;
76 bool Equal(
const Element &a,
const Element &b)
const
77 {
return GetRing().Equal(a, b);}
79 const Element& Identity()
const
80 {
return GetRing().MultiplicativeIdentity();}
82 const Element& Add(
const Element &a,
const Element &b)
const
83 {
return GetRing().Multiply(a, b);}
85 Element& Accumulate(Element &a,
const Element &b)
const
86 {
return a = GetRing().Multiply(a, b);}
88 const Element& Inverse(
const Element &a)
const
89 {
return GetRing().MultiplicativeInverse(a);}
91 const Element& Subtract(
const Element &a,
const Element &b)
const
92 {
return GetRing().Divide(a, b);}
94 Element& Reduce(Element &a,
const Element &b)
const
95 {
return a = GetRing().Divide(a, b);}
97 const Element& Double(
const Element &a)
const
98 {
return GetRing().Square(a);}
100 Element ScalarMultiply(
const Element &a,
const Integer &e)
const
101 {
return GetRing().Exponentiate(a, e);}
103 Element CascadeScalarMultiply(
const Element &x,
const Integer &e1,
const Element &y,
const Integer &e2)
const
104 {
return GetRing().CascadeExponentiate(x, e1, y, e2);}
106 void SimultaneousMultiply(Element *results,
const Element &base,
const Integer *exponents,
unsigned int exponentsCount)
const
107 {GetRing().SimultaneousExponentiate(results, base, exponents, exponentsCount);}
112 MultiplicativeGroupT m_mg;
118 template <
class T,
class E = Integer>
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;}
130 template <
class Element,
class Iterator>
132 template <
class Element,
class Iterator>
133 Element GeneralCascadeExponentiation(
const AbstractRing<Element> &ring, Iterator begin, Iterator end);
143 virtual void DivisionAlgorithm(Element &r, Element &q,
const Element &a,
const Element &d)
const =0;
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;
149 mutable Element result;
162 bool Equal(
const Element &a,
const Element &b)
const
165 const Element& Identity()
const
166 {
return Element::Zero();}
168 const Element& Add(
const Element &a,
const Element &b)
const
169 {
return result = a+b;}
171 Element& Accumulate(Element &a,
const Element &b)
const
174 const Element& Inverse(
const Element &a)
const
175 {
return result = -a;}
177 const Element& Subtract(
const Element &a,
const Element &b)
const
178 {
return result = a-b;}
180 Element& Reduce(Element &a,
const Element &b)
const
183 const Element& Double(
const Element &a)
const
184 {
return result = a.Doubled();}
186 const Element& MultiplicativeIdentity()
const
187 {
return Element::One();}
189 const Element& Multiply(
const Element &a,
const Element &b)
const
190 {
return result = a*b;}
192 const Element&
Square(
const Element &a)
const
193 {
return result = a.Squared();}
195 bool IsUnit(
const Element &a)
const
198 const Element& MultiplicativeInverse(
const Element &a)
const
199 {
return result = a.MultiplicativeInverse();}
201 const Element& Divide(
const Element &a,
const Element &b)
const
202 {
return result = a/b;}
204 const Element& Mod(
const Element &a,
const Element &b)
const
205 {
return result = a%b;}
207 void DivisionAlgorithm(Element &r, Element &q,
const Element &a,
const Element &d)
const
208 {Element::Divide(r, q, a, d);}
214 mutable Element result;
221 typedef T EuclideanDomain;
222 typedef typename T::Element Element;
224 QuotientRing(
const EuclideanDomain &domain,
const Element &modulus)
225 : m_domain(domain), m_modulus(modulus) {}
227 const EuclideanDomain & GetDomain()
const
230 const Element& GetModulus()
const
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());}
236 const Element& Identity()
const
237 {
return m_domain.Identity();}
239 const Element& Add(
const Element &a,
const Element &b)
const
240 {
return m_domain.Add(a, b);}
242 Element& Accumulate(Element &a,
const Element &b)
const
243 {
return m_domain.Accumulate(a, b);}
245 const Element& Inverse(
const Element &a)
const
246 {
return m_domain.Inverse(a);}
248 const Element& Subtract(
const Element &a,
const Element &b)
const
249 {
return m_domain.Subtract(a, b);}
251 Element& Reduce(Element &a,
const Element &b)
const
252 {
return m_domain.Reduce(a, b);}
254 const Element& Double(
const Element &a)
const
255 {
return m_domain.Double(a);}
257 bool IsUnit(
const Element &a)
const
258 {
return m_domain.IsUnit(m_domain.Gcd(a, m_modulus));}
260 const Element& MultiplicativeIdentity()
const
261 {
return m_domain.MultiplicativeIdentity();}
263 const Element& Multiply(
const Element &a,
const Element &b)
const
264 {
return m_domain.Mod(m_domain.Multiply(a, b), m_modulus);}
266 const Element&
Square(
const Element &a)
const
267 {
return m_domain.Mod(m_domain.Square(a), m_modulus);}
269 const Element& MultiplicativeInverse(
const Element &a)
const;
272 {
return m_domain == rhs.m_domain && m_modulus == rhs.m_modulus;}
275 EuclideanDomain m_domain;
281 #ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES
282 #include "algebra.cpp"
Abstract Euclidean Domain.
multiple precision integer and basic arithmetics