include/cryptopp/algebra.h

0001 // algebra.h - originally written and placed in the public domain by Wei Dai

0002
0003 /// \file algebra.h

0004 /// \brief Classes for performing mathematics over different fields

0005
0006 #ifndef CRYPTOPP_ALGEBRA_H
0007 #define CRYPTOPP_ALGEBRA_H
0008
0009 #include "config.h"
0010 #include "integer.h"
0011 #include "misc.h"
0012
0013 NAMESPACE_BEGIN(CryptoPP)
0014
0015 class Integer;
0016
0017 /// \brief Abstract group

0018 /// \tparam T element class or type

0019 /// \details <tt>const Element&</tt> returned by member functions are references

0020 ///   to internal data members. Since each object may have only

0021 ///   one such data member for holding results, the following code

0022 ///   will produce incorrect results:

0023 ///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>

0024 ///   But this should be fine:

0025 ///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>

0026 template <class T> class CRYPTOPP_NO_VTABLE AbstractGroup
0027 {
0028 public:
0029     typedef T Element;
0030
0031     virtual ~AbstractGroup() {}
0032
0033     /// \brief Compare two elements for equality

0034     /// \param a first element

0035     /// \param b second element

0036     /// \return true if the elements are equal, false otherwise

0037     /// \details Equal() tests the elements for equality using <tt>a==b</tt>

0038     virtual bool Equal(const Element &a, const Element &b) const =0;
0039
0040     /// \brief Provides the Identity element

0041     /// \return the Identity element

0042     virtual const Element& Identity() const =0;
0043
0044     /// \brief Adds elements in the group

0045     /// \param a first element

0046     /// \param b second element

0047     /// \return the sum of <tt>a</tt> and <tt>b</tt>

0048     virtual const Element& Add(const Element &a, const Element &b) const =0;
0049
0050     /// \brief Inverts the element in the group

0051     /// \param a first element

0052     /// \return the inverse of the element

0053     virtual const Element& Inverse(const Element &a) const =0;
0054
0055     /// \brief Determine if inversion is fast

0056     /// \return true if inversion is fast, false otherwise

0057     virtual bool InversionIsFast() const {return false;}
0058
0059     /// \brief Doubles an element in the group

0060     /// \param a the element

0061     /// \return the element doubled

0062     virtual const Element& Double(const Element &a) const;
0063
0064     /// \brief Subtracts elements in the group

0065     /// \param a first element

0066     /// \param b second element

0067     /// \return the difference of <tt>a</tt> and <tt>b</tt>. The element <tt>a</tt> must provide a Subtract member function.

0068     virtual const Element& Subtract(const Element &a, const Element &b) const;
0069
0070     /// \brief TODO

0071     /// \param a first element

0072     /// \param b second element

0073     /// \return TODO

0074     virtual Element& Accumulate(Element &a, const Element &b) const;
0075
0076     /// \brief Reduces an element in the congruence class

0077     /// \param a element to reduce

0078     /// \param b the congruence class

0079     /// \return the reduced element

0080     virtual Element& Reduce(Element &a, const Element &b) const;
0081
0082     /// \brief Performs a scalar multiplication

0083     /// \param a multiplicand

0084     /// \param e multiplier

0085     /// \return the product

0086     virtual Element ScalarMultiply(const Element &a, const Integer &e) const;
0087
0088     /// \brief TODO

0089     /// \param x first multiplicand

0090     /// \param e1 the first multiplier

0091     /// \param y second multiplicand

0092     /// \param e2 the second multiplier

0093     /// \return TODO

0094     virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
0095
0096     /// \brief Multiplies a base to multiple exponents in a group

0097     /// \param results an array of Elements

0098     /// \param base the base to raise to the exponents

0099     /// \param exponents an array of exponents

0100     /// \param exponentsCount the number of exponents in the array

0101     /// \details SimultaneousMultiply() multiplies the base to each exponent in the exponents array and stores the

0102     ///   result at the respective position in the results array.

0103     /// \details SimultaneousMultiply() must be implemented in a derived class.

0104     /// \pre <tt>COUNTOF(results) == exponentsCount</tt>

0105     /// \pre <tt>COUNTOF(exponents) == exponentsCount</tt>

0106     virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
0107 };
0108
0109 /// \brief Abstract ring

