1#ifndef CRYPTOPP_ALGEBRA_H 2#define CRYPTOPP_ALGEBRA_H 3 4#include "config.h" 5 6NAMESPACE_BEGIN(CryptoPP) 7 8class 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 19template <class T> class CRYPTOPP_NO_VTABLE AbstractGroup 20{ 21public: 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 44template <class T> class CRYPTOPP_NO_VTABLE AbstractRing : public AbstractGroup<T> 45{ 46public: 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 69private: 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 118template <class T, class E = Integer> 119struct BaseAndExponent 120{ 121public: 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 130template <class Element, class Iterator> 131 Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end); 132template <class Element, class Iterator> 133 Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end); 134 135// ******************************************************** 136 137//! Abstract Euclidean Domain 138template <class T> class CRYPTOPP_NO_VTABLE AbstractEuclideanDomain : public AbstractRing<T> 139{ 140public: 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 148protected: 149 mutable Element result; 150}; 151 152// ******************************************************** 153 154//! EuclideanDomainOf 155template <class T> class EuclideanDomainOf : public AbstractEuclideanDomain<T> 156{ 157public: 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 213private: 214 mutable Element result; 215}; 216 217//! Quotient Ring 218template <class T> class QuotientRing : public AbstractRing<typename T::Element> 219{ 220public: 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 274protected: 275 EuclideanDomain m_domain; 276 Element m_modulus; 277}; 278 279NAMESPACE_END 280 281#ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES 282#include "algebra.cpp" 283#endif 284 285#endif 286