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