0110 /// \tparam T element class or type

0111 /// \details <tt>const Element&</tt> returned by member functions are references

0112 ///   to internal data members. Since each object may have only

0113 ///   one such data member for holding results, the following code

0114 ///   will produce incorrect results:

0115 ///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>

0116 ///   But this should be fine:

0117 ///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>

0118 template <class T> class CRYPTOPP_NO_VTABLE AbstractRing : public AbstractGroup<T>
0119 {
0120 public:
0121     typedef T Element;
0122
0123     /// \brief Construct an AbstractRing

0124     AbstractRing() {m_mg.m_pRing = this;}
0125
0126     /// \brief Copy construct an AbstractRing

0127     /// \param source other AbstractRing

0128     AbstractRing(const AbstractRing &source)
0129         {CRYPTOPP_UNUSED(source); m_mg.m_pRing = this;}
0130
0131     /// \brief Assign an AbstractRing

0132     /// \param source other AbstractRing

0133     AbstractRing& operator=(const AbstractRing &source)
0134         {CRYPTOPP_UNUSED(source); return *this;}
0135
0136     /// \brief Determines whether an element is a unit in the group

0137     /// \param a the element

0138     /// \return true if the element is a unit after reduction, false otherwise.

0139     virtual bool IsUnit(const Element &a) const =0;
0140
0141     /// \brief Retrieves the multiplicative identity

0142     /// \return the multiplicative identity

0143     virtual const Element& MultiplicativeIdentity() const =0;
0144
0145     /// \brief Multiplies elements in the group

0146     /// \param a the multiplicand

0147     /// \param b the multiplier

0148     /// \return the product of a and b

0149     virtual const Element& Multiply(const Element &a, const Element &b) const =0;
0150
0151     /// \brief Calculate the multiplicative inverse of an element in the group

0152     /// \param a the element

0153     virtual const Element& MultiplicativeInverse(const Element &a) const =0;
0154
0155     /// \brief Square an element in the group

0156     /// \param a the element

0157     /// \return the element squared

0158     virtual const Element& Square(const Element &a) const;
0159
0160     /// \brief Divides elements in the group

0161     /// \param a the dividend

0162     /// \param b the divisor

0163     /// \return the quotient

0164     virtual const Element& Divide(const Element &a, const Element &b) const;
0165
0166     /// \brief Raises a base to an exponent in the group

0167     /// \param a the base

0168     /// \param e the exponent

0169     /// \return the exponentiation

0170     virtual Element Exponentiate(const Element &a, const Integer &e) const;
0171
0172     /// \brief TODO

0173     /// \param x first element

0174     /// \param e1 first exponent

0175     /// \param y second element

0176     /// \param e2 second exponent

0177     /// \return TODO

0178     virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
0179
0180     /// \brief Exponentiates a base to multiple exponents in the Ring

0181     /// \param results an array of Elements

0182     /// \param base the base to raise to the exponents

0183     /// \param exponents an array of exponents

0184     /// \param exponentsCount the number of exponents in the array

0185     /// \details SimultaneousExponentiate() raises the base to each exponent in the exponents array and stores the

0186     ///   result at the respective position in the results array.

0187     /// \details SimultaneousExponentiate() must be implemented in a derived class.

0188     /// \pre <tt>COUNTOF(results) == exponentsCount</tt>

0189     /// \pre <tt>COUNTOF(exponents) == exponentsCount</tt>

0190     virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
0191
0192     /// \brief Retrieves the multiplicative group

0193     /// \return the multiplicative group

0194     virtual const AbstractGroup<T>& MultiplicativeGroup() const
0195         {return m_mg;}
0196
0197 private:
0198     class MultiplicativeGroupT : public AbstractGroup<T>
0199     {
0200     public:
0201         const AbstractRing<T>& GetRing() const
0202             {return *m_pRing;}
0203
0204         bool Equal(const Element &a, const Element &b) const
0205             {return GetRing().Equal(a, b);}
0206
0207         const Element& Identity() const
0208             {return GetRing().MultiplicativeIdentity();}
0209
0210         const Element& Add(const Element &a, const Element &b) const
0211             {return GetRing().Multiply(a, b);}
0212
0213         Element& Accumulate(Element &a, const Element &b) const
0214             {return a = GetRing().Multiply(a, b);}
0215
0216         const Element& Inverse(const Element &a) const
0217             {return GetRing().MultiplicativeInverse(a);}
0218
0219         const Element& Subtract(const Element &a, const Element &b) const
0220             {return GetRing().Divide(a, b);}
0221
0222         Element& Reduce(Element &a, const Element &b) const
0223             {return a = GetRing().Divide(a, b);}
0224
0225         const Element& Double(const Element &a) const
0226             {return GetRing().Square(a);}
0227
0228         Element ScalarMultiply(const Element &a, const Integer &e) const
0229             {return GetRing().Exponentiate(a, e);}
0230
0231         Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
0232             {return GetRing().CascadeExponentiate(x, e1, y, e2);}
0233
0234         void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
0235             {GetRing().SimultaneousExponentiate(results, base, exponents, exponentsCount);}
0236
0237         const AbstractRing<T> *m_pRing;
0238     };
0239
0240     MultiplicativeGroupT m_mg;
0241 };
0242
0243 // ********************************************************

