algebra_8cpp-source.html

Crypto++是一个非常强大的密码学库,主要是功能全

00172         }
00173         <span class="keywordflow">return</span> result;
00174 }
00175 
00176 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Element, <span class="keyword">class</span> Iterator&gt; Element GeneralCascadeMultiplication(<span class="keyword">const</span> <a class="code" href="class_abstract_group.html">AbstractGroup&lt;Element&gt;</a> &amp;group, Iterator begin, Iterator end)
00177 {
00178         <span class="keywordflow">if</span> (end-begin == 1)
00179                 <span class="keywordflow">return</span> group.<a class="code" href="class_abstract_group.html#_euclidean_domain_ofa23">ScalarMultiply</a>(begin-&gt;base, begin-&gt;exponent);
00180         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (end-begin == 2)
00181                 <span class="keywordflow">return</span> group.<a class="code" href="class_abstract_group.html#_euclidean_domain_ofa24">CascadeScalarMultiply</a>(begin-&gt;base, begin-&gt;exponent, (begin+1)-&gt;base, (begin+1)-&gt;exponent);
00182         <span class="keywordflow">else</span>
00183         {
00184                 <a class="code" href="class_integer.html">Integer</a> q, t;
00185                 Iterator last = end;
00186                 --last;
00187 
00188                 std::make_heap(begin, end);
00189                 std::pop_heap(begin, end);
00190 
00191                 <span class="keywordflow">while</span> (!!begin-&gt;exponent)
00192                 {
00193                         <span class="comment">// last-&gt;exponent is largest exponent, begin-&gt;exponent is next largest</span>
00194                         t = last-&gt;exponent;
00195                         <a class="code" href="class_integer.html#_integerz49_9">Integer::Divide</a>(last-&gt;exponent, q, t, begin-&gt;exponent);
00196 
00197                         <span class="keywordflow">if</span> (q == <a class="code" href="class_integer.html#_integerz37_11">Integer::One</a>())
00198                                 group.<a class="code" href="class_abstract_group.html#_abstract_ringa20">Accumulate</a>(begin-&gt;base, last-&gt;base);      <span class="comment">// avoid overhead of ScalarMultiply()</span>
00199                         <span class="keywordflow">else</span>
00200                                 group.<a class="code" href="class_abstract_group.html#_abstract_ringa20">Accumulate</a>(begin-&gt;base, group.<a class="code" href="class_abstract_group.html#_euclidean_domain_ofa23">ScalarMultiply</a>(last-&gt;base, q));
00201 
00202                         std::push_heap(begin, end);
00203                         std::pop_heap(begin, end);
00204                 }
00205 
00206                 <span class="keywordflow">return</span> group.<a class="code" href="class_abstract_group.html#_euclidean_domain_ofa23">ScalarMultiply</a>(last-&gt;base, last-&gt;exponent);
00207         }
00208 }
00209 
00210 <span class="keyword">struct </span>WindowSlider
00211 {
00212         WindowSlider(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;exp, <span class="keywordtype">bool</span> fastNegate, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> windowSizeIn=0)
00213                 : exp(exp), windowModulus(<a class="code" href="class_integer.html">Integer</a>::One()), windowSize(windowSizeIn), windowBegin(0), fastNegate(fastNegate), firstTime(true), finished(false)
00214         {
00215                 <span class="keywordflow">if</span> (windowSize == 0)
00216                 {
00217                         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expLen = exp.<a class="code" href="class_integer.html#_integerz41_2">BitCount</a>();
00218                         windowSize = expLen &lt;= 17 ? 1 : (expLen &lt;= 24 ? 2 : (expLen &lt;= 70 ? 3 : (expLen &lt;= 197 ? 4 : (expLen &lt;= 539 ? 5 : (expLen &lt;= 1434 ? 6 : 7)))));
00219                 }
00220                 windowModulus &lt;&lt;= windowSize;
00221         }
00222 
00223         <span class="keywordtype">void</span> FindNextWindow()
00224         {
00225                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expLen = exp.WordCount() * WORD_BITS;
00226                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> skipCount = firstTime ? 0 : windowSize;
00227                 firstTime = <span class="keyword">false</span>;
00228                 <span class="keywordflow">while</span> (!exp.GetBit(skipCount))
00229                 {
00230                         <span class="keywordflow">if</span> (skipCount &gt;= expLen)
00231                         {
00232                                 finished = <span class="keyword">true</span>;
00233                                 <span class="keywordflow">return</span>;
00234                         }
00235                         skipCount++;
00236                 }
00237 
00238                 exp &gt;&gt;= skipCount;
00239                 windowBegin += skipCount;
00240                 expWindow = exp % (1 &lt;&lt; windowSize);
00241 
00242                 <span class="keywordflow">if</span> (fastNegate &amp;&amp; exp.GetBit(windowSize))
00243                 {
00244                         negateNext = <span class="keyword">true</span>;
00245                         expWindow = (1 &lt;&lt; windowSize) - expWindow;
00246                         exp += windowModulus;
00247                 }
00248                 <span class="keywordflow">else</span>
00249                         negateNext = <span class="keyword">false</span>;
00250         }
00251 
00252         <a class="code" href="class_integer.html">Integer</a> exp, windowModulus;
00253         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> windowSize, windowBegin, expWindow;
00254         <span class="keywordtype">bool</span> fastNegate, negateNext, firstTime, finished;
00255 };
00256 
00257 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
00258 <span class="keywordtype">void</span> <a class="code" href="class_abstract_group.html">AbstractGroup&lt;T&gt;::SimultaneousMultiply</a>(T *results, <span class="keyword">const</span> T &amp;base, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> *expBegin, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expCount)<span class="keyword"> const</span>
00259 <span class="keyword"></span>{
00260         std::vector&lt;std::vector&lt;Element&gt; &gt; buckets(expCount);
00261         std::vector&lt;WindowSlider&gt; exponents;
00262         exponents.reserve(expCount);
00263         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
00264 
00265         <span class="keywordflow">for</span> (i=0; i&lt;expCount; i++)
00266         {
00267                 assert(expBegin-&gt;<a class="code" href="class_integer.html#_integerz41_11">NotNegative</a>());
00268                 exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0));
00269                 exponents[i].FindNextWindow();
00270                 buckets[i].resize(1&lt;&lt;(exponents[i].windowSize-1), Identity());
00271         }
00272 
00273         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expBitPosition = 0;
00274         Element g = base;
00275         <span class="keywordtype">bool</span> notDone = <span class="keyword">true</span>;
00276 
00277         <span class="keywordflow">while</span> (notDone)
00278         {
00279                 notDone = <span class="keyword">false</span>;
00280                 <span class="keywordflow">for</span> (i=0; i&lt;expCount; i++)
00281                 {
00282                         <span class="keywordflow">if</span> (!exponents[i].finished &amp;&amp; expBitPosition == exponents[i].windowBegin)
00283                         {
00284                                 Element &amp;bucket = buckets[i][exponents[i].expWindow/2];
00285                                 <span class="keywordflow">if</span> (exponents[i].negateNext)
00286                                         Accumulate(bucket, Inverse(g));
00287                                 <span class="keywordflow">else</span>
00288                                         Accumulate(bucket, g);
00289                                 exponents[i].FindNextWindow();
00290                         }
00291                         notDone = notDone || !exponents[i].finished;
00292                 }
00293 
00294                 <span class="keywordflow">if</span> (notDone)
00295                 {
00296                         g = Double(g);
00297                         expBitPosition++;
00298                 }
00299         }
00300 
00301         <span class="keywordflow">for</span> (i=0; i&lt;expCount; i++)
00302         {
00303                 Element &amp;r = *results++;
00304                 r = buckets[i][buckets[i].size()-1];
00305                 <span class="keywordflow">if</span> (buckets[i].size() &gt; 1)
00306                 {
00307                         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j = buckets[i].size()-2; j &gt;= 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 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt; T <a class="code" href="class_abstract_ring.html">AbstractRing&lt;T&gt;::Exponentiate</a>(<span class="keyword">const</span> Element &amp;base, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;exponent)<span class="keyword"> const</span>
00319 <span class="keyword"></span>{
00320         Element result;
00321         SimultaneousExponentiate(&amp;result, base, &amp;exponent, 1);
00322         <span class="keywordflow">return</span> result;
00323 }
00324 
00325 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt; T <a class="code" href="class_abstract_ring.html">AbstractRing&lt;T&gt;::CascadeExponentiate</a>(<span class="keyword">const</span> Element &amp;x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;e1, <span class="keyword">const</span> Element &amp;y, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;e2)<span class="keyword"> const</span>
00326 <span class="keyword"></span>{
00327         <span class="keywordflow">return</span> MultiplicativeGroup().AbstractGroup&lt;T&gt;::CascadeScalarMultiply(x, e1, y, e2);
00328 }
00329 
00330 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Element, <span class="keyword">class</span> Iterator&gt; Element GeneralCascadeExponentiation(<span class="keyword">const</span> <a class="code" href="class_abstract_ring.html">AbstractRing&lt;Element&gt;</a> &amp;ring, Iterator begin, Iterator end)
00331 {
00332         <span class="keywordflow">return</span> GeneralCascadeMultiplication&lt;Element&gt;(ring.<a class="code" href="class_abstract_ring.html#_euclidean_domain_ofa21">MultiplicativeGroup</a>(), begin, end);
00333 }
00334 
00335 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
00336 <span class="keywordtype">void</span> <a class="code" href="class_abstract_ring.html">AbstractRing&lt;T&gt;::SimultaneousExponentiate</a>(T *results, <span class="keyword">const</span> T &amp;base, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> *exponents, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expCount)<span class="keyword"> const</span>
00337 <span class="keyword"></span>{
00338         MultiplicativeGroup().AbstractGroup&lt;T&gt;::SimultaneousMultiply(results, base, exponents, expCount);
00339 }
00340 
00341 NAMESPACE_END
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Tue Jul 8 23:34:07 2003 for Crypto++ by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 > 
</a>1.3.2 </small></address>
</body>
</html>