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
00011
00012
00013
00014
00015
00016
00017
00018
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
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
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
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
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
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
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
protected:
00269 EuclideanDomain m_domain;
00270 Element m_modulus;
00271 };
00272
00273 NAMESPACE_END
00274
00275
#endif