nbtheory_8cpp-source.html

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

<a name="l00108"></a>00108                 <span class="keywordflow">return</span> n==2 || n==3;
<a name="l00109"></a>00109 
<a name="l00110"></a>00110         assert(n&gt;3 &amp;&amp; b&gt;1 &amp;&amp; b&lt;n-1);
<a name="l00111"></a>00111 
<a name="l00112"></a>00112         <span class="keywordflow">if</span> ((n.<a class="code" href="class_integer.html#fedf9af097a3417d8bd3742ec53f9593">IsEven</a>() &amp;&amp; n!=2) || GCD(b, n) != 1)
<a name="l00113"></a>00113                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00114"></a>00114 
<a name="l00115"></a>00115         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> nminus1 = (n-1);
<a name="l00116"></a>00116         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> a;
<a name="l00117"></a>00117 
<a name="l00118"></a>00118         <span class="comment">// calculate a = largest power of 2 that divides (n-1)</span>
<a name="l00119"></a>00119         <span class="keywordflow">for</span> (a=0; ; a++)
<a name="l00120"></a>00120                 <span class="keywordflow">if</span> (nminus1.<a class="code" href="class_integer.html#0e377d23bde55fc7dc6ea2208c587d19" title="return the i-th bit, i=0 being the least significant bit">GetBit</a>(a))
<a name="l00121"></a>00121                         <span class="keywordflow">break</span>;
<a name="l00122"></a>00122         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> m = nminus1&gt;&gt;a;
<a name="l00123"></a>00123 
<a name="l00124"></a>00124         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> z = a_exp_b_mod_c(b, m, n);
<a name="l00125"></a>00125         <span class="keywordflow">if</span> (z==1 || z==nminus1)
<a name="l00126"></a>00126                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00127"></a>00127         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> j=1; j&lt;a; j++)
<a name="l00128"></a>00128         {
<a name="l00129"></a>00129                 z = z.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()%n;
<a name="l00130"></a>00130                 <span class="keywordflow">if</span> (z==nminus1)
<a name="l00131"></a>00131                         <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00132"></a>00132                 <span class="keywordflow">if</span> (z==1)
<a name="l00133"></a>00133                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00134"></a>00134         }
<a name="l00135"></a>00135         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00136"></a>00136 }
<a name="l00137"></a>00137 
<a name="l00138"></a>00138 <span class="keywordtype">bool</span> RabinMillerTest(<a class="code" href="class_random_number_generator.html" title="interface for random number generators">RandomNumberGenerator</a> &amp;rng, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &amp;n, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> rounds)
<a name="l00139"></a>00139 {
<a name="l00140"></a>00140         <span class="keywordflow">if</span> (n &lt;= 3)
<a name="l00141"></a>00141                 <span class="keywordflow">return</span> n==2 || n==3;
<a name="l00142"></a>00142 
<a name="l00143"></a>00143         assert(n&gt;3);
<a name="l00144"></a>00144 
<a name="l00145"></a>00145         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> b;
<a name="l00146"></a>00146         <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i&lt;rounds; i++)
<a name="l00147"></a>00147         {
<a name="l00148"></a>00148                 b.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, 2, n-2);
<a name="l00149"></a>00149                 <span class="keywordflow">if</span> (!IsStrongProbablePrime(n, b))
<a name="l00150"></a>00150                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00151"></a>00151         }
<a name="l00152"></a>00152         <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00153"></a>00153 }
<a name="l00154"></a>00154 
<a name="l00155"></a>00155 <span class="keywordtype">bool</span> IsLucasProbablePrime(<span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &amp;n)
<a name="l00156"></a>00156 {
<a name="l00157"></a>00157         <span class="keywordflow">if</span> (n &lt;= 1)
<a name="l00158"></a>00158                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00159"></a>00159 
<a name="l00160"></a>00160         <span class="keywordflow">if</span> (n.<a class="code" href="class_integer.html#fedf9af097a3417d8bd3742ec53f9593">IsEven</a>())
<a name="l00161"></a>00161                 <span class="keywordflow">return</span> n==2;
<a name="l00162"></a>00162 
<a name="l00163"></a>00163         assert(n&gt;2);
<a name="l00164"></a>00164 
<a name="l00165"></a>00165         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> b=3;
<a name="l00166"></a>00166         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0;
<a name="l00167"></a>00167         <span class="keywordtype">int</span> j;
<a name="l00168"></a>00168 
<a name="l00169"></a>00169         <span class="keywordflow">while</span> ((j=Jacobi(b.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()-4, n)) == 1)
<a name="l00170"></a>00170         {
<a name="l00171"></a>00171                 <span class="keywordflow">if</span> (++i==64 &amp;&amp; n.<a class="code" href="class_integer.html#3acfdfd7aa905d2600073449c31eb3c4" title="return whether this integer is a perfect square">IsSquare</a>())    <span class="comment">// avoid infinite loop if n is a square</span>
<a name="l00172"></a>00172                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00173"></a>00173                 ++b; ++b;
<a name="l00174"></a>00174         }
<a name="l00175"></a>00175 
<a name="l00176"></a>00176         <span class="keywordflow">if</span> (j==0) 
<a name="l00177"></a>00177                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00178"></a>00178         <span class="keywordflow">else</span>
<a name="l00179"></a>00179                 <span class="keywordflow">return</span> Lucas(n+1, b, n)==2;
<a name="l00180"></a>00180 }
<a name="l00181"></a>00181 
<a name="l00182"></a>00182 <span class="keywordtype">bool</span> IsStrongLucasProbablePrime(<span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &amp;n)
<a name="l00183"></a>00183 {
<a name="l00184"></a>00184         <span class="keywordflow">if</span> (n &lt;= 1)
<a name="l00185"></a>00185                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00186"></a>00186 
<a name="l00187"></a>00187         <span class="keywordflow">if</span> (n.<a class="code" href="class_integer.html#fedf9af097a3417d8bd3742ec53f9593">IsEven</a>())
<a name="l00188"></a>00188                 <span class="keywordflow">return</span> n==2;
<a name="l00189"></a>00189 
<a name="l00190"></a>00190         assert(n&gt;2);
<a name="l00191"></a>00191 
<a name="l00192"></a>00192         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> b=3;
<a name="l00193"></a>00193         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0;
<a name="l00194"></a>00194         <span class="keywordtype">int</span> j;
<a name="l00195"></a>00195 
<a name="l00196"></a>00196         <span class="keywordflow">while</span> ((j=Jacobi(b.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()-4, n)) == 1)
<a name="l00197"></a>00197         {
<a name="l00198"></a>00198                 <span class="keywordflow">if</span> (++i==64 &amp;&amp; n.<a class="code" href="class_integer.html#3acfdfd7aa905d2600073449c31eb3c4" title="return whether this integer is a perfect square">IsSquare</a>())    <span class="comment">// avoid infinite loop if n is a square</span>
<a name="l00199"></a>00199                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00200"></a>00200                 ++b; ++b;
<a name="l00201"></a>00201         }
<a name="l00202"></a>00202 
<a name="l00203"></a>00203         <span class="keywordflow">if</span> (j==0) 
<a name="l00204"></a>00204                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00205"></a>00205 
<a name="l00206"></a>00206         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> n1 = n+1;
<a name="l00207"></a>00207         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> a;
<a name="l00208"></a>00208 
<a name="l00209"></a>00209         <span class="comment">// calculate a = largest power of 2 that divides n1</span>
<a name="l00210"></a>00210         <span class="keywordflow">for</span> (a=0; ; a++)
<a name="l00211"></a>00211                 <span class="keywordflow">if</span> (n1.<a class="code" href="class_integer.html#0e377d23bde55fc7dc6ea2208c587d19" title="return the i-th bit, i=0 being the least significant bit">GetBit</a>(a))
<a name="l00212"></a>00212                         <span class="keywordflow">break</span>;
<a name="l00213"></a>00213         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> m = n1&gt;&gt;a;
<a name="l00214"></a>00214 
<a name="l00215"></a>00215         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> z = Lucas(m, b, n);
<a name="l00216"></a>00216         <span class="keywordflow">if</span> (z==2 || z==n-2)
<a name="l00217"></a>00217                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00218"></a>00218         <span class="keywordflow">for</span> (i=1; i&lt;a; i++)
<a name="l00219"></a>00219         {
<a name="l00220"></a>00220                 z = (z.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()-2)%n;
<a name="l00221"></a>00221                 <span class="keywordflow">if</span> (z==n-2)
<a name="l00222"></a>00222                         <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00223"></a>00223                 <span class="keywordflow">if</span> (z==2)
<a name="l00224"></a>00224                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00225"></a>00225         }
<a name="l00226"></a>00226         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00227"></a>00227 }
<a name="l00228"></a>00228 
<a name="l00229"></a><a class="code" href="struct_new_last_small_prime_squared.html">00229</a> <span class="keyword">struct </span><a class="code" href="struct_new_last_small_prime_squared.html">NewLastSmallPrimeSquared</a>
<a name="l00230"></a>00230 {
<a name="l00231"></a><a class="code" href="struct_new_last_small_prime_squared.html#87ef0701e5103ae502fb30e31b9444e2">00231</a>         <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> * <a class="code" href="struct_new_last_small_prime_squared.html#87ef0701e5103ae502fb30e31b9444e2">operator()</a>()<span class="keyword"> const</span>
<a name="l00232"></a>00232 <span class="keyword">        </span>{
<a name="l00233"></a>00233                 <span class="keywordflow">return</span> <span class="keyword">new</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a>(<a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a>(s_lastSmallPrime).Squared());
<a name="l00234"></a>00234         }
<a name="l00235"></a>00235 };