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