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 |