5 #ifndef CRYPTOPP_ALGEBRA_CPP // SunCC workaround: compiler could cause this file to be included twice
6 #define CRYPTOPP_ALGEBRA_CPP
13 NAMESPACE_BEGIN(CryptoPP)
15 template <class T> const T&
AbstractGroup<T>::Double(const Element &a)
const
17 return this->Add(a, a);
24 return this->Add(a1, Inverse(b));
29 return a = this->Add(a, b);
34 return a = this->Subtract(a, b);
39 return this->Multiply(a, a);
46 return this->Multiply(a1, this->MultiplicativeInverse(b));
52 this->DivisionAlgorithm(result, q, a, b);
59 unsigned int i0=0, i1=1, i2=2;
61 while (!this->Equal(g[i1], this->Identity()))
63 g[i2] = this->Mod(g[i0], g[i1]);
64 unsigned int t = i0; i0 = i1; i1 = i2; i2 = t;
67 return result = g[i0];
72 Element g[3]={m_modulus, a};
73 Element v[3]={m_domain.Identity(), m_domain.MultiplicativeIdentity()};
75 unsigned int i0=0, i1=1, i2=2;
77 while (!this->Equal(g[i1], this->Identity()))
81 m_domain.DivisionAlgorithm(g[i2], y, g[i0], g[i1]);
83 v[i2] = m_domain.Subtract(v[i0], m_domain.Multiply(v[i1], y));
84 unsigned int t = i0; i0 = i1; i1 = i2; i2 = t;
87 return m_domain.IsUnit(g[i0]) ? m_domain.Divide(v[i0], g[i0]) : m_domain.Identity();
93 this->SimultaneousMultiply(&result, base, &exponent, 1);
101 return this->Identity();
103 const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3));
104 const unsigned tableSize = 1<<w;
105 std::vector<Element> powerTable(tableSize << w);
108 powerTable[tableSize] = y;
110 powerTable[3] = this->Add(x,y);
113 powerTable[2] = this->Double(x);
114 powerTable[2*tableSize] = this->Double(y);
118 for (i=3; i<tableSize; i+=2)
119 powerTable[i] = Add(powerTable[i-2], powerTable[2]);
120 for (i=1; i<tableSize; i+=2)
121 for (j=i+tableSize; j<(tableSize<<w); j+=tableSize)
122 powerTable[j] = Add(powerTable[j-tableSize], y);
124 for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize)
125 powerTable[i] = Add(powerTable[i-2*tableSize], powerTable[2*tableSize]);
126 for (i=tableSize; i<(tableSize<<w); i+=2*tableSize)
127 for (j=i+2; j<i+tableSize; j+=2)
128 powerTable[j] = Add(powerTable[j-1], x);
132 unsigned power1 = 0, power2 = 0, prevPosition = expLen-1;
133 bool firstTime =
true;
135 for (
int i = expLen-1; i>=0; i--)
137 power1 = 2*power1 + e1.
GetBit(i);
138 power2 = 2*power2 + e2.
GetBit(i);
140 if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize)
142 unsigned squaresBefore = prevPosition-i;
143 unsigned squaresAfter = 0;
145 while ((power1 || power2) && power1%2 == 0 && power2%2==0)
154 result = powerTable[(power2<<w) + power1];
159 while (squaresBefore--)
160 result = this->Double(result);
161 if (power1 || power2)
162 Accumulate(result, powerTable[(power2<<w) + power1]);
164 while (squaresAfter--)
165 result = this->Double(result);
172 template <
class Element,
class Iterator> Element GeneralCascadeMultiplication(
const AbstractGroup<Element> &group, Iterator begin, Iterator end)
175 return group.ScalarMultiply(begin->base, begin->exponent);
176 else if (end-begin == 2)
177 return group.CascadeScalarMultiply(begin->base, begin->exponent, (begin+1)->base, (begin+1)->exponent);
184 std::make_heap(begin, end);
185 std::pop_heap(begin, end);
187 while (!!begin->exponent)
194 group.Accumulate(begin->base, last->base);
196 group.Accumulate(begin->base, group.ScalarMultiply(last->base, q));
198 std::push_heap(begin, end);
199 std::pop_heap(begin, end);
202 return group.ScalarMultiply(last->base, last->exponent);
209 : exp(expIn), windowModulus(
Integer::One()), windowSize(windowSizeIn), windowBegin(0), fastNegate(fastNegate), firstTime(
true), finished(
false)
213 unsigned int expLen = exp.
BitCount();
214 windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 : (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 : (expLen <= 1434 ? 6 : 7)))));
216 windowModulus <<= windowSize;
219 void FindNextWindow()
221 unsigned int expLen = exp.
WordCount() * WORD_BITS;
222 unsigned int skipCount = firstTime ? 0 : windowSize;
224 while (!exp.
GetBit(skipCount))
226 if (skipCount >= expLen)
235 windowBegin += skipCount;
236 expWindow = word32(exp % (word(1) << windowSize));
238 if (fastNegate && exp.
GetBit(windowSize))
241 expWindow = (word32(1) << windowSize) - expWindow;
242 exp += windowModulus;
249 unsigned int windowSize, windowBegin;
251 bool fastNegate, negateNext, firstTime, finished;
257 std::vector<std::vector<Element> > buckets(expCount);
258 std::vector<WindowSlider> exponents;
259 exponents.reserve(expCount);
262 for (i=0; i<expCount; i++)
264 assert(expBegin->NotNegative());
265 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 0));
266 exponents[i].FindNextWindow();
267 buckets[i].resize(1<<(exponents[i].windowSize-1), Identity());
270 unsigned int expBitPosition = 0;
277 for (i=0; i<expCount; i++)
279 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
281 Element &bucket = buckets[i][exponents[i].expWindow/2];
282 if (exponents[i].negateNext)
283 Accumulate(bucket, Inverse(g));
285 Accumulate(bucket, g);
286 exponents[i].FindNextWindow();
288 notDone = notDone || !exponents[i].finished;
298 for (i=0; i<expCount; i++)
300 Element &r = *results++;
301 r = buckets[i][buckets[i].size()-1];
302 if (buckets[i].size() > 1)
304 for (
int j = (
int)buckets[i].size()-2; j >= 1; j--)
306 Accumulate(buckets[i][j], buckets[i][j+1]);
307 Accumulate(r, buckets[i][j]);
309 Accumulate(buckets[i][0], buckets[i][1]);
310 r = Add(Double(r), buckets[i][0]);
318 SimultaneousExponentiate(&result, base, &exponent, 1);
324 return MultiplicativeGroup().AbstractGroup<T>::CascadeScalarMultiply(x, e1, y, e2);
327 template <
class Element,
class Iterator> Element GeneralCascadeExponentiation(
const AbstractRing<Element> &ring, Iterator begin, Iterator end)
329 return GeneralCascadeMultiplication<Element>(ring.MultiplicativeGroup(), begin, end);
335 MultiplicativeGroup().AbstractGroup<T>::SimultaneousMultiply(results, base, exponents, expCount);