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)
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)
198 std::push_heap(begin, end);
199 std::pop_heap(begin, end);
209 : exp(expIn), windowModulus(
Integer::One()), windowSize(windowSizeIn), windowBegin(0), expWindow(0)
210 , fastNegate(fastNegate), negateNext(
false), firstTime(
true), finished(
false)
214 unsigned int expLen = exp.
BitCount();
215 windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 : (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 : (expLen <= 1434 ? 6 : 7)))));
217 windowModulus <<= windowSize;
220 void FindNextWindow()
222 unsigned int expLen = exp.
WordCount() * WORD_BITS;
223 unsigned int skipCount = firstTime ? 0 : windowSize;
225 while (!exp.
GetBit(skipCount))
227 if (skipCount >= expLen)
236 windowBegin += skipCount;
237 expWindow = word32(exp % (word(1) << windowSize));
239 if (fastNegate && exp.
GetBit(windowSize))
242 expWindow = (word32(1) << windowSize) - expWindow;
243 exp += windowModulus;
250 unsigned int windowSize, windowBegin;
252 bool fastNegate, negateNext, firstTime, finished;
258 std::vector<std::vector<Element> > buckets(expCount);
259 std::vector<WindowSlider> exponents;
260 exponents.reserve(expCount);
263 for (i=0; i<expCount; i++)
266 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 0));
267 exponents[i].FindNextWindow();
268 buckets[i].resize(((
size_t) 1) << (exponents[i].windowSize-1), Identity());
271 unsigned int expBitPosition = 0;
278 for (i=0; i<expCount; i++)
280 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
282 Element &bucket = buckets[i][exponents[i].expWindow/2];
283 if (exponents[i].negateNext)
284 Accumulate(bucket, Inverse(g));
286 Accumulate(bucket, g);
287 exponents[i].FindNextWindow();
289 notDone = notDone || !exponents[i].finished;
299 for (i=0; i<expCount; i++)
301 Element &r = *results++;
302 r = buckets[i][buckets[i].size()-1];
303 if (buckets[i].size() > 1)
305 for (
int j = (
int)buckets[i].size()-2; j >= 1; j--)
307 Accumulate(buckets[i][j], buckets[i][j+1]);
308 Accumulate(r, buckets[i][j]);
310 Accumulate(buckets[i][0], buckets[i][1]);
311 r = Add(Double(r), buckets[i][0]);
319 SimultaneousExponentiate(&result, base, &exponent, 1);
325 return MultiplicativeGroup().AbstractGroup<T>::CascadeScalarMultiply(x, e1, y, e2);
328 template <
class Element,
class Iterator> Element GeneralCascadeExponentiation(
const AbstractRing<Element> &ring, Iterator begin, Iterator end)
336 MultiplicativeGroup().AbstractGroup<T>::SimultaneousMultiply(results, base, exponents, expCount);
virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
virtual const Element & Divide(const Element &a, const Element &b) const
Divides elements in the group.
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
virtual const Element & Subtract(const Element &a, const Element &b) const
Subtracts elements in the group.
virtual Element ScalarMultiply(const Element &a, const Integer &e) const
Performs a scalar multiplication.
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
virtual const AbstractGroup< T > & MultiplicativeGroup() const
Retrieves the multiplicative group.
virtual Element & Accumulate(Element &a, const Element &b) const
TODO.
virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the Ring.
Classes for performing mathematics over different fields.
static const Integer & One()
Integer representing 1.
virtual const Element & Square(const Element &a) const
Square an element in the group.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Multiple precision integer with arithmetic operations.
virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
virtual Element & Reduce(Element &a, const Element &b) const
Reduces an element in the congruence class.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d)
calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
virtual const Element & Mod(const Element &a, const Element &b) const =0
Performs a modular reduction in the ring.
Multiple precision integer with arithmetic operations.
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
virtual const Element & Gcd(const Element &a, const Element &b) const
Calculates the greatest common denominator in the ring.
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
virtual Element Exponentiate(const Element &a, const Integer &e) const
Raises a base to an exponent in the group.
bool NotNegative() const
Determines if the Integer is non-negative.