<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Crypto++: nbtheory.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.3.7 -->
<div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Class List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Class Members</a> | <a class="qindex" href="globals.html">File Members</a></div>
<h1>nbtheory.h</h1><pre class="fragment"><div>00001 <span class="comment">// nbtheory.h - written and placed in the public domain by Wei Dai</span>
00002
00003 <span class="preprocessor">#ifndef CRYPTOPP_NBTHEORY_H</span>
00004 <span class="preprocessor"></span><span class="preprocessor">#define CRYPTOPP_NBTHEORY_H</span>
00005 <span class="preprocessor"></span>
00006 <span class="preprocessor">#include "<a class="code" href="integer_8h.html">integer.h</a>"</span>
00007 <span class="preprocessor">#include "algparam.h"</span>
00008
00009 NAMESPACE_BEGIN(CryptoPP)
00010
00011 <span class="comment">// obtain pointer to small prime table and get its size</span>
00012 CRYPTOPP_DLL const word16 * GetPrimeTable(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> &size);
00013
00014 <span class="comment">// ************ primality testing ****************</span>
00015
00016 <span class="comment">// generate a provable prime</span>
00017 CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> MaurerProvablePrime(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits);
00018 CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> MihailescuProvablePrime(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits);
00019
00020 CRYPTOPP_DLL <span class="keywordtype">bool</span> IsSmallPrime(const <a class="code" href="class_integer.html">Integer</a> &p);
00021
00022 <span class="comment">// returns true if p is divisible by some prime less than bound</span>
00023 <span class="comment">// bound not be greater than the largest entry in the prime table</span>
00024 CRYPTOPP_DLL <span class="keywordtype">bool</span> TrialDivision(const <a class="code" href="class_integer.html">Integer</a> &p, <span class="keywordtype">unsigned</span> bound);
00025
00026 <span class="comment">// returns true if p is NOT divisible by small primes</span>
00027 CRYPTOPP_DLL <span class="keywordtype">bool</span> SmallDivisorsTest(const <a class="code" href="class_integer.html">Integer</a> &p);
00028
00029 <span class="comment">// These is no reason to use these two, use the ones below instead</span>
00030 CRYPTOPP_DLL <span class="keywordtype">bool</span> IsFermatProbablePrime(const <a class="code" href="class_integer.html">Integer</a> &n, const <a class="code" href="class_integer.html">Integer</a> &b);
00031 CRYPTOPP_DLL <span class="keywordtype">bool</span> IsLucasProbablePrime(const <a class="code" href="class_integer.html">Integer</a> &n);
00032
00033 CRYPTOPP_DLL <span class="keywordtype">bool</span> IsStrongProbablePrime(const <a class="code" href="class_integer.html">Integer</a> &n, const <a class="code" href="class_integer.html">Integer</a> &b);
00034 CRYPTOPP_DLL <span class="keywordtype">bool</span> IsStrongLucasProbablePrime(const <a class="code" href="class_integer.html">Integer</a> &n);
00035
00036 <span class="comment">// Rabin-Miller primality test, i.e. repeating the strong probable prime test </span>
00037 <span class="comment">// for several rounds with random bases</span>
00038 CRYPTOPP_DLL <span class="keywordtype">bool</span> RabinMillerTest(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, const <a class="code" href="class_integer.html">Integer</a> &w, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> rounds);
00039
00040 <span class="comment">// primality test, used to generate primes</span>
00041 CRYPTOPP_DLL <span class="keywordtype">bool</span> IsPrime(const <a class="code" href="class_integer.html">Integer</a> &p);
00042
00043 <span class="comment">// more reliable than IsPrime(), used to verify primes generated by others</span>
00044 CRYPTOPP_DLL <span class="keywordtype">bool</span> VerifyPrime(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, const <a class="code" href="class_integer.html">Integer</a> &p, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> level = 1);
00045
00046 class PrimeSelector
00047 {
00048 <span class="keyword">public</span>:
00049 <span class="keyword">const</span> PrimeSelector *GetSelectorPointer()<span class="keyword"> const </span>{<span class="keywordflow">return</span> <span class="keyword">this</span>;}
00050 <span class="keyword">virtual</span> <span class="keywordtype">bool</span> IsAcceptable(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &candidate) <span class="keyword">const</span> =0;
00051 };
00052
00053 <span class="comment">// use a fast sieve to find the first probable prime in {x | p<=x<=max and x%mod==equiv}</span>
00054 <span class="comment">// returns true iff successful, value of p is undefined if no such prime exists</span>
00055 CRYPTOPP_DLL <span class="keywordtype">bool</span> FirstPrime(<a class="code" href="class_integer.html">Integer</a> &p, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &max, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &equiv, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &mod, <span class="keyword">const</span> PrimeSelector *pSelector);
00056
00057 CRYPTOPP_DLL <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> &max);
00058
00059 CRYPTOPP_DLL AlgorithmParameters<AlgorithmParameters<AlgorithmParameters<NullNameValuePairs, Integer::RandomNumberType>, <a class="code" href="class_integer.html">Integer</a>>, Integer>
00060 MakeParametersForTwoPrimesOfEqualSize(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> productBitLength);
00061
00062 <span class="comment">// ********** other number theoretic functions ************</span>
00063
00064 <span class="keyword">inline</span> Integer GCD(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &b)
00065 {<span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz49_12">Integer::Gcd</a>(a,b);}
00066 <span class="keyword">inline</span> <span class="keywordtype">bool</span> RelativelyPrime(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &b)
00067 {<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_13">Integer::One</a>();}
00068 <span class="keyword">inline</span> Integer LCM(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &b)
00069 {<span class="keywordflow">return</span> a/<a class="code" href="class_integer.html#_integerz49_12">Integer::Gcd</a>(a,b)*b;}
00070 <span class="keyword">inline</span> Integer EuclideanMultiplicativeInverse(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &b)
00071 {<span class="keywordflow">return</span> a.InverseMod(b);}
00072
00073 <span class="comment">// use Chinese Remainder Theorem to calculate x given x mod p and x mod q</span>
00074 CRYPTOPP_DLL Integer CRT(<span class="keyword">const</span> Integer &xp, <span class="keyword">const</span> Integer &p, <span class="keyword">const</span> Integer &xq, <span class="keyword">const</span> Integer &q);
00075 <span class="comment">// use this one if u = inverse of p mod q has been precalculated</span>
00076 CRYPTOPP_DLL Integer CRT(<span class="keyword">const</span> Integer &xp, <span class="keyword">const</span> Integer &p, <span class="keyword">const</span> Integer &xq, <span class="keyword">const</span> Integer &q, <span class="keyword">const</span> Integer &u);
00077
00078 <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>
00079 <span class="comment">// check a number theory book for what Jacobi symbol means when b is not prime</span>
00080 CRYPTOPP_DLL <span class="keywordtype">int</span> Jacobi(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &b);
00081
00082 <span class="comment">// calculates the Lucas function V_e(p, 1) mod n</span>
00083 CRYPTOPP_DLL Integer Lucas(<span class="keyword">const</span> Integer &e, <span class="keyword">const</span> Integer &p, <span class="keyword">const</span> Integer &n);
00084 <span class="comment">// calculates x such that m==Lucas(e, x, p*q), p q primes</span>
00085 CRYPTOPP_DLL Integer InverseLucas(<span class="keyword">const</span> Integer &e, <span class="keyword">const</span> Integer &m, <span class="keyword">const</span> Integer &p, <span class="keyword">const</span> Integer &q);
00086 <span class="comment">// use this one if u=inverse of p mod q has been precalculated</span>
00087 CRYPTOPP_DLL Integer InverseLucas(<span class="keyword">const</span> Integer &e, <span class="keyword">const</span> Integer &m, <span class="keyword">const</span> Integer &p, <span class="keyword">const</span> Integer &q, <span class="keyword">const</span> Integer &u);
00088
00089 <span class="keyword">inline</span> Integer ModularExponentiation(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &e, <span class="keyword">const</span> Integer &m)
00090 {<span class="keywordflow">return</span> a_exp_b_mod_c(a, e, m);}
00091 <span class="comment">// returns x such that x*x%p == a, p prime</span>
00092 CRYPTOPP_DLL Integer ModularSquareRoot(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &p);
00093 <span class="comment">// returns x such that a==ModularExponentiation(x, e, p*q), p q primes,</span>
00094 <span class="comment">// and e relatively prime to (p-1)*(q-1)</span>
00095 CRYPTOPP_DLL Integer ModularRoot(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &e, <span class="keyword">const</span> Integer &p, <span class="keyword">const</span> Integer &q);
00096 <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>
00097 <span class="comment">// and u=inverse of p mod q have been precalculated</span>
00098 CRYPTOPP_DLL Integer ModularRoot(<span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &dp, <span class="keyword">const</span> Integer &dq, <span class="keyword">const</span> Integer &p, <span class="keyword">const</span> Integer &q, <span class="keyword">const</span> Integer &u);
00099
00100 <span class="comment">// find r1 and r2 such that ax^2 + bx + c == 0 (mod p) for x in {r1, r2}, p prime</span>
00101 <span class="comment">// returns true if solutions exist</span>
00102 CRYPTOPP_DLL <span class="keywordtype">bool</span> SolveModularQuadraticEquation(Integer &r1, Integer &r2, <span class="keyword">const</span> Integer &a, <span class="keyword">const</span> Integer &b, <span class="keyword">const</span> Integer &c, <span class="keyword">const</span> Integer &p);
00103
00104 <span class="comment">// returns log base 2 of estimated number of operations to calculate discrete log or factor a number</span>
00105 CRYPTOPP_DLL <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> DiscreteLogWorkFactor(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitlength);
00106 CRYPTOPP_DLL <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> FactoringWorkFactor(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitlength);
00107
00108 <span class="comment">// ********************************************************</span>
00109 <span class="comment"></span>
00110 <span class="comment">//! generator of prime numbers of special forms</span>
<a name="l00111"></a><a class="code" href="class_prime_and_generator.html">00111</a> <span class="comment"></span><span class="keyword">class </span>CRYPTOPP_DLL PrimeAndGenerator
00112 {
00113 <span class="keyword">public</span>:
00114 PrimeAndGenerator() {}
00115 <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>
00116 <span class="comment">// Precondition: pbits > 5</span>
00117 <span class="comment">// warning: this is slow, because primes of this form are harder to find</span>
00118 PrimeAndGenerator(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits)
00119 {Generate(delta, rng, pbits, pbits-1);}
00120 <span class="comment">// generate a random prime p of the form 2*r*q+delta, where q is also prime</span>
00121 <span class="comment">// Precondition: qbits > 4 && pbits > qbits</span>
00122 PrimeAndGenerator(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits, <span class="keywordtype">unsigned</span> qbits)
00123 {Generate(delta, rng, pbits, qbits);}
00124
00125 <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> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits, <span class="keywordtype">unsigned</span> qbits);
00126
00127 <span class="keyword">const</span> Integer& Prime()<span class="keyword"> const </span>{<span class="keywordflow">return</span> p;}
00128 <span class="keyword">const</span> Integer& SubPrime()<span class="keyword"> const </span>{<span class="keywordflow">return</span> q;}
00129 <span class="keyword">const</span> Integer& Generator()<span class="keyword"> const </span>{<span class="keywordflow">return</span> g;}
00130
00131 <span class="keyword">private</span>:
00132 Integer p, q, g;
00133 };
00134
00135 NAMESPACE_END
00136
00137 <span class="preprocessor">#endif</span>
</div></pre><hr size="1"><address style="align: right;"><small>Generated on Sun Nov 7 08:23:58 2004 for Crypto++ by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 ></a> 1.3.7 </small></address>
</body>
</html>
distrib
>
Mandriva
>
10.2
>
i586
>
media
>
contrib
>
by-pkgid
>
7457b841ac8136d3a1a9d3d960c5252e
>
files
>
1335
