Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

algebra.cpp

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

Generated on Fri Sep 9 19:01:20 2005 for Crypto++ by  doxygen 1.4.4