Crypto++

- Main Page
- Namespaces
- Classes
- Files

- File List
- 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 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