nbtheory_8cpp-source.html

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

<a name="l00492"></a>00492                 <span class="comment">// with q the recursively generated prime above. We will be able</span>
<a name="l00493"></a>00493                 <span class="comment">// to use Lucas tets for proving primality. A trick of Quisquater</span>
<a name="l00494"></a>00494                 <span class="comment">// allows taking q &gt; cubic_root(p) rather then square_root: this</span>
<a name="l00495"></a>00495                 <span class="comment">// decreases the recursion.</span>
<a name="l00496"></a>00496 
<a name="l00497"></a>00497                 p.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, minP, maxP, <a class="code" href="class_integer.html#9b4088ac01abf76b9ba60060abccb7a3d9b396a7ba736a4ca02db0125cc8c6a4">Integer::ANY</a>, 1, q2);
<a name="l00498"></a>00498                 <a class="code" href="class_prime_sieve.html">PrimeSieve</a> sieve(p, STDMIN(p+PrimeSearchInterval(maxP)*q2, maxP), q2);
<a name="l00499"></a>00499 
<a name="l00500"></a>00500                 <span class="keywordflow">while</span> (sieve.NextCandidate(p))
<a name="l00501"></a>00501                 {
<a name="l00502"></a>00502                         <span class="keywordflow">if</span> (FastProbablePrimeTest(p) &amp;&amp; ProvePrime(p, q))
<a name="l00503"></a>00503                                 <span class="keywordflow">return</span> p;
<a name="l00504"></a>00504                 }
<a name="l00505"></a>00505         }
<a name="l00506"></a>00506 
<a name="l00507"></a>00507         <span class="comment">// not reached</span>
<a name="l00508"></a>00508         <span class="keywordflow">return</span> p;
<a name="l00509"></a>00509 }
<a name="l00510"></a>00510 
<a name="l00511"></a>00511 Integer MaurerProvablePrime(<a class="code" href="class_random_number_generator.html" title="interface for random number generators">RandomNumberGenerator</a> &amp;rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits)
<a name="l00512"></a>00512 {
<a name="l00513"></a>00513         <span class="keyword">const</span> <span class="keywordtype">unsigned</span> smallPrimeBound = 29, c_opt=10;
<a name="l00514"></a>00514         Integer p;
<a name="l00515"></a>00515 
<a name="l00516"></a>00516         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> primeTableSize;
<a name="l00517"></a>00517         <span class="keyword">const</span> word16 * primeTable = GetPrimeTable(primeTableSize);
<a name="l00518"></a>00518 
<a name="l00519"></a>00519         <span class="keywordflow">if</span> (bits &lt; smallPrimeBound)
<a name="l00520"></a>00520         {
<a name="l00521"></a>00521                 <span class="keywordflow">do</span>
<a name="l00522"></a>00522                         p.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(bits-1), <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(bits)-1, <a class="code" href="class_integer.html#9b4088ac01abf76b9ba60060abccb7a3d9b396a7ba736a4ca02db0125cc8c6a4">Integer::ANY</a>, 1, 2);
<a name="l00523"></a>00523                 <span class="keywordflow">while</span> (TrialDivision(p, 1 &lt;&lt; ((bits+1)/2)));
<a name="l00524"></a>00524         }
<a name="l00525"></a>00525         <span class="keywordflow">else</span>
<a name="l00526"></a>00526         {
<a name="l00527"></a>00527                 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> margin = bits &gt; 50 ? 20 : (bits-10)/2;
<a name="l00528"></a>00528                 <span class="keywordtype">double</span> relativeSize;
<a name="l00529"></a>00529                 <span class="keywordflow">do</span>
<a name="l00530"></a>00530                         relativeSize = pow(2.0, <span class="keywordtype">double</span>(rng.GenerateWord32())/0xffffffff - 1);
<a name="l00531"></a>00531                 <span class="keywordflow">while</span> (bits * relativeSize &gt;= bits - margin);
<a name="l00532"></a>00532 
<a name="l00533"></a>00533                 Integer a,b;
<a name="l00534"></a>00534                 Integer q = MaurerProvablePrime(rng, <span class="keywordtype">unsigned</span>(bits*relativeSize));
<a name="l00535"></a>00535                 Integer I = <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(bits-2)/q;
<a name="l00536"></a>00536                 Integer I2 = I &lt;&lt; 1;
<a name="l00537"></a>00537                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> trialDivisorBound = (<span class="keywordtype">unsigned</span> int)STDMIN((<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)primeTable[primeTableSize-1], (<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)bits*bits/c_opt);
<a name="l00538"></a>00538                 <span class="keywordtype">bool</span> success = <span class="keyword">false</span>;
<a name="l00539"></a>00539                 <span class="keywordflow">while</span> (!success)
<a name="l00540"></a>00540                 {
<a name="l00541"></a>00541                         p.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, I, I2, <a class="code" href="class_integer.html#9b4088ac01abf76b9ba60060abccb7a3d9b396a7ba736a4ca02db0125cc8c6a4">Integer::ANY</a>);
<a name="l00542"></a>00542                         p *= q; p &lt;&lt;= 1; ++p;
<a name="l00543"></a>00543                         <span class="keywordflow">if</span> (!TrialDivision(p, trialDivisorBound))
<a name="l00544"></a>00544                         {
<a name="l00545"></a>00545                                 a.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, 2, p-1, <a class="code" href="class_integer.html#9b4088ac01abf76b9ba60060abccb7a3d9b396a7ba736a4ca02db0125cc8c6a4">Integer::ANY</a>);
<a name="l00546"></a>00546                                 b = a_exp_b_mod_c(a, (p-1)/q, p);
<a name="l00547"></a>00547                                 success = (GCD(b-1, p) == 1) &amp;&amp; (a_exp_b_mod_c(b, q, p) == 1);
<a name="l00548"></a>00548                         }
<a name="l00549"></a>00549                 }
<a name="l00550"></a>00550         }
<a name="l00551"></a>00551         <span class="keywordflow">return</span> p;
<a name="l00552"></a>00552 }
<a name="l00553"></a>00553 
<a name="l00554"></a>00554 Integer CRT(<span class="keyword">const</span> Integer &amp;xp, <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;xq, <span class="keyword">const</span> Integer &amp;q, <span class="keyword">const</span> Integer &amp;u)
<a name="l00555"></a>00555 {
<a name="l00556"></a>00556         <span class="comment">// isn't operator overloading great?</span>
<a name="l00557"></a>00557         <span class="keywordflow">return</span> p * (u * (xq-xp) % q) + xp;
<a name="l00558"></a>00558 <span class="comment">/*</span>
<a name="l00559"></a>00559 <span class="comment">        Integer t1 = xq-xp;</span>
<a name="l00560"></a>00560 <span class="comment">        cout &lt;&lt; hex &lt;&lt; t1 &lt;&lt; endl;</span>
<a name="l00561"></a>00561 <span class="comment">        Integer t2 = u * t1;</span>
<a name="l00562"></a>00562 <span class="comment">        cout &lt;&lt; hex &lt;&lt; t2 &lt;&lt; endl;</span>
<a name="l00563"></a>00563 <span class="comment">        Integer t3 = t2 % q;</span>
<a name="l00564"></a>00564 <span class="comment">        cout &lt;&lt; hex &lt;&lt; t3 &lt;&lt; endl;</span>
<a name="l00565"></a>00565 <span class="comment">        Integer t4 = p * t3;</span>
<a name="l00566"></a>00566 <span class="comment">        cout &lt;&lt; hex &lt;&lt; t4 &lt;&lt; endl;</span>
<a name="l00567"></a>00567 <span class="comment">        Integer t5 = t4 + xp;</span>
<a name="l00568"></a>00568 <span class="comment">        cout &lt;&lt; hex &lt;&lt; t5 &lt;&lt; endl;</span>
<a name="l00569"></a>00569 <span class="comment">        return t5;</span>
<a name="l00570"></a>00570 <span class="comment">*/</span>
<a name="l00571"></a>00571 }
<a name="l00572"></a>00572 
<a name="l00573"></a>00573 Integer CRT(<span class="keyword">const</span> Integer &amp;xp, <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;xq, <span class="keyword">const</span> Integer &amp;q)
<a name="l00574"></a>00574 {
<a name="l00575"></a>00575         <span class="keywordflow">return</span> CRT(xp, p, xq, q, EuclideanMultiplicativeInverse(p, q));
<a name="l00576"></a>00576 }
<a name="l00577"></a>00577 
<a name="l00578"></a>00578 Integer ModularSquareRoot(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;p)
<a name="l00579"></a>00579 {
<a name="l00580"></a>00580         <span class="keywordflow">if</span> (p%4 == 3)
<a name="l00581"></a>00581                 <span class="keywordflow">return</span> a_exp_b_mod_c(a, (p+1)/4, p);
<a name="l00582"></a>00582 
<a name="l00583"></a>00583         Integer q=p-1;
<a name="l00584"></a>00584         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> r=0;
<a name="l00585"></a>00585         <span class="keywordflow">while</span> (q.<a class="code" href="class_integer.html#fedf9af097a3417d8bd3742ec53f9593">IsEven</a>())
<a name="l00586"></a>00586         {
<a name="l00587"></a>00587                 r++;
<a name="l00588"></a>00588                 q &gt;&gt;= 1;
<a name="l00589"></a>00589         }
<a name="l00590"></a>00590 
<a name="l00591"></a>00591         Integer n=2;
<a name="l00592"></a>00592         <span class="keywordflow">while</span> (Jacobi(n, p) != -1)
<a name="l00593"></a>00593                 ++n;
<a name="l00594"></a>00594 
<a name="l00595"></a>00595         Integer y = a_exp_b_mod_c(n, q, p);
<a name="l00596"></a>00596         Integer x = a_exp_b_mod_c(a, (q-1)/2, p);
<a name="l00597"></a>00597         Integer b = (x.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()%p)*a%p;
<a name="l00598"></a>00598         x = a*x%p;
<a name="l00599"></a>00599         Integer tempb, t;
<a name="l00600"></a>00600 
<a name="l00601"></a>00601         <span class="keywordflow">while</span> (b != 1)
<a name="l00602"></a>00602         {
<a name="l00603"></a>00603                 <span class="keywordtype">unsigned</span> m=0;
<a name="l00604"></a>00604                 tempb = b;
<a name="l00605"></a>00605                 <span class="keywordflow">do</span>
<a name="l00606"></a>00606                 {
<a name="l00607"></a>00607                         m++;
<a name="l00608"></a>00608                         b = b.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()%p;
<a name="l00609"></a>00609                         <span class="keywordflow">if</span> (m==r)
<a name="l00610"></a>00610                                 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#19b7e6d48b1b57bd4846160ea2928175" title="avoid calling constructors for these frequently used integers">Integer::Zero</a>();
<a name="l00611"></a>00611                 }
<a name="l00612"></a>00612                 <span class="keywordflow">while</span> (b != 1);
<a name="l00613"></a>00613 
<a name="l00614"></a>00614                 t = y;
<a name="l00615"></a>00615                 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=0; i&lt;r-m-1; i++)
<a name="l00616"></a>00616                         t = t.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()%p;
<a name="l00617"></a>00617                 y = t.<a cla