From 3438e5d3ddf8444f0e31009ffbe8237ef3752c22 Mon Sep 17 00:00:00 2001 From: Alexander Harkness Date: Sun, 24 Nov 2013 14:21:13 +0000 Subject: move cryptopp into lib --- CryptoPP/algebra.cpp | 340 --------------------------------------------------- 1 file changed, 340 deletions(-) delete mode 100644 CryptoPP/algebra.cpp (limited to 'CryptoPP/algebra.cpp') diff --git a/CryptoPP/algebra.cpp b/CryptoPP/algebra.cpp deleted file mode 100644 index 958e63701..000000000 --- a/CryptoPP/algebra.cpp +++ /dev/null @@ -1,340 +0,0 @@ -// 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 this->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 this->Add(a1, Inverse(b)); -} - -template T& AbstractGroup::Accumulate(Element &a, const Element &b) const -{ - return a = this->Add(a, b); -} - -template T& AbstractGroup::Reduce(Element &a, const Element &b) const -{ - return a = this->Subtract(a, b); -} - -template const T& AbstractRing::Square(const Element &a) const -{ - return this->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 this->Multiply(a1, this->MultiplicativeInverse(b)); -} - -template const T& AbstractEuclideanDomain::Mod(const Element &a, const Element &b) const -{ - Element q; - this->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] = this->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 (!this->Equal(g[i1], this->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; - this->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 this->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] = this->Add(x,y); - else - { - powerTable[2] = this->Double(x); - powerTable[2*tableSize] = this->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<Double(result); - if (power1 || power2) - Accumulate(result, powerTable[(power2<Double(result); - power1 = power2 = 0; - } - } - return result; -} - -template 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