nbtheory_8h-source.html

来自「Crypto++是一个非常强大的密码学库,主要是功能全」· HTML 代码 · 共 157 行 · 第 1/2 页

00073         {<span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz49_12">Integer::Gcd</a>(a,b) == <a class="code" href="class_integer.html#_integerz37_11">Integer::One</a>();}
00074 <span class="keyword">inline</span> Integer LCM(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;b)
00075         {<span class="keywordflow">return</span> a/<a class="code" href="class_integer.html#_integerz49_12">Integer::Gcd</a>(a,b)*b;}
00076 <span class="keyword">inline</span> Integer EuclideanMultiplicativeInverse(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;b)
00077         {<span class="keywordflow">return</span> a.InverseMod(b);}
00078 
00079 <span class="comment">// use Chinese Remainder Theorem to calculate x given x mod p and x mod q</span>
00080 CRYPTOPP_DLL 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);
00081 <span class="comment">// use this one if u = inverse of p mod q has been precalculated</span>
00082 CRYPTOPP_DLL 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);
00083 
00084 <span class="comment">// if b is prime, then Jacobi(a, b) returns 0 if a%b==0, 1 if a is quadratic residue mod b, -1 otherwise</span>
00085 <span class="comment">// check a number theory book for what Jacobi symbol means when b is not prime</span>
00086 CRYPTOPP_DLL <span class="keywordtype">int</span> Jacobi(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;b);
00087 
00088 <span class="comment">// calculates the Lucas function V_e(p, 1) mod n</span>
00089 CRYPTOPP_DLL Integer Lucas(<span class="keyword">const</span> Integer &amp;e, <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;n);
00090 <span class="comment">// calculates x such that m==Lucas(e, x, p*q), p q primes</span>
00091 CRYPTOPP_DLL Integer InverseLucas(<span class="keyword">const</span> Integer &amp;e, <span class="keyword">const</span> Integer &amp;m, <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;q);
00092 <span class="comment">// use this one if u=inverse of p mod q has been precalculated</span>
00093 CRYPTOPP_DLL Integer InverseLucas(<span class="keyword">const</span> Integer &amp;e, <span class="keyword">const</span> Integer &amp;m, <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;q, <span class="keyword">const</span> Integer &amp;u);
00094 
00095 <span class="keyword">inline</span> Integer ModularExponentiation(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;e, <span class="keyword">const</span> Integer &amp;m)
00096         {<span class="keywordflow">return</span> a_exp_b_mod_c(a, e, m);}
00097 <span class="comment">// returns x such that x*x%p == a, p prime</span>
00098 CRYPTOPP_DLL Integer ModularSquareRoot(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;p);
00099 <span class="comment">// returns x such that a==ModularExponentiation(x, e, p*q), p q primes,</span>
00100 <span class="comment">// and e relatively prime to (p-1)*(q-1)</span>
00101 CRYPTOPP_DLL Integer ModularRoot(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;e, <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;q);
00102 <span class="comment">// use this one if dp=d%(p-1), dq=d%(q-1), (d is inverse of e mod (p-1)*(q-1))</span>
00103 <span class="comment">// and u=inverse of p mod q have been precalculated</span>
00104 CRYPTOPP_DLL Integer ModularRoot(<span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;dp, <span class="keyword">const</span> Integer &amp;dq, <span class="keyword">const</span> Integer &amp;p, <span class="keyword">const</span> Integer &amp;q, <span class="keyword">const</span> Integer &amp;u);
00105 
00106 <span class="comment">// find r1 and r2 such that ax^2 + bx + c == 0 (mod p) for x in {r1, r2}, p prime</span>
00107 <span class="comment">// returns true if solutions exist</span>
00108 CRYPTOPP_DLL <span class="keywordtype">bool</span> SolveModularQuadraticEquation(Integer &amp;r1, Integer &amp;r2, <span class="keyword">const</span> Integer &amp;a, <span class="keyword">const</span> Integer &amp;b, <span class="keyword">const</span> Integer &amp;c, <span class="keyword">const</span> Integer &amp;p);
00109 
00110 <span class="comment">// returns log base 2 of estimated number of operations to calculate discrete log or factor a number</span>
00111 CRYPTOPP_DLL <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> DiscreteLogWorkFactor(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitlength);
00112 CRYPTOPP_DLL <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> FactoringWorkFactor(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitlength);
00113 
00114 <span class="comment">// ********************************************************</span>
00115 <span class="comment"></span>
00116 <span class="comment">//! generator of prime numbers of special forms</span>
<a name="l00117"></a><a class="code" href="class_prime_and_generator.html">00117</a> <span class="comment"></span><span class="keyword">class </span>CRYPTOPP_DLL PrimeAndGenerator
00118 {
00119 <span class="keyword">public</span>:
00120         PrimeAndGenerator() {}
00121         <span class="comment">// generate a random prime p of the form 2*q+delta, where delta is 1 or -1 and q is also prime</span>
00122         <span class="comment">// Precondition: pbits &gt; 5</span>
00123         <span class="comment">// warning: this is slow, because primes of this form are harder to find</span>
00124         PrimeAndGenerator(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &amp;rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits)
00125                 {Generate(delta, rng, pbits, pbits-1);}
00126         <span class="comment">// generate a random prime p of the form 2*r*q+delta, where q is also prime</span>
00127         <span class="comment">// Precondition: qbits &gt; 4 &amp;&amp; pbits &gt; qbits</span>
00128         PrimeAndGenerator(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &amp;rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits, <span class="keywordtype">unsigned</span> qbits)
00129                 {Generate(delta, rng, pbits, qbits);}
00130         
00131         <span class="keywordtype">void</span> Generate(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &amp;rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits, <span class="keywordtype">unsigned</span> qbits);
00132 
00133         <span class="keyword">const</span> Integer&amp; Prime()<span class="keyword"> const </span>{<span class="keywordflow">return</span> p;}
00134         <span class="keyword">const</span> Integer&amp; SubPrime()<span class="keyword"> const </span>{<span class="keywordflow">return</span> q;}
00135         <span class="keyword">const</span> Integer&amp; Generator()<span class="keyword"> const </span>{<span class="keywordflow">return</span> g;}
00136 
00137 <span class="keyword">private</span>:
00138         Integer p, q, g;
00139 };
00140 
00141 NAMESPACE_END
00142 
00143 <span class="preprocessor">#endif</span>
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Tue Jul 8 23:34:21 2003 for Crypto++ by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 > 
</a>1.3.2 </small></address>
</body>
</html>