nbtheory_8cpp-source.html

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

<a name="l00236"></a>00236 
<a name="l00237"></a>00237 <span class="keywordtype">bool</span> IsPrime(<span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &amp;p)
<a name="l00238"></a>00238 {
<a name="l00239"></a>00239         <span class="keywordflow">if</span> (p &lt;= s_lastSmallPrime)
<a name="l00240"></a>00240                 <span class="keywordflow">return</span> IsSmallPrime(p);
<a name="l00241"></a>00241         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (p &lt;= <a class="code" href="class_singleton.html">Singleton&lt;Integer, NewLastSmallPrimeSquared&gt;</a>().Ref())
<a name="l00242"></a>00242                 <span class="keywordflow">return</span> SmallDivisorsTest(p);
<a name="l00243"></a>00243         <span class="keywordflow">else</span>
<a name="l00244"></a>00244                 <span class="keywordflow">return</span> SmallDivisorsTest(p) &amp;&amp; IsStrongProbablePrime(p, 3) &amp;&amp; IsStrongLucasProbablePrime(p);
<a name="l00245"></a>00245 }
<a name="l00246"></a>00246 
<a name="l00247"></a>00247 <span class="keywordtype">bool</span> VerifyPrime(<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;p, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> level)
<a name="l00248"></a>00248 {
<a name="l00249"></a>00249         <span class="keywordtype">bool</span> pass = IsPrime(p) &amp;&amp; RabinMillerTest(rng, p, 1);
<a name="l00250"></a>00250         <span class="keywordflow">if</span> (level &gt;= 1)
<a name="l00251"></a>00251                 pass = pass &amp;&amp; RabinMillerTest(rng, p, 10);
<a name="l00252"></a>00252         <span class="keywordflow">return</span> pass;
<a name="l00253"></a>00253 }
<a name="l00254"></a>00254 
<a name="l00255"></a>00255 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> PrimeSearchInterval(<span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &amp;max)
<a name="l00256"></a>00256 {
<a name="l00257"></a>00257         <span class="keywordflow">return</span> max.<a class="code" href="class_integer.html#867356d88074424328d0ebb9bea63254" title="number of significant bits = floor(log2(abs(*this))) + 1">BitCount</a>();
<a name="l00258"></a>00258 }
<a name="l00259"></a>00259 
<a name="l00260"></a>00260 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> FastProbablePrimeTest(<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="l00261"></a>00261 {
<a name="l00262"></a>00262         <span class="keywordflow">return</span> IsStrongProbablePrime(n,2);
<a name="l00263"></a>00263 }
<a name="l00264"></a>00264 
<a name="l00265"></a>00265 <a class="code" href="class_algorithm_parameters.html">AlgorithmParameters&lt;AlgorithmParameters&lt;AlgorithmParameters&lt;NullNameValuePairs, Integer::RandomNumberType&gt;</a>, <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a>&gt;, Integer&gt;
<a name="l00266"></a>00266         MakeParametersForTwoPrimesOfEqualSize(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> productBitLength)
<a name="l00267"></a>00267 {
<a name="l00268"></a>00268         <span class="keywordflow">if</span> (productBitLength &lt; 16)
<a name="l00269"></a>00269                 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html" title="exception thrown when an invalid argument is detected">InvalidArgument</a>(<span class="stringliteral">"invalid bit length"</span>);
<a name="l00270"></a>00270 
<a name="l00271"></a>00271         Integer minP, maxP;
<a name="l00272"></a>00272 
<a name="l00273"></a>00273         <span class="keywordflow">if</span> (productBitLength%2==0)
<a name="l00274"></a>00274         {
<a name="l00275"></a>00275                 minP = Integer(182) &lt;&lt; (productBitLength/2-8);
<a name="l00276"></a>00276                 maxP = <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(productBitLength/2)-1;
<a name="l00277"></a>00277         }
<a name="l00278"></a>00278         <span class="keywordflow">else</span>
<a name="l00279"></a>00279         {
<a name="l00280"></a>00280                 minP = <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>((productBitLength-1)/2);
<a name="l00281"></a>00281                 maxP = Integer(181) &lt;&lt; ((productBitLength+1)/2-8);
<a name="l00282"></a>00282         }
<a name="l00283"></a>00283 
<a name="l00284"></a>00284         <span class="keywordflow">return</span> MakeParameters(<span class="stringliteral">"RandomNumberType"</span>, <a class="code" href="class_integer.html#9b4088ac01abf76b9ba60060abccb7a3fe686f55e5b6768b20009a12522bd0d9">Integer::PRIME</a>)(<span class="stringliteral">"Min"</span>, minP)(<span class="stringliteral">"Max"</span>, maxP);
<a name="l00285"></a>00285 }
<a name="l00286"></a>00286 
<a name="l00287"></a><a class="code" href="class_prime_sieve.html">00287</a> <span class="keyword">class </span><a class="code" href="class_prime_sieve.html">PrimeSieve</a>
<a name="l00288"></a>00288 {
<a name="l00289"></a>00289 <span class="keyword">public</span>:
<a name="l00290"></a>00290         <span class="comment">// delta == 1 or -1 means double sieve with p = 2*q + delta</span>
<a name="l00291"></a>00291         <a class="code" href="class_prime_sieve.html#d666abdbdc1847849a034fca32e525b8">PrimeSieve</a>(<span class="keyword">const</span> Integer &amp;first, <span class="keyword">const</span> Integer &amp;last, <span class="keyword">const</span> Integer &amp;step, <span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta=0);
<a name="l00292"></a>00292         <span class="keywordtype">bool</span> <a class="code" href="class_prime_sieve.html#55376fe7f9294c1bf561350fa4a93013">NextCandidate</a>(Integer &amp;c);
<a name="l00293"></a>00293 
<a name="l00294"></a>00294         <span class="keywordtype">void</span> <a class="code" href="class_prime_sieve.html#efd53894e116b4719697f4a5347f0854">DoSieve</a>();
<a name="l00295"></a>00295         <span class="keyword">static</span> <span class="keywordtype">void</span> <a class="code" href="class_prime_sieve.html#ef7632203a02890568748c22506d6247">SieveSingle</a>(std::vector&lt;bool&gt; &amp;sieve, word16 p, <span class="keyword">const</span> Integer &amp;first, <span class="keyword">const</span> Integer &amp;step, word16 stepInv);
<a name="l00296"></a>00296 
<a name="l00297"></a><a class="code" href="class_prime_sieve.html#e4a118cd164def0137049b041a40df5a">00297</a>         Integer <a class="code" href="class_prime_sieve.html#505052e929448429944305dbbf8e3d9b">m_first</a>, <a class="code" href="class_prime_sieve.html#2166a7be20ae19477aec3a785053e758">m_last</a>, <a class="code" href="class_prime_sieve.html#e4a118cd164def0137049b041a40df5a">m_step</a>;
<a name="l00298"></a><a class="code" href="class_prime_sieve.html#b088fe1cbe49ca396ffee53f94da0706">00298</a>         <span class="keywordtype">signed</span> <span class="keywordtype">int</span> <a class="code" href="class_prime_sieve.html#b088fe1cbe49ca396ffee53f94da0706">m_delta</a>;
<a name="l00299"></a><a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">00299</a>         word <a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">m_next</a>;
<a name="l00300"></a><a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">00300</a>         std::vector&lt;bool&gt; <a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>;
<a name="l00301"></a>00301 };
<a name="l00302"></a>00302 
<a name="l00303"></a><a class="code" href="class_prime_sieve.html#d666abdbdc1847849a034fca32e525b8">00303</a> <a class="code" href="class_prime_sieve.html#d666abdbdc1847849a034fca32e525b8">PrimeSieve::PrimeSieve</a>(<span class="keyword">const</span> Integer &amp;first, <span class="keyword">const</span> Integer &amp;last, <span class="keyword">const</span> Integer &amp;step, <span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta)
<a name="l00304"></a>00304         : m_first(first), m_last(last), m_step(step), m_delta(delta), m_next(0)
<a name="l00305"></a>00305 {
<a name="l00306"></a>00306         <a class="code" href="class_prime_sieve.html#efd53894e116b4719697f4a5347f0854">DoSieve</a>();
<a name="l00307"></a>00307 }
<a name="l00308"></a>00308 
<a name="l00309"></a><a class="code" href="class_prime_sieve.html#55376fe7f9294c1bf561350fa4a93013">00309</a> <span class="keywordtype">bool</span> <a class="code" href="class_prime_sieve.html#55376fe7f9294c1bf561350fa4a93013">PrimeSieve::NextCandidate</a>(Integer &amp;c)
<a name="l00310"></a>00310 {
<a name="l00311"></a>00311         <span class="keywordtype">bool</span> safe = SafeConvert(std::find(<a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>.begin()+<a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">m_next</a>, <a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>.end(), <span class="keyword">false</span>) - <a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>.begin(), <a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">m_next</a>);
<a name="l00312"></a>00312         assert(safe);
<a name="l00313"></a>00313         <span class="keywordflow">if</span> (<a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">m_next</a> == <a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>.size())
<a name="l00314"></a>00314         {
<a name="l00315"></a>00315                 <a class="code" href="class_prime_sieve.html#505052e929448429944305dbbf8e3d9b">m_first</a> += <span class="keywordtype">long</span>(<a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>.size())*<a class="code" href="class_prime_sieve.html#e4a118cd164def0137049b041a40df5a">m_step</a>;
<a name="l00316"></a>00316                 <span class="keywordflow">if</span> (<a class="code" href="class_prime_sieve.html#505052e929448429944305dbbf8e3d9b">m_first</a> &gt; <a class="code" href="class_prime_sieve.html#2166a7be20ae19477aec3a785053e758">m_last</a>)
<a name="l00317"></a>00317                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00318"></a>00318                 <span class="keywordflow">else</span>
<a name="l00319"></a>00319                 {
<a name="l00320"></a>00320                         <a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">m_next</a> = 0;
<a name="l00321"></a>00321                         <a class="code" href="class_prime_sieve.html#efd53894e116b4719697f4a5347f0854">DoSieve</a>();
<a name="l00322"></a>00322                         <span class="keywordflow">return</span> <a class="code" href="class_prime_sieve.html#55376fe7f9294c1bf561350fa4a93013">NextCandidate</a>(c);
<a name="l00323"></a>00323                 }
<a name="l00324"></a>00324         }
<a name="l00325"></a>00325         <span class="keywordflow">else</span>
<a name="l00326"></a>00326         {
<a name="l00327"></a>00327                 c = <a class="code" href="class_prime_sieve.html#505052e929448429944305dbbf8e3d9b">m_first</a> + long(<a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">m_next</a>)*<a class="code" href="class_prime_sieve.html#e4a118cd164def0137049b041a40df5a">m_step</a>;
<a name="l00328"></a>00328                 ++<a class="code" href="class_prime_sieve.html#7fd1a09885673caf9979e3247b7e71f4">m_next</a>;
<a name="l00329"></a>00329                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00330"></a>00330         }
<a name="l00331"></a>00331 }
<a name="l00332"></a>00332 
<a name="l00333"></a><a class="code" href="class_prime_sieve.html#ef7632203a02890568748c22506d6247">00333</a> <span class="keywordtype">void</span> <a class="code" href="class_prime_sieve.html#ef7632203a02890568748c22506d6247">PrimeSieve::SieveSingle</a>(std::vector&lt;bool&gt; &amp;sieve, word16 p, <span class="keyword">const</span> Integer &amp;first, <span class="keyword">const</span> Integer &amp;step, word16 stepInv)
<a name="l00334"></a>00334 {
<a name="l00335"></a>00335         <span class="keywordflow">if</span> (stepInv)
<a name="l00336"></a>00336         {
<a name="l00337"></a>00337                 <span class="keywordtype">size_t</span> sieveSize = sieve.size();
<a name="l00338"></a>00338                 <span class="keywordtype">size_t</span> j = (word32(p-(first%p))*stepInv) % p;
<a name="l00339"></a>00339                 <span class="comment">// if the first multiple of p is p, skip it</span>
<a name="l00340"></a>00340                 <span class="keywordflow">if</span> (first.<a class="code" href="class_integer.html#8c04a3308dd546cac819835922ee8db6" title="number of significant words = ceiling(ByteCount()/sizeof(word))">WordCount</a>() &lt;= 1 &amp;&amp; first + step*long(j) == p)
<a name="l00341"></a>00341                         j += p;
<a name="l00342"></a>00342                 <span class="keywordflow">for</span> (; j &lt; sieveSize; j += p)
<a name="l00343"></a>00343                         sieve[j] = <span class="keyword">true</span>;
<a name="l00344"></a>00344         }
<a name="l00345"></a>00345 }
<a name="l00346"></a>00346 
<a name="l00347"></a><a class="code" href="class_prime_sieve.html#efd53894e116b4719697f4a5347f0854">00347</a> <span class="keywordtype">void</span> <a class="code" href="class_prime_sieve.html#efd53894e116b4719697f4a5347f0854">PrimeSieve::DoSieve</a>()
<a name="l00348"></a>00348 {
<a name="l00349"></a>00349         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> primeTableSize;
<a name="l00350"></a>00350         <span class="keyword">const</span> word16 * primeTable = GetPrimeTable(primeTableSize);
<a name="l00351"></a>00351 
<a name="l00352"></a>00352         <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> maxSieveSize = 32768;
<a name="l00353"></a>00353         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sieveSize = STDMIN(Integer(maxSieveSize), (<a class="code" href="class_prime_sieve.html#2166a7be20ae19477aec3a785053e758">m_last</a>-<a class="code" href="class_prime_sieve.html#505052e929448429944305dbbf8e3d9b">m_first</a>)/<a class="code" href="class_prime_sieve.html#e4a118cd164def0137049b041a40df5a">m_step</a>+1).ConvertToLong();
<a name="l00354"></a>00354 
<a name="l00355"></a>00355         <a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>.clear();
<a name="l00356"></a>00356         <a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>.resize(sieveSize, <span class="keyword">false</span>);
<a name="l00357"></a>00357 
<a name="l00358"></a>00358         <span class="keywordflow">if</span> (<a class="code" href="class_prime_sieve.html#b088fe1cbe49ca396ffee53f94da0706">m_delta</a> == 0)
<a name="l00359"></a>00359         {
<a name="l00360"></a>00360                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = 0; i &lt; primeTableSize; ++i)
<a name="l00361"></a>00361                         <a class="code" href="class_prime_sieve.html#ef7632203a02890568748c22506d6247">SieveSingle</a>(<a class="code" href="class_prime_sieve.html#43d578612bed4a6c9ef353987c0407f8">m_sieve</a>, primeTable[i], <a class="code" href="class_prime_sieve.html#505052e929448429944305dbbf8e3d9b">m_first</a>, <a class="code" href="class_prime_sieve.html#e4a118cd164def0137049b041a40df5a">m_step</a>, (word16)<a class="code" href="class_prime_sieve.html#e4a118cd164def0137049b041a40df5a">m_step</a>.<a class="code" href="class_integer.html#881f9c714ee42f35718725a43d4d7db3" title="calculate multiplicative inverse of *this mod n">InverseMod</a>(primeTable[i]));
<a name="l00362"></a>00362         }
<a name="l00363"></a>00363         <span class="keywordflow">else</span>