From 5e60e0e3af85f22aa0afe8bf0ecf85619afacfeb Mon Sep 17 00:00:00 2001 From: Micah Anderson Date: Thu, 22 Aug 2013 16:39:52 -0400 Subject: Imported Upstream version 0.6.0.12 --- src-cryptopp/algebra.cpp | 340 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 340 insertions(+) create mode 100644 src-cryptopp/algebra.cpp (limited to 'src-cryptopp/algebra.cpp') diff --git a/src-cryptopp/algebra.cpp b/src-cryptopp/algebra.cpp new file mode 100644 index 0000000..b8818e6 --- /dev/null +++ b/src-cryptopp/algebra.cpp @@ -0,0 +1,340 @@ +// algebra.cpp - written and placed in the public domain by Wei Dai + +#include "pch.h" + +#ifndef CRYPTOPP_ALGEBRA_CPP // SunCC workaround: compiler could cause this file to be included twice +#define CRYPTOPP_ALGEBRA_CPP + +#include "algebra.h" +#include "integer.h" + +#include + +NAMESPACE_BEGIN(CryptoPP) + +template const T& AbstractGroup::Double(const Element &a) const +{ + return Add(a, a); +} + +template const T& AbstractGroup::Subtract(const Element &a, const Element &b) const +{ + // make copy of a in case Inverse() overwrites it + Element a1(a); + return Add(a1, Inverse(b)); +} + +template T& AbstractGroup::Accumulate(Element &a, const Element &b) const +{ + return a = Add(a, b); +} + +template T& AbstractGroup::Reduce(Element &a, const Element &b) const +{ + return a = Subtract(a, b); +} + +template const T& AbstractRing::Square(const Element &a) const +{ + return Multiply(a, a); +} + +template const T& AbstractRing::Divide(const Element &a, const Element &b) const +{ + // make copy of a in case MultiplicativeInverse() overwrites it + Element a1(a); + return Multiply(a1, MultiplicativeInverse(b)); +} + +template const T& AbstractEuclideanDomain::Mod(const Element &a, const Element &b) const +{ + Element q; + DivisionAlgorithm(result, q, a, b); + return result; +} + +template const T& AbstractEuclideanDomain::Gcd(const Element &a, const Element &b) const +{ + Element g[3]={b, a}; + unsigned int i0=0, i1=1, i2=2; + + while (!this->Equal(g[i1], this->Identity())) + { + g[i2] = Mod(g[i0], g[i1]); + unsigned int t = i0; i0 = i1; i1 = i2; i2 = t; + } + + return result = g[i0]; +} + +template const typename QuotientRing::Element& QuotientRing::MultiplicativeInverse(const Element &a) const +{ + Element g[3]={m_modulus, a}; + Element v[3]={m_domain.Identity(), m_domain.MultiplicativeIdentity()}; + Element y; + unsigned int i0=0, i1=1, i2=2; + + while (!Equal(g[i1], Identity())) + { + // y = g[i0] / g[i1]; + // g[i2] = g[i0] % g[i1]; + m_domain.DivisionAlgorithm(g[i2], y, g[i0], g[i1]); + // v[i2] = v[i0] - (v[i1] * y); + v[i2] = m_domain.Subtract(v[i0], m_domain.Multiply(v[i1], y)); + unsigned int t = i0; i0 = i1; i1 = i2; i2 = t; + } + + return m_domain.IsUnit(g[i0]) ? m_domain.Divide(v[i0], g[i0]) : m_domain.Identity(); +} + +template T AbstractGroup::ScalarMultiply(const Element &base, const Integer &exponent) const +{ + Element result; + SimultaneousMultiply(&result, base, &exponent, 1); + return result; +} + +template T AbstractGroup::CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const +{ + const unsigned expLen = STDMAX(e1.BitCount(), e2.BitCount()); + if (expLen==0) + return Identity(); + + const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3)); + const unsigned tableSize = 1< powerTable(tableSize << w); + + powerTable[1] = x; + powerTable[tableSize] = y; + if (w==1) + powerTable[3] = Add(x,y); + else + { + powerTable[2] = Double(x); + powerTable[2*tableSize] = Double(y); + + unsigned i, j; + + for (i=3; i=0; i--) + { + power1 = 2*power1 + e1.GetBit(i); + power2 = 2*power2 + e2.GetBit(i); + + if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize) + { + unsigned squaresBefore = prevPosition-i; + unsigned squaresAfter = 0; + prevPosition = i; + while ((power1 || power2) && power1%2 == 0 && power2%2==0) + { + power1 /= 2; + power2 /= 2; + squaresBefore--; + squaresAfter++; + } + if (firstTime) + { + result = powerTable[(power2< Element GeneralCascadeMultiplication(const AbstractGroup &group, Iterator begin, Iterator end) +{ + if (end-begin == 1) + return group.ScalarMultiply(begin->base, begin->exponent); + else if (end-begin == 2) + return group.CascadeScalarMultiply(begin->base, begin->exponent, (begin+1)->base, (begin+1)->exponent); + else + { + Integer q, t; + Iterator last = end; + --last; + + std::make_heap(begin, end); + std::pop_heap(begin, end); + + while (!!begin->exponent) + { + // last->exponent is largest exponent, begin->exponent is next largest + t = last->exponent; + Integer::Divide(last->exponent, q, t, begin->exponent); + + if (q == Integer::One()) + group.Accumulate(begin->base, last->base); // avoid overhead of ScalarMultiply() + else + group.Accumulate(begin->base, group.ScalarMultiply(last->base, q)); + + std::push_heap(begin, end); + std::pop_heap(begin, end); + } + + return group.ScalarMultiply(last->base, last->exponent); + } +} + +struct WindowSlider +{ + WindowSlider(const Integer &expIn, bool fastNegate, unsigned int windowSizeIn=0) + : exp(expIn), windowModulus(Integer::One()), windowSize(windowSizeIn), windowBegin(0), fastNegate(fastNegate), firstTime(true), finished(false) + { + if (windowSize == 0) + { + unsigned int expLen = exp.BitCount(); + windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 : (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 : (expLen <= 1434 ? 6 : 7))))); + } + windowModulus <<= windowSize; + } + + void FindNextWindow() + { + unsigned int expLen = exp.WordCount() * WORD_BITS; + unsigned int skipCount = firstTime ? 0 : windowSize; + firstTime = false; + while (!exp.GetBit(skipCount)) + { + if (skipCount >= expLen) + { + finished = true; + return; + } + skipCount++; + } + + exp >>= skipCount; + windowBegin += skipCount; + expWindow = word32(exp % (word(1) << windowSize)); + + if (fastNegate && exp.GetBit(windowSize)) + { + negateNext = true; + expWindow = (word32(1) << windowSize) - expWindow; + exp += windowModulus; + } + else + negateNext = false; + } + + Integer exp, windowModulus; + unsigned int windowSize, windowBegin; + word32 expWindow; + bool fastNegate, negateNext, firstTime, finished; +}; + +template +void AbstractGroup::SimultaneousMultiply(T *results, const T &base, const Integer *expBegin, unsigned int expCount) const +{ + std::vector > buckets(expCount); + std::vector exponents; + exponents.reserve(expCount); + unsigned int i; + + for (i=0; iNotNegative()); + exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0)); + exponents[i].FindNextWindow(); + buckets[i].resize(1<<(exponents[i].windowSize-1), Identity()); + } + + unsigned int expBitPosition = 0; + Element g = base; + bool notDone = true; + + while (notDone) + { + notDone = false; + for (i=0; i 1) + { + for (int j = (int)buckets[i].size()-2; j >= 1; j--) + { + Accumulate(buckets[i][j], buckets[i][j+1]); + Accumulate(r, buckets[i][j]); + } + Accumulate(buckets[i][0], buckets[i][1]); + r = Add(Double(r), buckets[i][0]); + } + } +} + +template T AbstractRing::Exponentiate(const Element &base, const Integer &exponent) const +{ + Element result; + SimultaneousExponentiate(&result, base, &exponent, 1); + return result; +} + +template T AbstractRing::CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const +{ + return MultiplicativeGroup().AbstractGroup::CascadeScalarMultiply(x, e1, y, e2); +} + +template Element GeneralCascadeExponentiation(const AbstractRing &ring, Iterator begin, Iterator end) +{ + return GeneralCascadeMultiplication(ring.MultiplicativeGroup(), begin, end); +} + +template +void AbstractRing::SimultaneousExponentiate(T *results, const T &base, const Integer *exponents, unsigned int expCount) const +{ + MultiplicativeGroup().AbstractGroup::SimultaneousMultiply(results, base, exponents, expCount); +} + +NAMESPACE_END + +#endif -- cgit v1.2.3