Crypto++
algebra.h
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 // "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 #ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES
00282 #include "algebra.cpp"
00283 #endif
00284 
00285 #endif