Coverage Report

Created: 2024-11-21 07:03

/src/cryptopp/algebra.h
Line
Count
Source (jump to first uncovered line)
1
// algebra.h - originally written and placed in the public domain by Wei Dai
2
3
/// \file algebra.h
4
/// \brief Classes for performing mathematics over different fields
5
6
#ifndef CRYPTOPP_ALGEBRA_H
7
#define CRYPTOPP_ALGEBRA_H
8
9
#include "config.h"
10
#include "integer.h"
11
#include "misc.h"
12
13
NAMESPACE_BEGIN(CryptoPP)
14
15
class Integer;
16
17
/// \brief Abstract group
18
/// \tparam T element class or type
19
/// \details <tt>const Element&</tt> returned by member functions are references
20
///   to internal data members. Since each object may have only
21
///   one such data member for holding results, the following code
22
///   will produce incorrect results:
23
///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>
24
///   But this should be fine:
25
///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>
26
template <class T> class CRYPTOPP_NO_VTABLE AbstractGroup
27
{
28
public:
29
  typedef T Element;
30
31
338k
  virtual ~AbstractGroup() {}
CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::~AbstractGroup()
Line
Count
Source
31
108k
  virtual ~AbstractGroup() {}
CryptoPP::AbstractGroup<CryptoPP::Integer>::~AbstractGroup()
Line
Count
Source
31
229k
  virtual ~AbstractGroup() {}
Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::~AbstractGroup()
Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::~AbstractGroup()
32
33
  /// \brief Compare two elements for equality
34
  /// \param a first element
35
  /// \param b second element
36
  /// \return true if the elements are equal, false otherwise
37
  /// \details Equal() tests the elements for equality using <tt>a==b</tt>
38
  virtual bool Equal(const Element &a, const Element &b) const =0;
39
40
  /// \brief Provides the Identity element
41
  /// \return the Identity element
42
  virtual const Element& Identity() const =0;
43
44
  /// \brief Adds elements in the group
45
  /// \param a first element
46
  /// \param b second element
47
  /// \return the sum of <tt>a</tt> and <tt>b</tt>
48
  virtual const Element& Add(const Element &a, const Element &b) const =0;
49
50
  /// \brief Inverts the element in the group
51
  /// \param a first element
52
  /// \return the inverse of the element
53
  virtual const Element& Inverse(const Element &a) const =0;
54
55
  /// \brief Determine if inversion is fast
56
  /// \return true if inversion is fast, false otherwise
57
3.69k
  virtual bool InversionIsFast() const {return false;}
CryptoPP::AbstractGroup<CryptoPP::Integer>::InversionIsFast() const
Line
Count
Source
57
3.69k
  virtual bool InversionIsFast() const {return false;}
Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::InversionIsFast() const
Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::InversionIsFast() const
Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::InversionIsFast() const
58
59
  /// \brief Doubles an element in the group
60
  /// \param a the element
61
  /// \return the element doubled
62
  virtual const Element& Double(const Element &a) const;
63
64
  /// \brief Subtracts elements in the group
65
  /// \param a first element
66
  /// \param b second element
67
  /// \return the difference of <tt>a</tt> and <tt>b</tt>. The element <tt>a</tt> must provide a Subtract member function.
68
  virtual const Element& Subtract(const Element &a, const Element &b) const;
69
70
  /// \brief TODO
71
  /// \param a first element
72
  /// \param b second element
73
  /// \return TODO
74
  virtual Element& Accumulate(Element &a, const Element &b) const;
75
76
  /// \brief Reduces an element in the congruence class
77
  /// \param a element to reduce
78
  /// \param b the congruence class
79
  /// \return the reduced element
80
  virtual Element& Reduce(Element &a, const Element &b) const;
81
82
  /// \brief Performs a scalar multiplication
83
  /// \param a multiplicand
84
  /// \param e multiplier
85
  /// \return the product
86
  virtual Element ScalarMultiply(const Element &a, const Integer &e) const;
87
88
  /// \brief TODO
89
  /// \param x first multiplicand
90
  /// \param e1 the first multiplier
91
  /// \param y second multiplicand
92
  /// \param e2 the second multiplier
93
  /// \return TODO
94
  virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
95
96
  /// \brief Multiplies a base to multiple exponents in a group
97
  /// \param results an array of Elements
98
  /// \param base the base to raise to the exponents
99
  /// \param exponents an array of exponents
100
  /// \param exponentsCount the number of exponents in the array
101
  /// \details SimultaneousMultiply() multiplies the base to each exponent in the exponents array and stores the
102
  ///   result at the respective position in the results array.
103
  /// \details SimultaneousMultiply() must be implemented in a derived class.
104
  /// \pre <tt>COUNTOF(results) == exponentsCount</tt>
105
  /// \pre <tt>COUNTOF(exponents) == exponentsCount</tt>
106
  virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
107
};
108
109
/// \brief Abstract ring
110
/// \tparam T element class or type
111
/// \details <tt>const Element&</tt> returned by member functions are references
112
///   to internal data members. Since each object may have only
113
///   one such data member for holding results, the following code
114
///   will produce incorrect results:
115
///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>
116
///   But this should be fine:
117
///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>
118
template <class T> class CRYPTOPP_NO_VTABLE AbstractRing : public AbstractGroup<T>
119
{
120
public:
121
  typedef T Element;
122
123
  /// \brief Construct an AbstractRing
124
60.5k
  AbstractRing() {m_mg.m_pRing = this;}
CryptoPP::AbstractRing<CryptoPP::Integer>::AbstractRing()
Line
Count
Source
124
60.5k
  AbstractRing() {m_mg.m_pRing = this;}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::AbstractRing()
125
126
  /// \brief Copy construct an AbstractRing
127
  /// \param source other AbstractRing
128
  AbstractRing(const AbstractRing &source)
129
54.3k
    {CRYPTOPP_UNUSED(source); m_mg.m_pRing = this;}
CryptoPP::AbstractRing<CryptoPP::Integer>::AbstractRing(CryptoPP::AbstractRing<CryptoPP::Integer> const&)
Line
Count
Source
129
54.3k
    {CRYPTOPP_UNUSED(source); m_mg.m_pRing = this;}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::AbstractRing(CryptoPP::AbstractRing<CryptoPP::PolynomialMod2> const&)
130
131
  /// \brief Assign an AbstractRing
132
  /// \param source other AbstractRing
133
  AbstractRing& operator=(const AbstractRing &source)
134
0
    {CRYPTOPP_UNUSED(source); return *this;}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::operator=(CryptoPP::AbstractRing<CryptoPP::Integer> const&)
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::operator=(CryptoPP::AbstractRing<CryptoPP::PolynomialMod2> const&)
135
136
  /// \brief Determines whether an element is a unit in the group
137
  /// \param a the element
138
  /// \return true if the element is a unit after reduction, false otherwise.
139
  virtual bool IsUnit(const Element &a) const =0;
140
141
  /// \brief Retrieves the multiplicative identity
142
  /// \return the multiplicative identity
143
  virtual const Element& MultiplicativeIdentity() const =0;
144
145
  /// \brief Multiplies elements in the group
146
  /// \param a the multiplicand
147
  /// \param b the multiplier
148
  /// \return the product of a and b
149
  virtual const Element& Multiply(const Element &a, const Element &b) const =0;
150
151
  /// \brief Calculate the multiplicative inverse of an element in the group
152
  /// \param a the element
153
  virtual const Element& MultiplicativeInverse(const Element &a) const =0;
154
155
  /// \brief Square an element in the group
156
  /// \param a the element
157
  /// \return the element squared
158
  virtual const Element& Square(const Element &a) const;
159
160
  /// \brief Divides elements in the group
161
  /// \param a the dividend
162
  /// \param b the divisor
163
  /// \return the quotient
164
  virtual const Element& Divide(const Element &a, const Element &b) const;
165
166
  /// \brief Raises a base to an exponent in the group
167
  /// \param a the base
168
  /// \param e the exponent
169
  /// \return the exponentiation
170
  virtual Element Exponentiate(const Element &a, const Integer &e) const;
171
172
  /// \brief TODO
173
  /// \param x first element
174
  /// \param e1 first exponent
175
  /// \param y second element
176
  /// \param e2 second exponent
177
  /// \return TODO
178
  virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const;
179
180
  /// \brief Exponentiates a base to multiple exponents in the Ring
181
  /// \param results an array of Elements
182
  /// \param base the base to raise to the exponents
183
  /// \param exponents an array of exponents
184
  /// \param exponentsCount the number of exponents in the array
185
  /// \details SimultaneousExponentiate() raises the base to each exponent in the exponents array and stores the
186
  ///   result at the respective position in the results array.
187
  /// \details SimultaneousExponentiate() must be implemented in a derived class.
188
  /// \pre <tt>COUNTOF(results) == exponentsCount</tt>
189
  /// \pre <tt>COUNTOF(exponents) == exponentsCount</tt>
190
  virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
191
192
  /// \brief Retrieves the multiplicative group
193
  /// \return the multiplicative group
194
  virtual const AbstractGroup<T>& MultiplicativeGroup() const
195
3.69k
    {return m_mg;}
CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroup() const
Line
Count
Source
195
3.69k
    {return m_mg;}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroup() const
196
197
private:
198
  class MultiplicativeGroupT : public AbstractGroup<T>
199
  {
200
  public:
201
    const AbstractRing<T>& GetRing() const
202
2.25M
      {return *m_pRing;}
CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::GetRing() const
Line
Count
Source
202
2.25M
      {return *m_pRing;}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::GetRing() const
203
204
    bool Equal(const Element &a, const Element &b) const
205
0
      {return GetRing().Equal(a, b);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Equal(CryptoPP::Integer const&, CryptoPP::Integer const&) const
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Equal(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
206
207
    const Element& Identity() const
208
3.69k
      {return GetRing().MultiplicativeIdentity();}
CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Identity() const
Line
Count
Source
208
3.69k
      {return GetRing().MultiplicativeIdentity();}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Identity() const
209
210
    const Element& Add(const Element &a, const Element &b) const
211
3.35k
      {return GetRing().Multiply(a, b);}
CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Add(CryptoPP::Integer const&, CryptoPP::Integer const&) const
Line
Count
Source
211
3.35k
      {return GetRing().Multiply(a, b);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Add(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
212
213
    Element& Accumulate(Element &a, const Element &b) const
214
374k
      {return a = GetRing().Multiply(a, b);}
CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Accumulate(CryptoPP::Integer&, CryptoPP::Integer const&) const
Line
Count
Source
214
374k
      {return a = GetRing().Multiply(a, b);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Accumulate(CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2 const&) const
215
216
    const Element& Inverse(const Element &a) const
217
0
      {return GetRing().MultiplicativeInverse(a);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Inverse(CryptoPP::Integer const&) const
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Inverse(CryptoPP::PolynomialMod2 const&) const
218
219
    const Element& Subtract(const Element &a, const Element &b) const
220
0
      {return GetRing().Divide(a, b);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Subtract(CryptoPP::Integer const&, CryptoPP::Integer const&) const
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Subtract(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
221
222
    Element& Reduce(Element &a, const Element &b) const
223
0
      {return a = GetRing().Divide(a, b);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Reduce(CryptoPP::Integer&, CryptoPP::Integer const&) const
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Reduce(CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2 const&) const
224
225
    const Element& Double(const Element &a) const
226
1.87M
      {return GetRing().Square(a);}
CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::Double(CryptoPP::Integer const&) const
Line
Count
Source
226
1.87M
      {return GetRing().Square(a);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::Double(CryptoPP::PolynomialMod2 const&) const
227
228
    Element ScalarMultiply(const Element &a, const Integer &e) const
229
0
      {return GetRing().Exponentiate(a, e);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::ScalarMultiply(CryptoPP::Integer const&, CryptoPP::Integer const&) const
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::ScalarMultiply(CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&) const
230
231
    Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
232
0
      {return GetRing().CascadeExponentiate(x, e1, y, e2);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::CascadeScalarMultiply(CryptoPP::Integer const&, CryptoPP::Integer const&, CryptoPP::Integer const&, CryptoPP::Integer const&) const
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::CascadeScalarMultiply(CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&, CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&) const
233
234
    void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
235
0
      {GetRing().SimultaneousExponentiate(results, base, exponents, exponentsCount);}
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::MultiplicativeGroupT::SimultaneousMultiply(CryptoPP::Integer*, CryptoPP::Integer const&, CryptoPP::Integer const*, unsigned int) const
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::MultiplicativeGroupT::SimultaneousMultiply(CryptoPP::PolynomialMod2*, CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const*, unsigned int) const
236
237
    const AbstractRing<T> *m_pRing;
238
  };
239
240
  MultiplicativeGroupT m_mg;
241
};
242
243
// ********************************************************
244
245
/// \brief Base and exponent
246
/// \tparam T base class or type
247
/// \tparam E exponent class or type
248
template <class T, class E = Integer>
249
struct BaseAndExponent
250
{
251
public:
252
0
  BaseAndExponent() {}
253
0
  BaseAndExponent(const T &base, const E &exponent) : base(base), exponent(exponent) {}
Unexecuted instantiation: CryptoPP::BaseAndExponent<CryptoPP::Integer, CryptoPP::Integer>::BaseAndExponent(CryptoPP::Integer const&, CryptoPP::Integer const&)
Unexecuted instantiation: CryptoPP::BaseAndExponent<CryptoPP::EC2NPoint, CryptoPP::Integer>::BaseAndExponent(CryptoPP::EC2NPoint const&, CryptoPP::Integer const&)
Unexecuted instantiation: CryptoPP::BaseAndExponent<CryptoPP::ECPPoint, CryptoPP::Integer>::BaseAndExponent(CryptoPP::ECPPoint const&, CryptoPP::Integer const&)
254
0
  bool operator<(const BaseAndExponent<T, E> &rhs) const {return exponent < rhs.exponent;}
Unexecuted instantiation: CryptoPP::BaseAndExponent<CryptoPP::Integer, CryptoPP::Integer>::operator<(CryptoPP::BaseAndExponent<CryptoPP::Integer, CryptoPP::Integer> const&) const
Unexecuted instantiation: CryptoPP::BaseAndExponent<CryptoPP::EC2NPoint, CryptoPP::Integer>::operator<(CryptoPP::BaseAndExponent<CryptoPP::EC2NPoint, CryptoPP::Integer> const&) const
Unexecuted instantiation: CryptoPP::BaseAndExponent<CryptoPP::ECPPoint, CryptoPP::Integer>::operator<(CryptoPP::BaseAndExponent<CryptoPP::ECPPoint, CryptoPP::Integer> const&) const
255
  T base;
256
  E exponent;
257
};
258
259
// VC60 workaround: incomplete member template support
260
template <class Element, class Iterator>
261
  Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end);
262
template <class Element, class Iterator>
263
  Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end);
264
265
// ********************************************************
266
267
/// \brief Abstract Euclidean domain
268
/// \tparam T element class or type
269
/// \details <tt>const Element&</tt> returned by member functions are references
270
///   to internal data members. Since each object may have only
271
///   one such data member for holding results, the following code
272
///   will produce incorrect results:
273
///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>
274
///   But this should be fine:
275
///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>
276
template <class T> class CRYPTOPP_NO_VTABLE AbstractEuclideanDomain : public AbstractRing<T>
277
{
278
public:
279
  typedef T Element;
280
281
  /// \brief Performs the division algorithm on two elements in the ring
282
  /// \param r the remainder
283
  /// \param q the quotient
284
  /// \param a the dividend
285
  /// \param d the divisor
286
  virtual void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const =0;
287
288
  /// \brief Performs a modular reduction in the ring
289
  /// \param a the element
290
  /// \param b the modulus
291
  /// \return the result of <tt>a%b</tt>.
292
  virtual const Element& Mod(const Element &a, const Element &b) const =0;
293
294
  /// \brief Calculates the greatest common denominator in the ring
295
  /// \param a the first element
296
  /// \param b the second element
297
  /// \return the greatest common denominator of a and b.
298
  virtual const Element& Gcd(const Element &a, const Element &b) const;
299
300
protected:
301
  mutable Element result;
302
};
303
304
// ********************************************************
305
306
/// \brief Euclidean domain
307
/// \tparam T element class or type
308
/// \details <tt>const Element&</tt> returned by member functions are references
309
///   to internal data members. Since each object may have only
310
///   one such data member for holding results, the following code
311
///   will produce incorrect results:
312
///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>
313
///   But this should be fine:
314
///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>
315
template <class T> class EuclideanDomainOf : public AbstractEuclideanDomain<T>
316
{
317
public:
318
  typedef T Element;
319
320
765
  EuclideanDomainOf() {}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::EuclideanDomainOf()
CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::EuclideanDomainOf()
Line
Count
Source
320
765
  EuclideanDomainOf() {}
321
322
  bool Equal(const Element &a, const Element &b) const
323
449k
    {return a==b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Equal(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Equal(CryptoPP::Integer const&, CryptoPP::Integer const&) const
Line
Count
Source
323
449k
    {return a==b;}
324
325
  const Element& Identity() const
326
449k
    {return Element::Zero();}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Identity() const
CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Identity() const
Line
Count
Source
326
449k
    {return Element::Zero();}
327
328
  const Element& Add(const Element &a, const Element &b) const
329
0
    {return result = a+b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Add(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Add(CryptoPP::Integer const&, CryptoPP::Integer const&) const
330
331
  Element& Accumulate(Element &a, const Element &b) const
332
0
    {return a+=b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Accumulate(CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Accumulate(CryptoPP::Integer&, CryptoPP::Integer const&) const
333
334
  const Element& Inverse(const Element &a) const
335
0
    {return result = -a;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Inverse(CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Inverse(CryptoPP::Integer const&) const
336
337
  const Element& Subtract(const Element &a, const Element &b) const
338
0
    {return result = a-b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Subtract(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Subtract(CryptoPP::Integer const&, CryptoPP::Integer const&) const
339
340
  Element& Reduce(Element &a, const Element &b) const
341
0
    {return a-=b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Reduce(CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Reduce(CryptoPP::Integer&, CryptoPP::Integer const&) const
342
343
  const Element& Double(const Element &a) const
344
0
    {return result = a.Doubled();}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Double(CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Double(CryptoPP::Integer const&) const
345
346
  const Element& MultiplicativeIdentity() const
347
0
    {return Element::One();}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::MultiplicativeIdentity() const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::MultiplicativeIdentity() const
348
349
  const Element& Multiply(const Element &a, const Element &b) const
350
0
    {return result = a*b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Multiply(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Multiply(CryptoPP::Integer const&, CryptoPP::Integer const&) const
351
352
  const Element& Square(const Element &a) const
353
0
    {return result = a.Squared();}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Square(CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Square(CryptoPP::Integer const&) const
354
355
  bool IsUnit(const Element &a) const
356
0
    {return a.IsUnit();}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::IsUnit(CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::IsUnit(CryptoPP::Integer const&) const
357
358
  const Element& MultiplicativeInverse(const Element &a) const
359
0
    {return result = a.MultiplicativeInverse();}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::MultiplicativeInverse(CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::MultiplicativeInverse(CryptoPP::Integer const&) const
360
361
  const Element& Divide(const Element &a, const Element &b) const
362
0
    {return result = a/b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Divide(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Divide(CryptoPP::Integer const&, CryptoPP::Integer const&) const
363
364
  const Element& Mod(const Element &a, const Element &b) const
365
448k
    {return result = a%b;}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::Mod(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::Mod(CryptoPP::Integer const&, CryptoPP::Integer const&) const
Line
Count
Source
365
448k
    {return result = a%b;}
366
367
  void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
368
0
    {Element::Divide(r, q, a, d);}
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::PolynomialMod2>::DivisionAlgorithm(CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const
Unexecuted instantiation: CryptoPP::EuclideanDomainOf<CryptoPP::Integer>::DivisionAlgorithm(CryptoPP::Integer&, CryptoPP::Integer&, CryptoPP::Integer const&, CryptoPP::Integer const&) const
369
370
  bool operator==(const EuclideanDomainOf<T> &rhs) const
371
0
    {CRYPTOPP_UNUSED(rhs); return true;}
372
373
private:
374
  mutable Element result;
375
};
376
377
/// \brief Quotient ring
378
/// \tparam T element class or type
379
/// \details <tt>const Element&</tt> returned by member functions are references
380
///   to internal data members. Since each object may have only
381
///   one such data member for holding results, the following code
382
///   will produce incorrect results:
383
///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>
384
///   But this should be fine:
385
///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>
386
template <class T> class QuotientRing : public AbstractRing<typename T::Element>
387
{
388
public:
389
  typedef T EuclideanDomain;
390
  typedef typename T::Element Element;
391
392
  QuotientRing(const EuclideanDomain &domain, const Element &modulus)
393
0
    : m_domain(domain), m_modulus(modulus) {}
394
395
  const EuclideanDomain & GetDomain() const
396
0
    {return m_domain;}
397
398
  const Element& GetModulus() const
399
0
    {return m_modulus;}
400
401
  bool Equal(const Element &a, const Element &b) const
402
0
    {return m_domain.Equal(m_domain.Mod(m_domain.Subtract(a, b), m_modulus), m_domain.Identity());}
403
404
  const Element& Identity() const
405
0
    {return m_domain.Identity();}
406
407
  const Element& Add(const Element &a, const Element &b) const
408
0
    {return m_domain.Add(a, b);}
409
410
  Element& Accumulate(Element &a, const Element &b) const
411
0
    {return m_domain.Accumulate(a, b);}
412
413
  const Element& Inverse(const Element &a) const
414
0
    {return m_domain.Inverse(a);}
415
416
  const Element& Subtract(const Element &a, const Element &b) const
417
0
    {return m_domain.Subtract(a, b);}
418
419
  Element& Reduce(Element &a, const Element &b) const
420
0
    {return m_domain.Reduce(a, b);}
421
422
  const Element& Double(const Element &a) const
423
0
    {return m_domain.Double(a);}
424
425
  bool IsUnit(const Element &a) const
426
0
    {return m_domain.IsUnit(m_domain.Gcd(a, m_modulus));}
427
428
  const Element& MultiplicativeIdentity() const
429
0
    {return m_domain.MultiplicativeIdentity();}
430
431
  const Element& Multiply(const Element &a, const Element &b) const
432
0
    {return m_domain.Mod(m_domain.Multiply(a, b), m_modulus);}
433
434
  const Element& Square(const Element &a) const
435
0
    {return m_domain.Mod(m_domain.Square(a), m_modulus);}
436
437
  const Element& MultiplicativeInverse(const Element &a) const;
438
439
  bool operator==(const QuotientRing<T> &rhs) const
440
0
    {return m_domain == rhs.m_domain && m_modulus == rhs.m_modulus;}
441
442
protected:
443
  EuclideanDomain m_domain;
444
  Element m_modulus;
445
};
446
447
NAMESPACE_END
448
449
#ifdef CRYPTOPP_MANUALLY_INSTANTIATE_TEMPLATES
450
#include "algebra.cpp"
451
#endif
452
453
#endif