00001 #ifndef CRYPTOPP_ALGEBRA_H
00002 #define CRYPTOPP_ALGEBRA_H
00003
00004 #include "config.h"
00005
00006 NAMESPACE_BEGIN(CryptoPP)
00007
00008 class Integer;
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 template <class T> class CRYPTOPP_NO_VTABLE AbstractGroup
00020 {
00021 public:
00022 typedef T Element;
00023
00024 virtual ~AbstractGroup() {}
00025
00026 virtual bool Equal(const Element &a, const Element &b) const =0;
00027 virtual const Element& Identity() const =0;
00028 virtual const Element& Add(const Element &a, const Element &b) const =0;
00029 virtual const Element& Inverse(const Element &a) const =0;
00030 virtual bool InversionIsFast() const {return false;}
00031
00032 virtual const Element& Double(const Element &a) const;
00033 virtual const Element& Subtract(const Element &a, const Element &b) const;
00034 virtual Element& Accumulate(Element &a, const Element &b) const;
00035 virtual Element& Reduce(Element &a, const Element &b) const;
00036
00037 virtual Element ScalarMultiply(const Element &a, const Integer &e) const;
00038 virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
00039
00040 virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
00041 };
00042
00043
00044 template <class T> class CRYPTOPP_NO_VTABLE AbstractRing : public AbstractGroup<T>
00045 {
00046 public:
00047 typedef T Element;
00048
00049 AbstractRing() {m_mg.m_pRing = this;}
00050 AbstractRing(const AbstractRing &source) {m_mg.m_pRing = this;}
00051 AbstractRing& operator=(const AbstractRing &source) {return *this;}
00052
00053 virtual bool IsUnit(const Element &a) const =0;
00054 virtual const Element& MultiplicativeIdentity() const =0;
00055 virtual const Element& Multiply(const Element &a, const Element &b) const =0;
00056 virtual const Element& MultiplicativeInverse(const Element &a) const =0;
00057
00058 virtual const Element& Square(const Element &a) const;
00059 virtual const Element& Divide(const Element &a, const Element &b) const;
00060
00061 virtual Element Exponentiate(const Element &a, const Integer &e) const;
00062 virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
00063
00064 virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
00065
00066 virtual const AbstractGroup<T>& MultiplicativeGroup() const
00067 {return m_mg;}
00068
00069 private:
00070 class MultiplicativeGroupT : public AbstractGroup<T>
00071 {
00072 public:
00073 const AbstractRing<T>& GetRing() const
00074 {return *m_pRing;}
00075
00076 bool Equal(const Element &a, const Element &b) const
00077 {return GetRing().Equal(a, b);}
00078
00079 const Element& Identity() const
00080 {return GetRing().MultiplicativeIdentity();}
00081
00082 const Element& Add(const Element &a, const Element &b) const
00083 {return GetRing().Multiply(a, b);}
00084
00085 Element& Accumulate(Element &a, const Element &b) const
00086 {return a = GetRing().Multiply(a, b);}
00087
00088 const Element& Inverse(const Element &a) const
00089 {return GetRing().MultiplicativeInverse(a);}
00090
00091 const Element& Subtract(const Element &a, const Element &b) const
00092 {return GetRing().Divide(a, b);}
00093
00094 Element& Reduce(Element &a, const Element &b) const
00095 {return a = GetRing().Divide(a, b);}
00096
00097 const Element& Double(const Element &a) const
00098 {return GetRing().Square(a);}
00099
00100 Element ScalarMultiply(const Element &a, const Integer &e) const
00101 {return GetRing().Exponentiate(a, e);}
00102
00103 Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
00104 {return GetRing().CascadeExponentiate(x, e1, y, e2);}
00105
00106 void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
00107 {GetRing().SimultaneousExponentiate(results, base, exponents, exponentsCount);}
00108
00109 const AbstractRing<T> *m_pRing;
00110 };
00111
00112 MultiplicativeGroupT m_mg;
00113 };
00114
00115
00116
00117
00118 template <class T, class E = Integer>
00119 struct BaseAndExponent
00120 {
00121 public:
00122 BaseAndExponent() {}
00123 BaseAndExponent(const T &base, const E &exponent) : base(base), exponent(exponent) {}
00124 bool operator<(const BaseAndExponent<T, E> &rhs) const {return exponent < rhs.exponent;}
00125 T base;
00126 E exponent;
00127 };
00128
00129
00130 template <class Element, class Iterator>
00131 Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end);
00132 template <class Element, class Iterator>
00133 Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end);
00134
00135
00136
00137
00138 template <class T> class CRYPTOPP_NO_VTABLE AbstractEuclideanDomain : public AbstractRing<T>
00139 {
00140 public:
00141 typedef T Element;
00142
00143 virtual void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const =0;
00144
00145 virtual const Element& Mod(const Element &a, const Element &b) const =0;
00146 virtual const Element& Gcd(const Element &a, const Element &b) const;
00147
00148 protected:
00149 mutable Element result;
00150 };
00151
00152
00153
00154
00155 template <class T> class EuclideanDomainOf : public AbstractEuclideanDomain<T>
00156 {
00157 public:
00158 typedef T Element;
00159
00160 EuclideanDomainOf() {}
00161
00162 bool Equal(const Element &a, const Element &b) const
00163 {return a==b;}
00164
00165 const Element& Identity() const
00166 {return Element::Zero();}
00167
00168 const Element& Add(const Element &a, const Element &b) const
00169 {return result = a+b;}
00170
00171 Element& Accumulate(Element &a, const Element &b) const
00172 {return a+=b;}
00173
00174 const Element& Inverse(const Element &a) const
00175 {return result = -a;}
00176
00177 const Element& Subtract(const Element &a, const Element &b) const
00178 {return result = a-b;}
00179
00180 Element& Reduce(Element &a, const Element &b) const
00181 {return a-=b;}
00182
00183 const Element& Double(const Element &a) const
00184 {return result = a.Doubled();}
00185
00186 const Element& MultiplicativeIdentity() const
00187 {return Element::One();}
00188
00189 const Element& Multiply(const Element &a, const Element &b) const
00190 {return result = a*b;}
00191
00192 const Element& Square(const Element &a) const
00193 {return result = a.Squared();}
00194
00195 bool IsUnit(const Element &a) const
00196 {return a.IsUnit();}
00197
00198 const Element& MultiplicativeInverse(const Element &a) const
00199 {return result = a.MultiplicativeInverse();}
00200
00201 const Element& Divide(const Element &a, const Element &b) const
00202 {return result = a/b;}
00203
00204 const Element& Mod(const Element &a, const Element &b) const
00205 {return result = a%b;}
00206
00207 void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
00208 {Element::Divide(r, q, a, d);}
00209
00210 bool operator==(const EuclideanDomainOf<T> &rhs) const
00211 {return true;}
00212
00213 private:
00214 mutable Element result;
00215 };
00216
00217
00218 template <class T> class QuotientRing : public AbstractRing<typename T::Element>
00219 {
00220 public:
00221 typedef T EuclideanDomain;
00222 typedef typename T::Element Element;
00223
00224 QuotientRing(const EuclideanDomain &domain, const Element &modulus)
00225 : m_domain(domain), m_modulus(modulus) {}
00226
00227 const EuclideanDomain & GetDomain() const
00228 {return m_domain;}
00229
00230 const Element& GetModulus() const
00231 {return m_modulus;}
00232
00233 bool Equal(const Element &a, const Element &b) const
00234 {return m_domain.Equal(m_domain.Mod(m_domain.Subtract(a, b), m_modulus), m_domain.Identity());}
00235
00236 const Element& Identity() const
00237 {return m_domain.Identity();}
00238
00239 const Element& Add(const Element &a, const Element &b) const
00240 {return m_domain.Add(a, b);}
00241
00242 Element& Accumulate(Element &a, const Element &b) const
00243 {return m_domain.Accumulate(a, b);}
00244
00245 const Element& Inverse(const Element &a) const
00246 {return m_domain.Inverse(a);}
00247
00248 const Element& Subtract(const Element &a, const Element &b) const
00249 {return m_domain.Subtract(a, b);}
00250
00251 Element& Reduce(Element &a, const Element &b) const
00252 {return m_domain.Reduce(a, b);}
00253
00254 const Element& Double(const Element &a) const
00255 {return m_domain.Double(a);}
00256
00257 bool IsUnit(const Element &a) const
00258 {return m_domain.IsUnit(m_domain.Gcd(a, m_modulus));}
00259
00260 const Element& MultiplicativeIdentity() const
00261 {return m_domain.MultiplicativeIdentity();}
00262
00263 const Element& Multiply(const Element &a, const Element &b) const
00264 {return m_domain.Mod(m_domain.Multiply(a, b), m_modulus);}
00265
00266 const Element& Square(const Element &a) const
00267 {return m_domain.Mod(m_domain.Square(a), m_modulus);}
00268
00269 const Element& MultiplicativeInverse(const Element &a) const;
00270
00271 bool operator==(const QuotientRing<T> &rhs) const
00272 {return m_domain == rhs.m_domain && m_modulus == rhs.m_modulus;}
00273
00274 protected:
00275 EuclideanDomain m_domain;
00276 Element m_modulus;
00277 };
00278
00279 NAMESPACE_END
00280
00281 #ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES
00282 #include "algebra.cpp"
00283 #endif
00284
00285 #endif