Crypto++
modarith.h
1 #ifndef CRYPTOPP_MODARITH_H
2 #define CRYPTOPP_MODARITH_H
3 
4 // implementations are in integer.cpp
5 
6 #include "cryptlib.h"
7 #include "misc.h"
8 #include "integer.h"
9 #include "algebra.h"
10 
11 NAMESPACE_BEGIN(CryptoPP)
12 
13 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<Integer>;
14 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<Integer>;
15 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<Integer>;
16 
17 //! ring of congruence classes modulo n
18 /*! \note this implementation represents each congruence class as the smallest non-negative integer in that class */
19 class CRYPTOPP_DLL ModularArithmetic : public AbstractRing<Integer>
20 {
21 public:
22 
23  typedef int RandomizationParameter;
24  typedef Integer Element;
25 
26  ModularArithmetic(const Integer &modulus = Integer::One())
27  : m_modulus(modulus), m_result((word)0, modulus.reg.size()) {}
28 
30  : m_modulus(ma.m_modulus), m_result((word)0, m_modulus.reg.size()) {}
31 
32  ModularArithmetic(BufferedTransformation &bt); // construct from BER encoded parameters
33 
34  virtual ModularArithmetic * Clone() const {return new ModularArithmetic(*this);}
35 
36  void DEREncode(BufferedTransformation &bt) const;
37 
38  void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
39  void BERDecodeElement(BufferedTransformation &in, Element &a) const;
40 
41  const Integer& GetModulus() const {return m_modulus;}
42  void SetModulus(const Integer &newModulus) {m_modulus = newModulus; m_result.reg.resize(m_modulus.reg.size());}
43 
44  virtual bool IsMontgomeryRepresentation() const {return false;}
45 
46  virtual Integer ConvertIn(const Integer &a) const
47  {return a%m_modulus;}
48 
49  virtual Integer ConvertOut(const Integer &a) const
50  {return a;}
51 
52  const Integer& Half(const Integer &a) const;
53 
54  bool Equal(const Integer &a, const Integer &b) const
55  {return a==b;}
56 
57  const Integer& Identity() const
58  {return Integer::Zero();}
59 
60  const Integer& Add(const Integer &a, const Integer &b) const;
61 
62  Integer& Accumulate(Integer &a, const Integer &b) const;
63 
64  const Integer& Inverse(const Integer &a) const;
65 
66  const Integer& Subtract(const Integer &a, const Integer &b) const;
67 
68  Integer& Reduce(Integer &a, const Integer &b) const;
69 
70  const Integer& Double(const Integer &a) const
71  {return Add(a, a);}
72 
73  const Integer& MultiplicativeIdentity() const
74  {return Integer::One();}
75 
76  const Integer& Multiply(const Integer &a, const Integer &b) const
77  {return m_result1 = a*b%m_modulus;}
78 
79  const Integer& Square(const Integer &a) const
80  {return m_result1 = a.Squared()%m_modulus;}
81 
82  bool IsUnit(const Integer &a) const
83  {return Integer::Gcd(a, m_modulus).IsUnit();}
84 
85  const Integer& MultiplicativeInverse(const Integer &a) const
86  {return m_result1 = a.InverseMod(m_modulus);}
87 
88  const Integer& Divide(const Integer &a, const Integer &b) const
89  {return Multiply(a, MultiplicativeInverse(b));}
90 
91  Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const;
92 
93  void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
94 
95  unsigned int MaxElementBitLength() const
96  {return (m_modulus-1).BitCount();}
97 
98  unsigned int MaxElementByteLength() const
99  {return (m_modulus-1).ByteCount();}
100 
101  Element RandomElement( RandomNumberGenerator &rng , const RandomizationParameter &ignore_for_now = 0 ) const
102  // left RandomizationParameter arg as ref in case RandomizationParameter becomes a more complicated struct
103  {
104  return Element( rng , Integer( (long) 0) , m_modulus - Integer( (long) 1 ) ) ;
105  }
106 
107  bool operator==(const ModularArithmetic &rhs) const
108  {return m_modulus == rhs.m_modulus;}
109 
110  static const RandomizationParameter DefaultRandomizationParameter ;
111 
112 protected:
113  Integer m_modulus;
114  mutable Integer m_result, m_result1;
115 
116 };
117 
118 // const ModularArithmetic::RandomizationParameter ModularArithmetic::DefaultRandomizationParameter = 0 ;
119 
120 //! do modular arithmetics in Montgomery representation for increased speed
121 /*! \note the Montgomery representation represents each congruence class [a] as a*r%n, where r is a convenient power of 2 */
122 class CRYPTOPP_DLL MontgomeryRepresentation : public ModularArithmetic
123 {
124 public:
125  MontgomeryRepresentation(const Integer &modulus); // modulus must be odd
126 
127  virtual ModularArithmetic * Clone() const {return new MontgomeryRepresentation(*this);}
128 
129  bool IsMontgomeryRepresentation() const {return true;}
130 
131  Integer ConvertIn(const Integer &a) const
132  {return (a<<(WORD_BITS*m_modulus.reg.size()))%m_modulus;}
133 
134  Integer ConvertOut(const Integer &a) const;
135 
136  const Integer& MultiplicativeIdentity() const
137  {return m_result1 = Integer::Power2(WORD_BITS*m_modulus.reg.size())%m_modulus;}
138 
139  const Integer& Multiply(const Integer &a, const Integer &b) const;
140 
141  const Integer& Square(const Integer &a) const;
142 
143  const Integer& MultiplicativeInverse(const Integer &a) const;
144 
145  Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
146  {return AbstractRing<Integer>::CascadeExponentiate(x, e1, y, e2);}
147 
148  void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
149  {AbstractRing<Integer>::SimultaneousExponentiate(results, base, exponents, exponentsCount);}
150 
151 private:
152  Integer m_u;
153  mutable IntegerSecBlock m_workspace;
154 };
155 
156 NAMESPACE_END
157 
158 #endif
static const Integer & One()
avoid calling constructors for these frequently used integers
void resize(size_type newSize)
change size and preserve contents
Definition: secblock.h:396
static Integer Gcd(const Integer &a, const Integer &n)
greatest common divisor
Abstract Euclidean Domain.
Definition: algebra.h:138
Square
Definition: square.h:19
ring of congruence classes modulo n
Definition: modarith.h:19
interface for random number generators
Definition: cryptlib.h:668
interface for buffered transformations
Definition: cryptlib.h:770
Abstract Ring.
Definition: algebra.h:44
bool IsUnit() const
is 1 or -1
multiple precision integer and basic arithmetics
Definition: integer.h:26
static Integer Power2(size_t e)
return the integer 2**e
Abstract Group.
Definition: algebra.h:19
do modular arithmetics in Montgomery representation for increased speed
Definition: modarith.h:122
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
static const Integer & Zero()
avoid calling constructors for these frequently used integers