algebra_8cpp-source.html

著名的密码库Crypto++的文档 C++语言的杰作。程序员必备。

<a name="l00103"></a>00103         <span class="keyword">const</span> <span class="keywordtype">unsigned</span> w = (expLen &lt;= 46 ? 1 : (expLen &lt;= 260 ? 2 : 3));
<a name="l00104"></a>00104         <span class="keyword">const</span> <span class="keywordtype">unsigned</span> tableSize = 1&lt;&lt;w;
<a name="l00105"></a>00105         std::vector&lt;Element&gt; powerTable(tableSize &lt;&lt; w);
<a name="l00106"></a>00106 
<a name="l00107"></a>00107         powerTable[1] = x;
<a name="l00108"></a>00108         powerTable[tableSize] = y;
<a name="l00109"></a>00109         <span class="keywordflow">if</span> (w==1)
<a name="l00110"></a>00110                 powerTable[3] = Add(x,y);
<a name="l00111"></a>00111         <span class="keywordflow">else</span>
<a name="l00112"></a>00112         {
<a name="l00113"></a>00113                 powerTable[2] = <a class="code" href="class_abstract_group.html#e54ef772d5f231729e188cbe3b9173f6">Double</a>(x);
<a name="l00114"></a>00114                 powerTable[2*tableSize] = <a class="code" href="class_abstract_group.html#e54ef772d5f231729e188cbe3b9173f6">Double</a>(y);
<a name="l00115"></a>00115 
<a name="l00116"></a>00116                 <span class="keywordtype">unsigned</span> i, j;
<a name="l00117"></a>00117 
<a name="l00118"></a>00118                 <span class="keywordflow">for</span> (i=3; i&lt;tableSize; i+=2)
<a name="l00119"></a>00119                         powerTable[i] = Add(powerTable[i-2], powerTable[2]);
<a name="l00120"></a>00120                 <span class="keywordflow">for</span> (i=1; i&lt;tableSize; i+=2)
<a name="l00121"></a>00121                         <span class="keywordflow">for</span> (j=i+tableSize; j&lt;(tableSize&lt;&lt;w); j+=tableSize)
<a name="l00122"></a>00122                                 powerTable[j] = Add(powerTable[j-tableSize], y);
<a name="l00123"></a>00123 
<a name="l00124"></a>00124                 <span class="keywordflow">for</span> (i=3*tableSize; i&lt;(tableSize&lt;&lt;w); i+=2*tableSize)
<a name="l00125"></a>00125                         powerTable[i] = Add(powerTable[i-2*tableSize], powerTable[2*tableSize]);
<a name="l00126"></a>00126                 <span class="keywordflow">for</span> (i=tableSize; i&lt;(tableSize&lt;&lt;w); i+=2*tableSize)
<a name="l00127"></a>00127                         <span class="keywordflow">for</span> (j=i+2; j&lt;i+tableSize; j+=2)
<a name="l00128"></a>00128                                 powerTable[j] = Add(powerTable[j-1], x);
<a name="l00129"></a>00129         }
<a name="l00130"></a>00130 
<a name="l00131"></a>00131         <a class="code" href="class_abstract_group.html#4a2b3308fb5c13f70fcc5746be52ba7b">Element</a> result;
<a name="l00132"></a>00132         <span class="keywordtype">unsigned</span> power1 = 0, power2 = 0, prevPosition = expLen-1;
<a name="l00133"></a>00133         <span class="keywordtype">bool</span> firstTime = <span class="keyword">true</span>;
<a name="l00134"></a>00134 
<a name="l00135"></a>00135         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = expLen-1; i&gt;=0; i--)
<a name="l00136"></a>00136         {
<a name="l00137"></a>00137                 power1 = 2*power1 + e1.<a class="code" href="class_integer.html#0e377d23bde55fc7dc6ea2208c587d19" title="return the i-th bit, i=0 being the least significant bit">GetBit</a>(i);
<a name="l00138"></a>00138                 power2 = 2*power2 + e2.<a class="code" href="class_integer.html#0e377d23bde55fc7dc6ea2208c587d19" title="return the i-th bit, i=0 being the least significant bit">GetBit</a>(i);
<a name="l00139"></a>00139 
<a name="l00140"></a>00140                 <span class="keywordflow">if</span> (i==0 || 2*power1 &gt;= tableSize || 2*power2 &gt;= tableSize)
<a name="l00141"></a>00141                 {
<a name="l00142"></a>00142                         <span class="keywordtype">unsigned</span> squaresBefore = prevPosition-i;
<a name="l00143"></a>00143                         <span class="keywordtype">unsigned</span> squaresAfter = 0;
<a name="l00144"></a>00144                         prevPosition = i;
<a name="l00145"></a>00145                         <span class="keywordflow">while</span> ((power1 || power2) &amp;&amp; power1%2 == 0 &amp;&amp; power2%2==0)
<a name="l00146"></a>00146                         {
<a name="l00147"></a>00147                                 power1 /= 2;
<a name="l00148"></a>00148                                 power2 /= 2;
<a name="l00149"></a>00149                                 squaresBefore--;
<a name="l00150"></a>00150                                 squaresAfter++;
<a name="l00151"></a>00151                         }
<a name="l00152"></a>00152                         <span class="keywordflow">if</span> (firstTime)
<a name="l00153"></a>00153                         {
<a name="l00154"></a>00154                                 result = powerTable[(power2&lt;&lt;w) + power1];
<a name="l00155"></a>00155                                 firstTime = <span class="keyword">false</span>;
<a name="l00156"></a>00156                         }
<a name="l00157"></a>00157                         <span class="keywordflow">else</span>
<a name="l00158"></a>00158                         {
<a name="l00159"></a>00159                                 <span class="keywordflow">while</span> (squaresBefore--)
<a name="l00160"></a>00160                                         result = <a class="code" href="class_abstract_group.html#e54ef772d5f231729e188cbe3b9173f6">Double</a>(result);
<a name="l00161"></a>00161                                 <span class="keywordflow">if</span> (power1 || power2)
<a name="l00162"></a>00162                                         <a class="code" href="class_abstract_group.html#45aa7c2240cb2f87184c7ad90df298ec">Accumulate</a>(result, powerTable[(power2&lt;&lt;w) + power1]);
<a name="l00163"></a>00163                         }
<a name="l00164"></a>00164                         <span class="keywordflow">while</span> (squaresAfter--)
<a name="l00165"></a>00165                                 result = <a class="code" href="class_abstract_group.html#e54ef772d5f231729e188cbe3b9173f6">Double</a>(result);
<a name="l00166"></a>00166                         power1 = power2 = 0;
<a name="l00167"></a>00167                 }
<a name="l00168"></a>00168         }
<a name="l00169"></a>00169         <span class="keywordflow">return</span> result;
<a name="l00170"></a>00170 }
<a name="l00171"></a>00171 
<a name="l00172"></a>00172 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Element, <span class="keyword">class</span> Iterator&gt; <a class="code" href="class_abstract_group.html#4a2b3308fb5c13f70fcc5746be52ba7b">Element</a> GeneralCascadeMultiplication(<span class="keyword">const</span> <a class="code" href="class_abstract_group.html" title="Abstract Group.">AbstractGroup&lt;Element&gt;</a> &amp;group, Iterator begin, Iterator end)
<a name="l00173"></a>00173 {
<a name="l00174"></a>00174         <span class="keywordflow">if</span> (end-begin == 1)
<a name="l00175"></a>00175                 <span class="keywordflow">return</span> group.<a class="code" href="class_abstract_group.html#c01536b91c4fa3d0e0f929917143595b">ScalarMultiply</a>(begin-&gt;base, begin-&gt;exponent);
<a name="l00176"></a>00176         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (end-begin == 2)
<a name="l00177"></a>00177                 <span class="keywordflow">return</span> group.<a class="code" href="class_abstract_group.html#ca3e1ca578003aff2595cc8d73522894">CascadeScalarMultiply</a>(begin-&gt;base, begin-&gt;exponent, (begin+1)-&gt;base, (begin+1)-&gt;exponent);
<a name="l00178"></a>00178         <span class="keywordflow">else</span>
<a name="l00179"></a>00179         {
<a name="l00180"></a>00180                 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> q, t;
<a name="l00181"></a>00181                 Iterator last = end;
<a name="l00182"></a>00182                 --last;
<a name="l00183"></a>00183 
<a name="l00184"></a>00184                 std::make_heap(begin, end);
<a name="l00185"></a>00185                 std::pop_heap(begin, end);
<a name="l00186"></a>00186 
<a name="l00187"></a>00187                 <span class="keywordflow">while</span> (!!begin-&gt;exponent)
<a name="l00188"></a>00188                 {
<a name="l00189"></a>00189                         <span class="comment">// last-&gt;exponent is largest exponent, begin-&gt;exponent is next largest</span>
<a name="l00190"></a>00190                         t = last-&gt;exponent;
<a name="l00191"></a>00191                         <a class="code" href="class_integer.html#567c89aa176b354143c99d558d05a5fb" title="calculate r and q such that (a == d*q + r) &amp;&amp; (0 &lt;= r &lt; abs(d))">Integer::Divide</a>(last-&gt;exponent, q, t, begin-&gt;exponent);
<a name="l00192"></a>00192 
<a name="l00193"></a>00193                         <span class="keywordflow">if</span> (q == <a class="code" href="class_integer.html#8c070592581bf6c2f928c72bfa1c1638" title="avoid calling constructors for these frequently used integers">Integer::One</a>())
<a name="l00194"></a>00194                                 group.<a class="code" href="class_abstract_group.html#45aa7c2240cb2f87184c7ad90df298ec">Accumulate</a>(begin-&gt;base, last-&gt;base);      <span class="comment">// avoid overhead of ScalarMultiply()</span>
<a name="l00195"></a>00195                         <span class="keywordflow">else</span>
<a name="l00196"></a>00196                                 group.<a class="code" href="class_abstract_group.html#45aa7c2240cb2f87184c7ad90df298ec">Accumulate</a>(begin-&gt;base, group.<a class="code" href="class_abstract_group.html#c01536b91c4fa3d0e0f929917143595b">ScalarMultiply</a>(last-&gt;base, q));
<a name="l00197"></a>00197 
<a name="l00198"></a>00198                         std::push_heap(begin, end);
<a name="l00199"></a>00199                         std::pop_heap(begin, end);
<a name="l00200"></a>00200                 }
<a name="l00201"></a>00201 
<a name="l00202"></a>00202                 <span class="keywordflow">return</span> group.<a class="code" href="class_abstract_group.html#c01536b91c4fa3d0e0f929917143595b">ScalarMultiply</a>(last-&gt;base, last-&gt;exponent);
<a name="l00203"></a>00203         }
<a name="l00204"></a>00204 }
<a name="l00205"></a>00205 
<a name="l00206"></a><a class="code" href="struct_window_slider.html">00206</a> <span class="keyword">struct </span><a class="code" href="struct_window_slider.html">WindowSlider</a>
<a name="l00207"></a>00207 {
<a name="l00208"></a><a class="code" href="struct_window_slider.html#f8e745674d82cb6aefbbd16c181f9f86">00208</a>         <a class="code" href="struct_window_slider.html">WindowSlider</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &amp;expIn, <span class="keywordtype">bool</span> fastNegate, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> windowSizeIn=0)
<a name="l00209"></a>00209                 : exp(expIn), windowModulus(<a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a>::One()), windowSize(windowSizeIn), windowBegin(0), fastNegate(fastNegate), firstTime(true), finished(false)
<a name="l00210"></a>00210         {
<a name="l00211"></a>00211                 <span class="keywordflow">if</span> (windowSize == 0)
<a name="l00212"></a>00212                 {
<a name="l00213"></a>00213                         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expLen = exp.BitCount();
<a name="l00214"></a>00214                         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)))));
<a name="l00215"></a>00215                 }
<a name="l00216"></a>00216                 windowModulus &lt;&lt;= windowSize;
<a name="l00217"></a>00217         }
<a name="l00218"></a>00218 
<a name="l00219"></a><a class="code" href="struct_window_slider.html#b5eb09cfae787154eb834b5834cd01dd">00219</a>         <span class="keywordtype">void</span> FindNextWindow()
<a name="l00220"></a>00220         {
<a name="l00221"></a>00221                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expLen = exp.WordCount() * WORD_BITS;
<a name="l00222"></a>00222                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> skipCount = firstTime ? 0 : windowSize;
<a name="l00223"></a>00223                 firstTime = <span class="keyword">false</span>;
<a name="l00224"></a>00224                 <span class="keywordflow">while</span> (!exp.GetBit(skipCount))
<a name="l00225"></a>00225                 {