00001
00002
00003 #include "pch.h"
00004
00005 #include "algebra.h"
00006 #include "integer.h"
00007
00008 #include <vector>
00009
00010 NAMESPACE_BEGIN(CryptoPP)
00011
00012 template <class T> const T& AbstractGroup<T>::Double(const Element &a) const
00013 {
00014 return Add(a, a);
00015 }
00016
00017 template <class T> const T& AbstractGroup<T>::Subtract(const Element &a, const Element &b) const
00018 {
00019
00020 Element a1(a);
00021 return Add(a1, Inverse(b));
00022 }
00023
00024 template <class T> T& AbstractGroup<T>::Accumulate(Element &a, const Element &b) const
00025 {
00026 return a = Add(a, b);
00027 }
00028
00029 template <class T> T& AbstractGroup<T>::Reduce(Element &a, const Element &b) const
00030 {
00031 return a = Subtract(a, b);
00032 }
00033
00034 template <class T> const T& AbstractRing<T>::Square(const Element &a) const
00035 {
00036 return Multiply(a, a);
00037 }
00038
00039 template <class T> const T& AbstractRing<T>::Divide(const Element &a, const Element &b) const
00040 {
00041
00042 Element a1(a);
00043 return Multiply(a1, MultiplicativeInverse(b));
00044 }
00045
00046 template <class T> const T& AbstractEuclideanDomain<T>::Mod(const Element &a, const Element &b) const
00047 {
00048 Element q;
00049 DivisionAlgorithm(result, q, a, b);
00050 return result;
00051 }
00052
00053 template <class T> const T& AbstractEuclideanDomain<T>::Gcd(const Element &a, const Element &b) const
00054 {
00055 Element g[3]={b, a};
00056 unsigned int i0=0, i1=1, i2=2;
00057
00058 while (!Equal(g[i1], Identity()))
00059 {
00060 g[i2] = Mod(g[i0], g[i1]);
00061 unsigned int t = i0; i0 = i1; i1 = i2; i2 = t;
00062 }
00063
00064 return result = g[i0];
00065 }
00066
00067 template <class T> const typename QuotientRing<T>::Element& QuotientRing<T>::MultiplicativeInverse(const Element &a) const
00068 {
00069 Element g[3]={m_modulus, a};
00070 #ifdef __BCPLUSPLUS__
00071
00072 Element v[3];
00073 v[0]=m_domain.Identity();
00074 v[1]=m_domain.MultiplicativeIdentity();
00075 #else
00076 Element v[3]={m_domain.Identity(), m_domain.MultiplicativeIdentity()};
00077 #endif
00078 Element y;
00079 unsigned int i0=0, i1=1, i2=2;
00080
00081 while (!Equal(g[i1], Identity()))
00082 {
00083
00084
00085 m_domain.DivisionAlgorithm(g[i2], y, g[i0], g[i1]);
00086
00087 v[i2] = m_domain.Subtract(v[i0], m_domain.Multiply(v[i1], y));
00088 unsigned int t = i0; i0 = i1; i1 = i2; i2 = t;
00089 }
00090
00091 return m_domain.IsUnit(g[i0]) ? m_domain.Divide(v[i0], g[i0]) : m_domain.Identity();
00092 }
00093
00094 template <class T> T AbstractGroup<T>::ScalarMultiply(const Element &base, const Integer &exponent) const
00095 {
00096 Element result;
00097 SimultaneousMultiply(&result, base, &exponent, 1);
00098 return result;
00099 }
00100
00101 template <class T> T AbstractGroup<T>::CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
00102 {
00103 const unsigned expLen = STDMAX(e1.BitCount(), e2.BitCount());
00104 if (expLen==0)
00105 return Identity();
00106
00107 const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3));
00108 const unsigned tableSize = 1<<w;
00109 std::vector<Element> powerTable(tableSize << w);
00110
00111 powerTable[1] = x;
00112 powerTable[tableSize] = y;
00113 if (w==1)
00114 powerTable[3] = Add(x,y);
00115 else
00116 {
00117 powerTable[2] = Double(x);
00118 powerTable[2*tableSize] = Double(y);
00119
00120 unsigned i, j;
00121
00122 for (i=3; i<tableSize; i+=2)
00123 powerTable[i] = Add(powerTable[i-2], powerTable[2]);
00124 for (i=1; i<tableSize; i+=2)
00125 for (j=i+tableSize; j<(tableSize<<w); j+=tableSize)
00126 powerTable[j] = Add(powerTable[j-tableSize], y);
00127
00128 for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize)
00129 powerTable[i] = Add(powerTable[i-2*tableSize], powerTable[2*tableSize]);
00130 for (i=tableSize; i<(tableSize<<w); i+=2*tableSize)
00131 for (j=i+2; j<i+tableSize; j+=2)
00132 powerTable[j] = Add(powerTable[j-1], x);
00133 }
00134
00135 Element result;
00136 unsigned power1 = 0, power2 = 0, prevPosition = expLen-1;
00137 bool firstTime = true;
00138
00139 for (int i = expLen-1; i>=0; i--)
00140 {
00141 power1 = 2*power1 + e1.GetBit(i);
00142 power2 = 2*power2 + e2.GetBit(i);
00143
00144 if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize)
00145 {
00146 unsigned squaresBefore = prevPosition-i;
00147 unsigned squaresAfter = 0;
00148 prevPosition = i;
00149 while ((power1 || power2) && power1%2 == 0 && power2%2==0)
00150 {
00151 power1 /= 2;
00152 power2 /= 2;
00153 squaresBefore--;
00154 squaresAfter++;
00155 }
00156 if (firstTime)
00157 {
00158 result = powerTable[(power2<<w) + power1];
00159 firstTime = false;
00160 }
00161 else
00162 {
00163 while (squaresBefore--)
00164 result = Double(result);
00165 if (power1 || power2)
00166 Accumulate(result, powerTable[(power2<<w) + power1]);
00167 }
00168 while (squaresAfter--)
00169 result = Double(result);
00170 power1 = power2 = 0;
00171 }
00172 }
00173 return result;
00174 }
00175
00176 template <class Element, class Iterator> Element GeneralCascadeMultiplication(const AbstractGroup<Element> &group, Iterator begin, Iterator end)
00177 {
00178 if (end-begin == 1)
00179 return group.ScalarMultiply(begin->base, begin->exponent);
00180 else if (end-begin == 2)
00181 return group.CascadeScalarMultiply(begin->base, begin->exponent, (begin+1)->base, (begin+1)->exponent);
00182 else
00183 {
00184 Integer q, t;
00185 Iterator last = end;
00186 --last;
00187
00188 std::make_heap(begin, end);
00189 std::pop_heap(begin, end);
00190
00191 while (!!begin->exponent)
00192 {
00193
00194 t = last->exponent;
00195 Integer::Divide(last->exponent, q, t, begin->exponent);
00196
00197 if (q == Integer::One())
00198 group.Accumulate(begin->base, last->base);
00199 else
00200 group.Accumulate(begin->base, group.ScalarMultiply(last->base, q));
00201
00202 std::push_heap(begin, end);
00203 std::pop_heap(begin, end);
00204 }
00205
00206 return group.ScalarMultiply(last->base, last->exponent);
00207 }
00208 }
00209
00210 struct WindowSlider
00211 {
00212 WindowSlider(const Integer &exp, bool fastNegate, unsigned int windowSizeIn=0)
00213 : exp(exp), windowModulus(Integer::One()), windowSize(windowSizeIn), windowBegin(0), fastNegate(fastNegate), firstTime(true), finished(false)
00214 {
00215 if (windowSize == 0)
00216 {
00217 unsigned int expLen = exp.BitCount();
00218 windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 : (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 : (expLen <= 1434 ? 6 : 7)))));
00219 }
00220 windowModulus <<= windowSize;
00221 }
00222
00223 void FindNextWindow()
00224 {
00225 unsigned int expLen = exp.WordCount() * WORD_BITS;
00226 unsigned int skipCount = firstTime ? 0 : windowSize;
00227 firstTime = false;
00228 while (!exp.GetBit(skipCount))
00229 {
00230 if (skipCount >= expLen)
00231 {
00232 finished = true;
00233 return;
00234 }
00235 skipCount++;
00236 }
00237
00238 exp >>= skipCount;
00239 windowBegin += skipCount;
00240 expWindow = exp % (1 << windowSize);
00241
00242 if (fastNegate && exp.GetBit(windowSize))
00243 {
00244 negateNext = true;
00245 expWindow = (1 << windowSize) - expWindow;
00246 exp += windowModulus;
00247 }
00248 else
00249 negateNext = false;
00250 }
00251
00252 Integer exp, windowModulus;
00253 unsigned int windowSize, windowBegin, expWindow;
00254 bool fastNegate, negateNext, firstTime, finished;
00255 };
00256
00257 template <class T>
00258 void AbstractGroup<T>::SimultaneousMultiply(T *results, const T &base, const Integer *expBegin, unsigned int expCount) const
00259 {
00260 std::vector<std::vector<Element> > buckets(expCount);
00261 std::vector<WindowSlider> exponents;
00262 exponents.reserve(expCount);
00263 unsigned int i;
00264
00265 for (i=0; i<expCount; i++)
00266 {
00267 assert(expBegin->NotNegative());
00268 exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0));
00269 exponents[i].FindNextWindow();
00270 buckets[i].resize(1<<(exponents[i].windowSize-1), Identity());
00271 }
00272
00273 unsigned int expBitPosition = 0;
00274 Element g = base;
00275 bool notDone = true;
00276
00277 while (notDone)
00278 {
00279 notDone = false;
00280 for (i=0; i<expCount; i++)
00281 {
00282 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
00283 {
00284 Element &bucket = buckets[i][exponents[i].expWindow/2];
00285 if (exponents[i].negateNext)
00286 Accumulate(bucket, Inverse(g));
00287 else
00288 Accumulate(bucket, g);
00289 exponents[i].FindNextWindow();
00290 }
00291 notDone = notDone || !exponents[i].finished;
00292 }
00293
00294 if (notDone)
00295 {
00296 g = Double(g);
00297 expBitPosition++;
00298 }
00299 }
00300
00301 for (i=0; i<expCount; i++)
00302 {
00303 Element &r = *results++;
00304 r = buckets[i][buckets[i].size()-1];
00305 if (buckets[i].size() > 1)
00306 {
00307 for (int j = buckets[i].size()-2; j >= 1; j--)
00308 {
00309 Accumulate(buckets[i][j], buckets[i][j+1]);
00310 Accumulate(r, buckets[i][j]);
00311 }
00312 Accumulate(buckets[i][0], buckets[i][1]);
00313 r = Add(Double(r), buckets[i][0]);
00314 }
00315 }
00316 }
00317
00318 template <class T> T AbstractRing<T>::Exponentiate(const Element &base, const Integer &exponent) const
00319 {
00320 Element result;
00321 SimultaneousExponentiate(&result, base, &exponent, 1);
00322 return result;
00323 }
00324
00325 template <class T> T AbstractRing<T>::CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
00326 {
00327 return MultiplicativeGroup().AbstractGroup<T>::CascadeScalarMultiply(x, e1, y, e2);
00328 }
00329
00330 template <class Element, class Iterator> Element GeneralCascadeExponentiation(const AbstractRing<Element> &ring, Iterator begin, Iterator end)
00331 {
00332 return GeneralCascadeMultiplication<Element>(ring.MultiplicativeGroup(), begin, end);
00333 }
00334
00335 template <class T>
00336 void AbstractRing<T>::SimultaneousExponentiate(T *results, const T &base, const Integer *exponents, unsigned int expCount) const
00337 {
00338 MultiplicativeGroup().AbstractGroup<T>::SimultaneousMultiply(results, base, exponents, expCount);
00339 }
00340
00341 NAMESPACE_END