0244
0245 /// \brief Base and exponent

0246 /// \tparam T base class or type

0247 /// \tparam E exponent class or type

0248 template <class T, class E = Integer>
0249 struct BaseAndExponent
0250 {
0251 public:
0252     BaseAndExponent() {}
0253     BaseAndExponent(const T &base, const E &exponent) : base(base), exponent(exponent) {}
0254     bool operator<(const BaseAndExponent<T, E> &rhs) const {return exponent < rhs.exponent;}
0255     T base;
0256     E exponent;
0257 };
0258
0259 // VC60 workaround: incomplete member template support

0260 template <class Element, class Iterator>
0261     Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end);
0262 template <class Element, class Iterator>
0263     Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end);
0264
0265 // ********************************************************

0266
0267 /// \brief Abstract Euclidean domain

0268 /// \tparam T element class or type

0269 /// \details <tt>const Element&</tt> returned by member functions are references

0270 ///   to internal data members. Since each object may have only

0271 ///   one such data member for holding results, the following code

0272 ///   will produce incorrect results:

0273 ///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>

0274 ///   But this should be fine:

0275 ///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>

0276 template <class T> class CRYPTOPP_NO_VTABLE AbstractEuclideanDomain : public AbstractRing<T>
0277 {
0278 public:
0279     typedef T Element;
0280
0281     /// \brief Performs the division algorithm on two elements in the ring

0282     /// \param r the remainder

0283     /// \param q the quotient

0284     /// \param a the dividend

0285     /// \param d the divisor

0286     virtual void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const =0;
0287
0288     /// \brief Performs a modular reduction in the ring

0289     /// \param a the element

0290     /// \param b the modulus

0291     /// \return the result of <tt>a%b</tt>.

0292     virtual const Element& Mod(const Element &a, const Element &b) const =0;
0293
0294     /// \brief Calculates the greatest common denominator in the ring

0295     /// \param a the first element

0296     /// \param b the second element

0297     /// \return the greatest common denominator of a and b.

0298     virtual const Element& Gcd(const Element &a, const Element &b) const;
0299
0300 protected:
0301     mutable Element result;
0302 };
0303
0304 // ********************************************************

0305
0306 /// \brief Euclidean domain

0307 /// \tparam T element class or type

0308 /// \details <tt>const Element&</tt> returned by member functions are references

0309 ///   to internal data members. Since each object may have only

0310 ///   one such data member for holding results, the following code

0311 ///   will produce incorrect results:

0312 ///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>

0313 ///   But this should be fine:

0314 ///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>

