nbtheory_8cpp-source.html

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

00195                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
00196         }
00197         <span class="keywordflow">return</span> <span class="keyword">true</span>;
00198 }
00199 
00200 <span class="keywordtype">bool</span> IsLucasProbablePrime(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;n)
00201 {
00202         <span class="keywordflow">if</span> (n &lt;= 1)
00203                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00204 
00205         <span class="keywordflow">if</span> (n.<a class="code" href="class_integer.html#_integerz41_14">IsEven</a>())
00206                 <span class="keywordflow">return</span> n==2;
00207 
00208         assert(n&gt;2);
00209 
00210         <a class="code" href="class_integer.html">Integer</a> b=3;
00211         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0;
00212         <span class="keywordtype">int</span> j;
00213 
00214         <span class="keywordflow">while</span> ((j=Jacobi(b.Squared()-4, n)) == 1)
00215         {
00216                 <span class="keywordflow">if</span> (++i==64 &amp;&amp; n.<a class="code" href="class_integer.html#_integerz49_4">IsSquare</a>())    <span class="comment">// avoid infinite loop if n is a square</span>
00217                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
00218                 ++b; ++b;
00219         }
00220 
00221         <span class="keywordflow">if</span> (j==0) 
00222                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00223         <span class="keywordflow">else</span>
00224                 <span class="keywordflow">return</span> Lucas(n+1, b, n)==2;
00225 }
00226 
00227 <span class="keywordtype">bool</span> IsStrongLucasProbablePrime(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;n)
00228 {
00229         <span class="keywordflow">if</span> (n &lt;= 1)
00230                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00231 
00232         <span class="keywordflow">if</span> (n.<a class="code" href="class_integer.html#_integerz41_14">IsEven</a>())
00233                 <span class="keywordflow">return</span> n==2;
00234 
00235         assert(n&gt;2);
00236 
00237         <a class="code" href="class_integer.html">Integer</a> b=3;
00238         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0;
00239         <span class="keywordtype">int</span> j;
00240 
00241         <span class="keywordflow">while</span> ((j=Jacobi(b.Squared()-4, n)) == 1)
00242         {
00243                 <span class="keywordflow">if</span> (++i==64 &amp;&amp; n.<a class="code" href="class_integer.html#_integerz49_4">IsSquare</a>())    <span class="comment">// avoid infinite loop if n is a square</span>
00244                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
00245                 ++b; ++b;
00246         }
00247 
00248         <span class="keywordflow">if</span> (j==0) 
00249                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00250 
00251         <a class="code" href="class_integer.html">Integer</a> n1 = n+1;
00252         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> a;
00253 
00254         <span class="comment">// calculate a = largest power of 2 that divides n1</span>
00255         <span class="keywordflow">for</span> (a=0; ; a++)
00256                 <span class="keywordflow">if</span> (n1.<a class="code" href="class_integer.html#_integerz41_5">GetBit</a>(a))
00257                         <span class="keywordflow">break</span>;
00258         <a class="code" href="class_integer.html">Integer</a> m = n1&gt;&gt;a;
00259 
00260         <a class="code" href="class_integer.html">Integer</a> z = Lucas(m, b, n);
00261         <span class="keywordflow">if</span> (z==2 || z==n-2)
00262                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
00263         <span class="keywordflow">for</span> (i=1; i&lt;a; i++)
00264         {
00265                 z = (z.Squared()-2)%n;
00266                 <span class="keywordflow">if</span> (z==n-2)
00267                         <span class="keywordflow">return</span> <span class="keyword">true</span>;
00268                 <span class="keywordflow">if</span> (z==2)
00269                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
00270         }
00271         <span class="keywordflow">return</span> <span class="keyword">false</span>;
00272 }
00273 
00274 <span class="keywordtype">bool</span> IsPrime(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;p)
00275 {
00276         <span class="keyword">static</span> <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> lastSmallPrimeSquared = <a class="code" href="class_integer.html">Integer</a>(lastSmallPrime).Squared();
00277 
00278         <span class="keywordflow">if</span> (p &lt;= lastSmallPrime)
00279                 <span class="keywordflow">return</span> IsSmallPrime(p);
00280         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (p &lt;= lastSmallPrimeSquared)
00281                 <span class="keywordflow">return</span> SmallDivisorsTest(p);
00282         <span class="keywordflow">else</span>
00283                 <span class="keywordflow">return</span> SmallDivisorsTest(p) &amp;&amp; IsStrongProbablePrime(p, 3) &amp;&amp; IsStrongLucasProbablePrime(p);
00284 }
00285 
00286 <span class="keywordtype">bool</span> VerifyPrime(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &amp;rng, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;p, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> level)
00287 {
00288         <span class="keywordtype">bool</span> pass = IsPrime(p) &amp;&amp; RabinMillerTest(rng, p, 1);
00289         <span class="keywordflow">if</span> (level &gt;= 1)
00290                 pass = pass &amp;&amp; RabinMillerTest(rng, p, 10);
00291         <span class="keywordflow">return</span> pass;
00292 }
00293 
00294 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> PrimeSearchInterval(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;max)
00295 {
00296         <span class="keywordflow">return</span> max.<a class="code" href="class_integer.html#_integerz41_2">BitCount</a>();
00297 }
00298 
00299 <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">Integer</a> &amp;n)
00300 {
00301         <span class="keywordflow">return</span> IsStrongProbablePrime(n,2);
00302 }
00303 
00304 AlgorithmParameters&lt;AlgorithmParameters&lt;AlgorithmParameters&lt;NullNameValuePairs, Integer::RandomNumberType&gt;, <a class="code" href="class_integer.html">Integer</a>&gt;, Integer&gt;
00305         MakeParametersForTwoPrimesOfEqualSize(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> productBitLength)
00306 {
00307         <span class="keywordflow">if</span> (productBitLength &lt; 16)
00308                 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"invalid bit length"</span>);
00309 
00310         Integer minP, maxP;
00311 
00312         <span class="keywordflow">if</span> (productBitLength%2==0)
00313         {
00314                 minP = Integer(182) &lt;&lt; (productBitLength/2-8);
00315                 maxP = <a class="code" href="class_integer.html#_integerz37_13">Integer::Power2</a>(productBitLength/2)-1;
00316         }
00317         <span class="keywordflow">else</span>
00318         {
00319                 minP = <a class="code" href="class_integer.html#_integerz37_13">Integer::Power2</a>((productBitLength-1)/2);
00320                 maxP = Integer(181) &lt;&lt; ((productBitLength+1)/2-8);
00321         }
00322 
00323         <span class="keywordflow">return</span> MakeParameters(<span class="stringliteral">"RandomNumberType"</span>, Integer::PRIME)(<span class="stringliteral">"Min"</span>, minP)(<span class="stringliteral">"Max"</span>, maxP);
00324 }
00325 
00326 <span class="keyword">class </span>PrimeSieve
00327 {
00328 <span class="keyword">public</span>:
00329         <span class="comment">// delta == 1 or -1 means double sieve with p = 2*q + delta</span>
00330         PrimeSieve(<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);
00331         <span class="keywordtype">bool</span> NextCandidate(Integer &amp;c);
00332 
00333         <span class="keywordtype">void</span> DoSieve();
00334         <span class="keyword">static</span> <span class="keywordtype">void</span> SieveSingle(std::vector&lt;bool&gt; &amp;sieve, word p, <span class="keyword">const</span> Integer &amp;first, <span class="keyword">const</span> Integer &amp;step, word stepInv);
00335 
00336         Integer m_first, m_last, m_step;
00337         <span class="keywordtype">signed</span> <span class="keywordtype">int</span> m_delta;
00338         word m_next;
00339         std::vector&lt;bool&gt; m_sieve;
00340 };
00341 
00342 PrimeSieve::PrimeSieve(<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)
00343         : m_first(first), m_last(last), m_step(step), m_delta(delta), m_next(0)
00344 {
00345         DoSieve();
00346 }
00347 
00348 <span class="keywordtype">bool</span> PrimeSieve::NextCandidate(Integer &amp;c)
00349 {
00350         m_next = std::find(m_sieve.begin()+m_next, m_sieve.end(), <span class="keyword">false</span>) - m_sieve.begin();
00351         <span class="keywordflow">if</span> (m_next == m_sieve.size())
00352         {
00353                 m_first += m_sieve.size()*m_step;
00354                 <span class="keywordflow">if</span> (m_first &gt; m_last)
00355                         <span class="keywordflow">return</span> <span class="keyword">false</span>;
00356                 <span class="keywordflow">else</span>
00357                 {
00358                         m_next = 0;
00359                         DoSieve();
00360                         <span class="keywordflow">return</span> NextCandidate(c);
00361                 }
00362         }
00363         <span class="keywordflow">else</span>
00364         {
00365                 c = m_first + m_next*m_step;
00366                 ++m_next;
00367                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
00368         }
00369 }
00370 
00371 <span class="keywordtype">void</span> PrimeSieve::SieveSingle(std::vector&lt;bool&gt; &amp;sieve, word p, <span class="keyword">const</span> Integer &amp;first, <span class="keyword">const</span> Integer &amp;step, word stepInv)
00372 {
00373         <span class="keywordflow">if</span> (stepInv)
00374         {
00375                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sieveSize = sieve.size();
00376                 word j = word((dword(p-(first%p))*stepInv) % p);
00377                 <span class="comment">// if the first multiple of p is p, skip it</span>
00378                 <span class="keywordflow">if</span> (first.<a class="code" href="class_integer.html#_integerz41_4">WordCount</a>() &lt;= 1 &amp;&amp; first + step*j == p)
00379                         j += p;
00380                 <span class="keywordflow">for</span> (; j &lt; sieveSize; j += p)
00381                         sieve[j] = <span class="keyword">true</span>;
00382         }
00383 }
00384 
00385 <span class="keywordtype">void</span> PrimeSieve::DoSieve()
00386 {
00387         BuildPrimeTable();
00388 
00389         <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> maxSieveSize = 32768;
00390         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sieveSize = STDMIN(Integer(maxSieveSize), (m_last-m_first)/m_step+1).ConvertToLong();
00391 
00392         m_sieve.clear();
00393         m_sieve.resize(sieveSize, <span class="keyword">false</span>);
00394 
00395         <span class="keywordflow">if</span> (m_delta == 0)