Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

algebra.h

00001 #ifndef CRYPTOPP_ALGEBRA_H 00002 #define CRYPTOPP_ALGEBRA_H 00003 00004 #include "cryptopp_config.h" 00005 00006 NAMESPACE_BEGIN(CryptoPP) 00007 00008 class Integer; 00009 00010 // "const Element&" returned by member functions are references 00011 // to internal data members. Since each object may have only 00012 // one such data member for holding results, the following code 00013 // will produce incorrect results: 00014 // abcd = group.Add(group.Add(a,b), group.Add(c,d)); 00015 // But this should be fine: 00016 // abcd = group.Add(a, group.Add(b, group.Add(c,d)); 00017 00018 //! Abstract Group 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 //! Abstract Ring 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 //! Base and Exponent 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 // VC60 workaround: incomplete member template support 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 //! Abstract Euclidean Domain 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 //! EuclideanDomainOf 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 //! Quotient Ring 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 #endif

Generated on Fri Aug 27 21:58:19 2004 for Crypto++ by doxygen 1.3.8