0315 template <class T> class EuclideanDomainOf : public AbstractEuclideanDomain<T>
0316 {
0317 public:
0318     typedef T Element;
0319
0320     EuclideanDomainOf() {}
0321
0322     bool Equal(const Element &a, const Element &b) const
0323         {return a==b;}
0324
0325     const Element& Identity() const
0326         {return Element::Zero();}
0327
0328     const Element& Add(const Element &a, const Element &b) const
0329         {return result = a+b;}
0330
0331     Element& Accumulate(Element &a, const Element &b) const
0332         {return a+=b;}
0333
0334     const Element& Inverse(const Element &a) const
0335         {return result = -a;}
0336
0337     const Element& Subtract(const Element &a, const Element &b) const
0338         {return result = a-b;}
0339
0340     Element& Reduce(Element &a, const Element &b) const
0341         {return a-=b;}
0342
0343     const Element& Double(const Element &a) const
0344         {return result = a.Doubled();}
0345
0346     const Element& MultiplicativeIdentity() const
0347         {return Element::One();}
0348
0349     const Element& Multiply(const Element &a, const Element &b) const
0350         {return result = a*b;}
0351
0352     const Element& Square(const Element &a) const
0353         {return result = a.Squared();}
0354
0355     bool IsUnit(const Element &a) const
0356         {return a.IsUnit();}
0357
0358     const Element& MultiplicativeInverse(const Element &a) const
0359         {return result = a.MultiplicativeInverse();}
0360
0361     const Element& Divide(const Element &a, const Element &b) const
0362         {return result = a/b;}
0363
0364     const Element& Mod(const Element &a, const Element &b) const
0365         {return result = a%b;}
0366
0367     void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
0368         {Element::Divide(r, q, a, d);}
0369
0370     bool operator==(const EuclideanDomainOf<T> &rhs) const
0371         {CRYPTOPP_UNUSED(rhs); return true;}
0372
0373 private:
0374     mutable Element result;
0375 };
0376
0377 /// \brief Quotient ring

0378 /// \tparam T element class or type

0379 /// \details <tt>const Element&</tt> returned by member functions are references

0380 ///   to internal data members. Since each object may have only

0381 ///   one such data member for holding results, the following code

0382 ///   will produce incorrect results:

0383 ///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>

0384 ///   But this should be fine:

0385 ///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>

0386 template <class T> class QuotientRing : public AbstractRing<typename T::Element>
0387 {
0388 public:
0389     typedef T EuclideanDomain;
0390     typedef typename T::Element Element;
0391
0392     QuotientRing(const EuclideanDomain &domain, const Element &modulus)
0393         : m_domain(domain), m_modulus(modulus) {}
0394
0395     const EuclideanDomain & GetDomain() const
0396         {return m_domain;}
0397
0398     const Element& GetModulus() const
0399         {return m_modulus;}
0400
0401     bool Equal(const Element &a, const Element &b) const
0402         {return m_domain.Equal(m_domain.Mod(m_domain.Subtract(a, b), m_modulus), m_domain.Identity());}
0403
0404     const Element& Identity() const
0405         {return m_domain.Identity();}
0406
0407     const Element& Add(const Element &a, const Element &b) const
0408         {return m_domain.Add(a, b);}
0409
0410     Element& Accumulate(Element &a, const Element &b) const
0411         {return m_domain.Accumulate(a, b);}
0412
0413     const Element& Inverse(const Element &a) const
0414         {return m_domain.Inverse(a);}
0415
0416     const Element& Subtract(const Element &a, const Element &b) const
0417         {return m_domain.Subtract(a, b);}
0418
0419     Element& Reduce(Element &a, const Element &b) const
0420         {return m_domain.Reduce(a, b);}
0421
0422     const Element& Double(const Element &a) const
0423         {return m_domain.Double(a);}
0424
0425     bool IsUnit(const Element &a) const
0426         {return m_domain.IsUnit(m_domain.Gcd(a, m_modulus));}
0427
0428     const Element& MultiplicativeIdentity() const
0429         {return m_domain.MultiplicativeIdentity();}
0430
0431     const Element& Multiply(const Element &a, const Element &b) const
0432         {return m_domain.Mod(m_domain.Multiply(a, b), m_modulus);}
0433
0434     const Element& Square(const Element &a) const
0435         {return m_domain.Mod(m_domain.Square(a), m_modulus);}
0436
0437     const Element& MultiplicativeInverse(const Element &a) const;
0438
0439     bool operator==(const QuotientRing<T> &rhs) const
0440         {return m_domain == rhs.m_domain && m_modulus == rhs.m_modulus;}
0441
0442 protected:
0443     EuclideanDomain m_domain;
0444     Element m_modulus;
0445 };
0446
0447 NAMESPACE_END
0448
0449 #ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES
0450 #include "algebra.cpp"
0451 #endif
0452
0453 #endif