00001
00002
00003
00004
00005
00006 #ifndef CRYPTOPP_NBTHEORY_H
00007 #define CRYPTOPP_NBTHEORY_H
00008
00009 #include "cryptlib.h"
00010 #include "integer.h"
00011 #include "algparam.h"
00012
00013 NAMESPACE_BEGIN(CryptoPP)
00014
00015
00016 CRYPTOPP_DLL const word16 * CRYPTOPP_API GetPrimeTable(unsigned int &size);
00017
00018
00019
00020
00021
00022
00023
00024 CRYPTOPP_DLL Integer CRYPTOPP_API MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits);
00025
00026
00027
00028
00029
00030
00031 CRYPTOPP_DLL Integer CRYPTOPP_API MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits);
00032
00033
00034
00035
00036
00037
00038
00039 CRYPTOPP_DLL bool CRYPTOPP_API IsSmallPrime(const Integer &p);
00040
00041
00042
00043
00044
00045 CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision(const Integer &p, unsigned bound);
00046
00047
00048 CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest(const Integer &p);
00049
00050
00051 CRYPTOPP_DLL bool CRYPTOPP_API IsFermatProbablePrime(const Integer &n, const Integer &b);
00052 CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime(const Integer &n);
00053
00054 CRYPTOPP_DLL bool CRYPTOPP_API IsStrongProbablePrime(const Integer &n, const Integer &b);
00055 CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime(const Integer &n);
00056
00057
00058
00059 CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest(RandomNumberGenerator &rng, const Integer &w, unsigned int rounds);
00060
00061
00062
00063
00064
00065
00066 CRYPTOPP_DLL bool CRYPTOPP_API IsPrime(const Integer &p);
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076 CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level = 1);
00077
00078
00079
00080 class CRYPTOPP_DLL PrimeSelector
00081 {
00082 public:
00083 const PrimeSelector *GetSelectorPointer() const {return this;}
00084 virtual bool IsAcceptable(const Integer &candidate) const =0;
00085 };
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097 CRYPTOPP_DLL bool CRYPTOPP_API FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector);
00098
00099 CRYPTOPP_DLL unsigned int CRYPTOPP_API PrimeSearchInterval(const Integer &max);
00100
00101 CRYPTOPP_DLL AlgorithmParameters CRYPTOPP_API MakeParametersForTwoPrimesOfEqualSize(unsigned int productBitLength);
00102
00103
00104
00105 inline Integer GCD(const Integer &a, const Integer &b)
00106 {return Integer::Gcd(a,b);}
00107 inline bool RelativelyPrime(const Integer &a, const Integer &b)
00108 {return Integer::Gcd(a,b) == Integer::One();}
00109 inline Integer LCM(const Integer &a, const Integer &b)
00110 {return a/Integer::Gcd(a,b)*b;}
00111 inline Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
00112 {return a.InverseMod(b);}
00113
00114
00115 CRYPTOPP_DLL Integer CRYPTOPP_API CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u);
00116
00117
00118
00119 CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b);
00120
00121
00122 CRYPTOPP_DLL Integer CRYPTOPP_API Lucas(const Integer &e, const Integer &p, const Integer &n);
00123
00124 CRYPTOPP_DLL Integer CRYPTOPP_API InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u);
00125
00126 inline Integer ModularExponentiation(const Integer &a, const Integer &e, const Integer &m)
00127 {return a_exp_b_mod_c(a, e, m);}
00128
00129 CRYPTOPP_DLL Integer CRYPTOPP_API ModularSquareRoot(const Integer &a, const Integer &p);
00130
00131
00132
00133
00134 CRYPTOPP_DLL Integer CRYPTOPP_API ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u);
00135
00136
00137
00138 CRYPTOPP_DLL bool CRYPTOPP_API SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p);
00139
00140
00141 CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor(unsigned int bitlength);
00142 CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor(unsigned int bitlength);
00143
00144
00145
00146
00147 class CRYPTOPP_DLL PrimeAndGenerator
00148 {
00149 public:
00150 PrimeAndGenerator() {}
00151
00152
00153
00154 PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits)
00155 {Generate(delta, rng, pbits, pbits-1);}
00156
00157
00158 PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
00159 {Generate(delta, rng, pbits, qbits);}
00160
00161 void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits);
00162
00163 const Integer& Prime() const {return p;}
00164 const Integer& SubPrime() const {return q;}
00165 const Integer& Generator() const {return g;}
00166
00167 private:
00168 Integer p, q, g;
00169 };
00170
00171 NAMESPACE_END
00172
00173 #endif