/src/cryptopp/algebra.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | // algebra.cpp - originally written and placed in the public domain by Wei Dai |
2 | | |
3 | | #include "pch.h" |
4 | | |
5 | | #ifndef CRYPTOPP_ALGEBRA_CPP // SunCC workaround: compiler could cause this file to be included twice |
6 | | #define CRYPTOPP_ALGEBRA_CPP |
7 | | |
8 | | #include "algebra.h" |
9 | | #include "integer.h" |
10 | | |
11 | | #include <vector> |
12 | | |
13 | | NAMESPACE_BEGIN(CryptoPP) |
14 | | |
15 | | template <class T> const T& AbstractGroup<T>::Double(const Element &a) const |
16 | 0 | { |
17 | 0 | return this->Add(a, a); |
18 | 0 | } Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::Integer>::Double(CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::Double(CryptoPP::PolynomialMod2 const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::Double(CryptoPP::ECPPoint const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::Double(CryptoPP::EC2NPoint const&) const |
19 | | |
20 | | template <class T> const T& AbstractGroup<T>::Subtract(const Element &a, const Element &b) const |
21 | 0 | { |
22 | | // make copy of a in case Inverse() overwrites it |
23 | 0 | Element a1(a); |
24 | 0 | return this->Add(a1, Inverse(b)); |
25 | 0 | } Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::Integer>::Subtract(CryptoPP::Integer const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::Subtract(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::Subtract(CryptoPP::ECPPoint const&, CryptoPP::ECPPoint const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::Subtract(CryptoPP::EC2NPoint const&, CryptoPP::EC2NPoint const&) const |
26 | | |
27 | | template <class T> T& AbstractGroup<T>::Accumulate(Element &a, const Element &b) const |
28 | 0 | { |
29 | 0 | return a = this->Add(a, b); |
30 | 0 | } Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::Integer>::Accumulate(CryptoPP::Integer&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::Accumulate(CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2 const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::Accumulate(CryptoPP::ECPPoint&, CryptoPP::ECPPoint const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::Accumulate(CryptoPP::EC2NPoint&, CryptoPP::EC2NPoint const&) const |
31 | | |
32 | | template <class T> T& AbstractGroup<T>::Reduce(Element &a, const Element &b) const |
33 | 0 | { |
34 | 0 | return a = this->Subtract(a, b); |
35 | 0 | } Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::Integer>::Reduce(CryptoPP::Integer&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::Reduce(CryptoPP::PolynomialMod2&, CryptoPP::PolynomialMod2 const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::Reduce(CryptoPP::ECPPoint&, CryptoPP::ECPPoint const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::Reduce(CryptoPP::EC2NPoint&, CryptoPP::EC2NPoint const&) const |
36 | | |
37 | | template <class T> const T& AbstractRing<T>::Square(const Element &a) const |
38 | 0 | { |
39 | 0 | return this->Multiply(a, a); |
40 | 0 | } Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::Square(CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::Square(CryptoPP::PolynomialMod2 const&) const |
41 | | |
42 | | template <class T> const T& AbstractRing<T>::Divide(const Element &a, const Element &b) const |
43 | 0 | { |
44 | | // make copy of a in case MultiplicativeInverse() overwrites it |
45 | 0 | Element a1(a); |
46 | 0 | return this->Multiply(a1, this->MultiplicativeInverse(b)); |
47 | 0 | } Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::Divide(CryptoPP::Integer const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::Divide(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const |
48 | | |
49 | | template <class T> const T& AbstractEuclideanDomain<T>::Mod(const Element &a, const Element &b) const |
50 | 0 | { |
51 | 0 | Element q; |
52 | 0 | this->DivisionAlgorithm(result, q, a, b); |
53 | 0 | return result; |
54 | 0 | } Unexecuted instantiation: CryptoPP::AbstractEuclideanDomain<CryptoPP::Integer>::Mod(CryptoPP::Integer const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractEuclideanDomain<CryptoPP::PolynomialMod2>::Mod(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const |
55 | | |
56 | | template <class T> const T& AbstractEuclideanDomain<T>::Gcd(const Element &a, const Element &b) const |
57 | 765 | { |
58 | 765 | Element g[3]={b, a}; |
59 | 765 | unsigned int i0=0, i1=1, i2=2; |
60 | | |
61 | 449k | while (!this->Equal(g[i1], this->Identity())) |
62 | 448k | { |
63 | 448k | g[i2] = this->Mod(g[i0], g[i1]); |
64 | 448k | unsigned int t = i0; i0 = i1; i1 = i2; i2 = t; |
65 | 448k | } |
66 | | |
67 | 765 | return result = g[i0]; |
68 | 765 | } CryptoPP::AbstractEuclideanDomain<CryptoPP::Integer>::Gcd(CryptoPP::Integer const&, CryptoPP::Integer const&) const Line | Count | Source | 57 | 765 | { | 58 | 765 | Element g[3]={b, a}; | 59 | 765 | unsigned int i0=0, i1=1, i2=2; | 60 | | | 61 | 449k | while (!this->Equal(g[i1], this->Identity())) | 62 | 448k | { | 63 | 448k | g[i2] = this->Mod(g[i0], g[i1]); | 64 | 448k | unsigned int t = i0; i0 = i1; i1 = i2; i2 = t; | 65 | 448k | } | 66 | | | 67 | 765 | return result = g[i0]; | 68 | 765 | } |
Unexecuted instantiation: CryptoPP::AbstractEuclideanDomain<CryptoPP::PolynomialMod2>::Gcd(CryptoPP::PolynomialMod2 const&, CryptoPP::PolynomialMod2 const&) const |
69 | | |
70 | | template <class T> const typename QuotientRing<T>::Element& QuotientRing<T>::MultiplicativeInverse(const Element &a) const |
71 | 0 | { |
72 | 0 | Element g[3]={m_modulus, a}; |
73 | 0 | Element v[3]={m_domain.Identity(), m_domain.MultiplicativeIdentity()}; |
74 | 0 | Element y; |
75 | 0 | unsigned int i0=0, i1=1, i2=2; |
76 | |
|
77 | 0 | while (!this->Equal(g[i1], this->Identity())) |
78 | 0 | { |
79 | | // y = g[i0] / g[i1]; |
80 | | // g[i2] = g[i0] % g[i1]; |
81 | 0 | m_domain.DivisionAlgorithm(g[i2], y, g[i0], g[i1]); |
82 | | // v[i2] = v[i0] - (v[i1] * y); |
83 | 0 | v[i2] = m_domain.Subtract(v[i0], m_domain.Multiply(v[i1], y)); |
84 | 0 | unsigned int t = i0; i0 = i1; i1 = i2; i2 = t; |
85 | 0 | } |
86 | |
|
87 | 0 | return m_domain.IsUnit(g[i0]) ? m_domain.Divide(v[i0], g[i0]) : m_domain.Identity(); |
88 | 0 | } |
89 | | |
90 | | template <class T> T AbstractGroup<T>::ScalarMultiply(const Element &base, const Integer &exponent) const |
91 | 0 | { |
92 | 0 | Element result; |
93 | 0 | this->SimultaneousMultiply(&result, base, &exponent, 1); |
94 | 0 | return result; |
95 | 0 | } Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::Integer>::ScalarMultiply(CryptoPP::Integer const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::ScalarMultiply(CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::ScalarMultiply(CryptoPP::ECPPoint const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::ScalarMultiply(CryptoPP::EC2NPoint const&, CryptoPP::Integer const&) const |
96 | | |
97 | | template <class T> T AbstractGroup<T>::CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const |
98 | 0 | { |
99 | 0 | const unsigned expLen = STDMAX(e1.BitCount(), e2.BitCount()); |
100 | 0 | if (expLen==0) |
101 | 0 | return this->Identity(); |
102 | | |
103 | 0 | const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3)); |
104 | 0 | const unsigned tableSize = 1<<w; |
105 | 0 | std::vector<Element> powerTable(tableSize << w); |
106 | |
|
107 | 0 | powerTable[1] = x; |
108 | 0 | powerTable[tableSize] = y; |
109 | 0 | if (w==1) |
110 | 0 | powerTable[3] = this->Add(x,y); |
111 | 0 | else |
112 | 0 | { |
113 | 0 | powerTable[2] = this->Double(x); |
114 | 0 | powerTable[2*tableSize] = this->Double(y); |
115 | |
|
116 | 0 | unsigned i, j; |
117 | |
|
118 | 0 | for (i=3; i<tableSize; i+=2) |
119 | 0 | powerTable[i] = Add(powerTable[i-2], powerTable[2]); |
120 | 0 | for (i=1; i<tableSize; i+=2) |
121 | 0 | for (j=i+tableSize; j<(tableSize<<w); j+=tableSize) |
122 | 0 | powerTable[j] = Add(powerTable[j-tableSize], y); |
123 | |
|
124 | 0 | for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize) |
125 | 0 | powerTable[i] = Add(powerTable[i-2*tableSize], powerTable[2*tableSize]); |
126 | 0 | for (i=tableSize; i<(tableSize<<w); i+=2*tableSize) |
127 | 0 | for (j=i+2; j<i+tableSize; j+=2) |
128 | 0 | powerTable[j] = Add(powerTable[j-1], x); |
129 | 0 | } |
130 | |
|
131 | 0 | Element result; |
132 | 0 | unsigned power1 = 0, power2 = 0, prevPosition = expLen-1; |
133 | 0 | bool firstTime = true; |
134 | |
|
135 | 0 | for (int i = expLen-1; i>=0; i--) |
136 | 0 | { |
137 | 0 | power1 = 2*power1 + e1.GetBit(i); |
138 | 0 | power2 = 2*power2 + e2.GetBit(i); |
139 | |
|
140 | 0 | if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize) |
141 | 0 | { |
142 | 0 | unsigned squaresBefore = prevPosition-i; |
143 | 0 | unsigned squaresAfter = 0; |
144 | 0 | prevPosition = i; |
145 | 0 | while ((power1 || power2) && power1%2 == 0 && power2%2==0) |
146 | 0 | { |
147 | 0 | power1 /= 2; |
148 | 0 | power2 /= 2; |
149 | 0 | squaresBefore--; |
150 | 0 | squaresAfter++; |
151 | 0 | } |
152 | 0 | if (firstTime) |
153 | 0 | { |
154 | 0 | result = powerTable[(power2<<w) + power1]; |
155 | 0 | firstTime = false; |
156 | 0 | } |
157 | 0 | else |
158 | 0 | { |
159 | 0 | while (squaresBefore--) |
160 | 0 | result = this->Double(result); |
161 | 0 | if (power1 || power2) |
162 | 0 | Accumulate(result, powerTable[(power2<<w) + power1]); |
163 | 0 | } |
164 | 0 | while (squaresAfter--) |
165 | 0 | result = this->Double(result); |
166 | 0 | power1 = power2 = 0; |
167 | 0 | } |
168 | 0 | } |
169 | 0 | return result; |
170 | 0 | } Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::Integer>::CascadeScalarMultiply(CryptoPP::Integer const&, CryptoPP::Integer const&, CryptoPP::Integer const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::CascadeScalarMultiply(CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&, CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::CascadeScalarMultiply(CryptoPP::ECPPoint const&, CryptoPP::Integer const&, CryptoPP::ECPPoint const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::CascadeScalarMultiply(CryptoPP::EC2NPoint const&, CryptoPP::Integer const&, CryptoPP::EC2NPoint const&, CryptoPP::Integer const&) const |
171 | | |
172 | | template <class Element, class Iterator> Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end) |
173 | 0 | { |
174 | 0 | if (end-begin == 1) |
175 | 0 | return group.ScalarMultiply(begin->base, begin->exponent); |
176 | 0 | else if (end-begin == 2) |
177 | 0 | return group.CascadeScalarMultiply(begin->base, begin->exponent, (begin+1)->base, (begin+1)->exponent); |
178 | 0 | else |
179 | 0 | { |
180 | 0 | Integer q, t; |
181 | 0 | Iterator last = end; |
182 | 0 | --last; |
183 | |
|
184 | 0 | std::make_heap(begin, end); |
185 | 0 | std::pop_heap(begin, end); |
186 | |
|
187 | 0 | while (!!begin->exponent) |
188 | 0 | { |
189 | | // last->exponent is largest exponent, begin->exponent is next largest |
190 | 0 | t = last->exponent; |
191 | 0 | Integer::Divide(last->exponent, q, t, begin->exponent); |
192 | |
|
193 | 0 | if (q == Integer::One()) |
194 | 0 | group.Accumulate(begin->base, last->base); // avoid overhead of ScalarMultiply() |
195 | 0 | else |
196 | 0 | group.Accumulate(begin->base, group.ScalarMultiply(last->base, q)); |
197 | |
|
198 | 0 | std::push_heap(begin, end); |
199 | 0 | std::pop_heap(begin, end); |
200 | 0 | } |
201 | |
|
202 | 0 | return group.ScalarMultiply(last->base, last->exponent); |
203 | 0 | } |
204 | 0 | } Unexecuted instantiation: CryptoPP::Integer CryptoPP::GeneralCascadeMultiplication<CryptoPP::Integer, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::Integer, CryptoPP::Integer>*> >(CryptoPP::AbstractGroup<CryptoPP::Integer> const&, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::Integer, CryptoPP::Integer>*>, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::Integer, CryptoPP::Integer>*>) Unexecuted instantiation: CryptoPP::EC2NPoint CryptoPP::GeneralCascadeMultiplication<CryptoPP::EC2NPoint, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::EC2NPoint, CryptoPP::Integer>*> >(CryptoPP::AbstractGroup<CryptoPP::EC2NPoint> const&, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::EC2NPoint, CryptoPP::Integer>*>, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::EC2NPoint, CryptoPP::Integer>*>) Unexecuted instantiation: CryptoPP::ECPPoint CryptoPP::GeneralCascadeMultiplication<CryptoPP::ECPPoint, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::ECPPoint, CryptoPP::Integer>*> >(CryptoPP::AbstractGroup<CryptoPP::ECPPoint> const&, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::ECPPoint, CryptoPP::Integer>*>, std::__1::__wrap_iter<CryptoPP::BaseAndExponent<CryptoPP::ECPPoint, CryptoPP::Integer>*>) |
205 | | |
206 | | struct WindowSlider |
207 | | { |
208 | | WindowSlider(const Integer &expIn, bool fastNegate, unsigned int windowSizeIn=0) |
209 | | : exp(expIn), windowModulus(Integer::One()), windowSize(windowSizeIn), windowBegin(0), expWindow(0) |
210 | | , fastNegate(fastNegate), negateNext(false), firstTime(true), finished(false) |
211 | 3.69k | { |
212 | 3.69k | if (windowSize == 0) |
213 | 3.69k | { |
214 | 3.69k | unsigned int expLen = exp.BitCount(); |
215 | 3.69k | windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 : (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 : (expLen <= 1434 ? 6 : 7))))); |
216 | 3.69k | } |
217 | 3.69k | windowModulus <<= windowSize; |
218 | 3.69k | } |
219 | | |
220 | | void FindNextWindow() |
221 | 267k | { |
222 | 267k | unsigned int expLen = exp.WordCount() * WORD_BITS; |
223 | 267k | unsigned int skipCount = firstTime ? 0 : windowSize; |
224 | 267k | firstTime = false; |
225 | 770k | while (!exp.GetBit(skipCount)) |
226 | 506k | { |
227 | 506k | if (skipCount >= expLen) |
228 | 3.69k | { |
229 | 3.69k | finished = true; |
230 | 3.69k | return; |
231 | 3.69k | } |
232 | 502k | skipCount++; |
233 | 502k | } |
234 | | |
235 | 263k | exp >>= skipCount; |
236 | 263k | windowBegin += skipCount; |
237 | 263k | expWindow = word32(exp % (word(1) << windowSize)); |
238 | | |
239 | 263k | if (fastNegate && exp.GetBit(windowSize)) |
240 | 0 | { |
241 | 0 | negateNext = true; |
242 | 0 | expWindow = (word32(1) << windowSize) - expWindow; |
243 | 0 | exp += windowModulus; |
244 | 0 | } |
245 | 263k | else |
246 | 263k | negateNext = false; |
247 | 263k | } |
248 | | |
249 | | Integer exp, windowModulus; |
250 | | unsigned int windowSize, windowBegin; |
251 | | word32 expWindow; |
252 | | bool fastNegate, negateNext, firstTime, finished; |
253 | | }; |
254 | | |
255 | | template <class T> |
256 | | void AbstractGroup<T>::SimultaneousMultiply(T *results, const T &base, const Integer *expBegin, unsigned int expCount) const |
257 | 3.69k | { |
258 | 3.69k | std::vector<std::vector<Element> > buckets(expCount); |
259 | 3.69k | std::vector<WindowSlider> exponents; |
260 | 3.69k | exponents.reserve(expCount); |
261 | 3.69k | unsigned int i; |
262 | | |
263 | 7.38k | for (i=0; expBegin && i<expCount; i++) |
264 | 3.69k | { |
265 | 3.69k | CRYPTOPP_ASSERT(expBegin->NotNegative()); |
266 | 3.69k | exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0)); |
267 | 3.69k | exponents[i].FindNextWindow(); |
268 | 3.69k | buckets[i].resize(((size_t) 1) << (exponents[i].windowSize-1), Identity()); |
269 | 3.69k | } |
270 | | |
271 | 3.69k | unsigned int expBitPosition = 0; |
272 | 3.69k | Element g = base; |
273 | 3.69k | bool notDone = true; |
274 | | |
275 | 1.87M | while (notDone) |
276 | 1.87M | { |
277 | 1.87M | notDone = false; |
278 | 3.74M | for (i=0; i<expCount; i++) |
279 | 1.87M | { |
280 | 1.87M | if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin) |
281 | 263k | { |
282 | 263k | Element &bucket = buckets[i][exponents[i].expWindow/2]; |
283 | 263k | if (exponents[i].negateNext) |
284 | 0 | Accumulate(bucket, Inverse(g)); |
285 | 263k | else |
286 | 263k | Accumulate(bucket, g); |
287 | 263k | exponents[i].FindNextWindow(); |
288 | 263k | } |
289 | 1.87M | notDone = notDone || !exponents[i].finished; |
290 | 1.87M | } |
291 | | |
292 | 1.87M | if (notDone) |
293 | 1.87M | { |
294 | 1.87M | g = Double(g); |
295 | 1.87M | expBitPosition++; |
296 | 1.87M | } |
297 | 1.87M | } |
298 | | |
299 | 7.38k | for (i=0; i<expCount; i++) |
300 | 3.69k | { |
301 | 3.69k | Element &r = *results++; |
302 | 3.69k | r = buckets[i][buckets[i].size()-1]; |
303 | 3.69k | if (buckets[i].size() > 1) |
304 | 3.35k | { |
305 | 56.9k | for (int j = (int)buckets[i].size()-2; j >= 1; j--) |
306 | 53.6k | { |
307 | 53.6k | Accumulate(buckets[i][j], buckets[i][j+1]); |
308 | 53.6k | Accumulate(r, buckets[i][j]); |
309 | 53.6k | } |
310 | 3.35k | Accumulate(buckets[i][0], buckets[i][1]); |
311 | 3.35k | r = Add(Double(r), buckets[i][0]); |
312 | 3.35k | } |
313 | 3.69k | } |
314 | 3.69k | } CryptoPP::AbstractGroup<CryptoPP::Integer>::SimultaneousMultiply(CryptoPP::Integer*, CryptoPP::Integer const&, CryptoPP::Integer const*, unsigned int) const Line | Count | Source | 257 | 3.69k | { | 258 | 3.69k | std::vector<std::vector<Element> > buckets(expCount); | 259 | 3.69k | std::vector<WindowSlider> exponents; | 260 | 3.69k | exponents.reserve(expCount); | 261 | 3.69k | unsigned int i; | 262 | | | 263 | 7.38k | for (i=0; expBegin && i<expCount; i++) | 264 | 3.69k | { | 265 | 3.69k | CRYPTOPP_ASSERT(expBegin->NotNegative()); | 266 | 3.69k | exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0)); | 267 | 3.69k | exponents[i].FindNextWindow(); | 268 | 3.69k | buckets[i].resize(((size_t) 1) << (exponents[i].windowSize-1), Identity()); | 269 | 3.69k | } | 270 | | | 271 | 3.69k | unsigned int expBitPosition = 0; | 272 | 3.69k | Element g = base; | 273 | 3.69k | bool notDone = true; | 274 | | | 275 | 1.87M | while (notDone) | 276 | 1.87M | { | 277 | 1.87M | notDone = false; | 278 | 3.74M | for (i=0; i<expCount; i++) | 279 | 1.87M | { | 280 | 1.87M | if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin) | 281 | 263k | { | 282 | 263k | Element &bucket = buckets[i][exponents[i].expWindow/2]; | 283 | 263k | if (exponents[i].negateNext) | 284 | 0 | Accumulate(bucket, Inverse(g)); | 285 | 263k | else | 286 | 263k | Accumulate(bucket, g); | 287 | 263k | exponents[i].FindNextWindow(); | 288 | 263k | } | 289 | 1.87M | notDone = notDone || !exponents[i].finished; | 290 | 1.87M | } | 291 | | | 292 | 1.87M | if (notDone) | 293 | 1.87M | { | 294 | 1.87M | g = Double(g); | 295 | 1.87M | expBitPosition++; | 296 | 1.87M | } | 297 | 1.87M | } | 298 | | | 299 | 7.38k | for (i=0; i<expCount; i++) | 300 | 3.69k | { | 301 | 3.69k | Element &r = *results++; | 302 | 3.69k | r = buckets[i][buckets[i].size()-1]; | 303 | 3.69k | if (buckets[i].size() > 1) | 304 | 3.35k | { | 305 | 56.9k | for (int j = (int)buckets[i].size()-2; j >= 1; j--) | 306 | 53.6k | { | 307 | 53.6k | Accumulate(buckets[i][j], buckets[i][j+1]); | 308 | 53.6k | Accumulate(r, buckets[i][j]); | 309 | 53.6k | } | 310 | 3.35k | Accumulate(buckets[i][0], buckets[i][1]); | 311 | 3.35k | r = Add(Double(r), buckets[i][0]); | 312 | 3.35k | } | 313 | 3.69k | } | 314 | 3.69k | } |
Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::PolynomialMod2>::SimultaneousMultiply(CryptoPP::PolynomialMod2*, CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const*, unsigned int) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::ECPPoint>::SimultaneousMultiply(CryptoPP::ECPPoint*, CryptoPP::ECPPoint const&, CryptoPP::Integer const*, unsigned int) const Unexecuted instantiation: CryptoPP::AbstractGroup<CryptoPP::EC2NPoint>::SimultaneousMultiply(CryptoPP::EC2NPoint*, CryptoPP::EC2NPoint const&, CryptoPP::Integer const*, unsigned int) const |
315 | | |
316 | | template <class T> T AbstractRing<T>::Exponentiate(const Element &base, const Integer &exponent) const |
317 | 3.69k | { |
318 | 3.69k | Element result; |
319 | 3.69k | SimultaneousExponentiate(&result, base, &exponent, 1); |
320 | 3.69k | return result; |
321 | 3.69k | } CryptoPP::AbstractRing<CryptoPP::Integer>::Exponentiate(CryptoPP::Integer const&, CryptoPP::Integer const&) const Line | Count | Source | 317 | 3.69k | { | 318 | 3.69k | Element result; | 319 | 3.69k | SimultaneousExponentiate(&result, base, &exponent, 1); | 320 | 3.69k | return result; | 321 | 3.69k | } |
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::Exponentiate(CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&) const |
322 | | |
323 | | template <class T> T AbstractRing<T>::CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const |
324 | 0 | { |
325 | 0 | return MultiplicativeGroup().AbstractGroup<T>::CascadeScalarMultiply(x, e1, y, e2); |
326 | 0 | } Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::Integer>::CascadeExponentiate(CryptoPP::Integer const&, CryptoPP::Integer const&, CryptoPP::Integer const&, CryptoPP::Integer const&) const Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::CascadeExponentiate(CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&, CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const&) const |
327 | | |
328 | | template <class Element, class Iterator> Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end) |
329 | | { |
330 | | return GeneralCascadeMultiplication<Element>(ring.MultiplicativeGroup(), begin, end); |
331 | | } |
332 | | |
333 | | template <class T> |
334 | | void AbstractRing<T>::SimultaneousExponentiate(T *results, const T &base, const Integer *exponents, unsigned int expCount) const |
335 | 3.69k | { |
336 | 3.69k | MultiplicativeGroup().AbstractGroup<T>::SimultaneousMultiply(results, base, exponents, expCount); |
337 | 3.69k | } CryptoPP::AbstractRing<CryptoPP::Integer>::SimultaneousExponentiate(CryptoPP::Integer*, CryptoPP::Integer const&, CryptoPP::Integer const*, unsigned int) const Line | Count | Source | 335 | 3.69k | { | 336 | 3.69k | MultiplicativeGroup().AbstractGroup<T>::SimultaneousMultiply(results, base, exponents, expCount); | 337 | 3.69k | } |
Unexecuted instantiation: CryptoPP::AbstractRing<CryptoPP::PolynomialMod2>::SimultaneousExponentiate(CryptoPP::PolynomialMod2*, CryptoPP::PolynomialMod2 const&, CryptoPP::Integer const*, unsigned int) const |
338 | | |
339 | | NAMESPACE_END |
340 | | |
341 | | #endif |