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

# 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 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 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 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 private:
    00211         mutable Element result;
    00212 };
    00213
    00214 //! Quotient Ring
    00215 template <class T> class QuotientRing : public AbstractRing<typename T::Element>
    00216 {
    00217 public:
    00218         typedef T EuclideanDomain;
    00219         typedef typename T::Element Element;
    00220
    00221         QuotientRing(const EuclideanDomain &domain, const Element &modulus)
    00222                 : m_domain(domain), m_modulus(modulus) {}
    00223
    00224         const EuclideanDomain & GetDomain() const
    00225                 {return m_domain;}
    00226
    00227         const Element& GetModulus() const
    00228                 {return m_modulus;}
    00229
    00230         bool Equal(const Element &a, const Element &b) const
    00231                 {return m_domain.Equal(m_domain.Mod(m_domain.Subtract(a, b), m_modulus), m_domain.Identity());}
    00232
    00233         const Element& Identity() const
    00234                 {return m_domain.Identity();}
    00235
    00236         const Element& Add(const Element &a, const Element &b) const
    00237                 {return m_domain.Add(a, b);}
    00238
    00239         Element& Accumulate(Element &a, const Element &b) const
    00240                 {return m_domain.Accumulate(a, b);}
    00241
    00242         const Element& Inverse(const Element &a) const
    00243                 {return m_domain.Inverse(a);}
    00244
    00245         const Element& Subtract(const Element &a, const Element &b) const
    00246                 {return m_domain.Subtract(a, b);}
    00247
    00248         Element& Reduce(Element &a, const Element &b) const
    00249                 {return m_domain.Reduce(a, b);}
    00250
    00251         const Element& Double(const Element &a) const
    00252                 {return m_domain.Double(a);}
    00253
    00254         bool IsUnit(const Element &a) const
    00255                 {return m_domain.IsUnit(m_domain.Gcd(a, m_modulus));}
    00256
    00257         const Element& MultiplicativeIdentity() const
    00258                 {return m_domain.MultiplicativeIdentity();}
    00259
    00260         const Element& Multiply(const Element &a, const Element &b) const
    00261                 {return m_domain.Mod(m_domain.Multiply(a, b), m_modulus);}
    00262
    00263         const Element& Square(const Element &a) const
    00264                 {return m_domain.Mod(m_domain.Square(a), m_modulus);}
    00265
    00266         const Element& MultiplicativeInverse(const Element &a) const;
    00267
    00268         bool operator==(const QuotientRing<T> &rhs) const
    00269                 {return m_modulus == rhs.m_modulus;}
    00270
    00271 protected:
    00272         EuclideanDomain m_domain;
    00273         Element m_modulus;
    00274 };
    00275
    00276 NAMESPACE_END
    00277
    00278 #endif