Fabcoin Core  0.16.2
P2P Digital Currency
nbtheory.h
Go to the documentation of this file.
1 // nbtheory.h - written and placed in the public domain by Wei Dai
2 
5 
6 #ifndef CRYPTOPP_NBTHEORY_H
7 #define CRYPTOPP_NBTHEORY_H
8 
9 #include "cryptlib.h"
10 #include "integer.h"
11 #include "algparam.h"
12 
14 
15 // obtain pointer to small prime table and get its size
16 CRYPTOPP_DLL const word16 * CRYPTOPP_API GetPrimeTable(unsigned int &size);
17 
18 // ************ primality testing ****************
19 
25 
32 
40 
45 CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision(const Integer &p, unsigned bound);
46 
47 // returns true if p is NOT divisible by small primes
49 
50 // These is no reason to use these two, use the ones below instead
53 
56 
57 // Rabin-Miller primality test, i.e. repeating the strong probable prime test
58 // for several rounds with random bases
59 CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest(RandomNumberGenerator &rng, const Integer &w, unsigned int rounds);
60 
67 
76 CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level = 1);
77 
81 {
82 public:
83  const PrimeSelector *GetSelectorPointer() const {return this;}
84  virtual bool IsAcceptable(const Integer &candidate) const =0;
85 };
86 
97 CRYPTOPP_DLL bool CRYPTOPP_API FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector);
98 
99 CRYPTOPP_DLL unsigned int CRYPTOPP_API PrimeSearchInterval(const Integer &max);
100 
102 
103 // ********** other number theoretic functions ************
104 
105 inline Integer GCD(const Integer &a, const Integer &b)
106  {return Integer::Gcd(a,b);}
107 inline bool RelativelyPrime(const Integer &a, const Integer &b)
108  {return Integer::Gcd(a,b) == Integer::One();}
109 inline Integer LCM(const Integer &a, const Integer &b)
110  {return a/Integer::Gcd(a,b)*b;}
112  {return a.InverseMod(b);}
113 
114 // use Chinese Remainder Theorem to calculate x given x mod p and x mod q, and u = inverse of p mod q
115 CRYPTOPP_DLL Integer CRYPTOPP_API CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u);
116 
117 // if b is prime, then Jacobi(a, b) returns 0 if a%b==0, 1 if a is quadratic residue mod b, -1 otherwise
118 // check a number theory book for what Jacobi symbol means when b is not prime
119 CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b);
120 
121 // calculates the Lucas function V_e(p, 1) mod n
122 CRYPTOPP_DLL Integer CRYPTOPP_API Lucas(const Integer &e, const Integer &p, const Integer &n);
123 // calculates x such that m==Lucas(e, x, p*q), p q primes, u=inverse of p mod q
124 CRYPTOPP_DLL Integer CRYPTOPP_API InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u);
125 
126 inline Integer ModularExponentiation(const Integer &a, const Integer &e, const Integer &m)
127  {return a_exp_b_mod_c(a, e, m);}
128 // returns x such that x*x%p == a, p prime
130 // returns x such that a==ModularExponentiation(x, e, p*q), p q primes,
131 // and e relatively prime to (p-1)*(q-1)
132 // dp=d%(p-1), dq=d%(q-1), (d is inverse of e mod (p-1)*(q-1))
133 // and u=inverse of p mod q
134 CRYPTOPP_DLL Integer CRYPTOPP_API ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u);
135 
136 // find r1 and r2 such that ax^2 + bx + c == 0 (mod p) for x in {r1, r2}, p prime
137 // returns true if solutions exist
139 
140 // returns log base 2 of estimated number of operations to calculate discrete log or factor a number
141 CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor(unsigned int bitlength);
142 CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor(unsigned int bitlength);
143 
144 // ********************************************************
145 
149 {
150 public:
153 
162  PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits)
163  {Generate(delta, rng, pbits, pbits-1);}
164 
173  PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
174  {Generate(delta, rng, pbits, qbits);}
175 
182  void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits);
183 
186  const Integer& Prime() const {return p;}
187 
190  const Integer& SubPrime() const {return q;}
191 
194  const Integer& Generator() const {return g;}
195 
196 private:
197  Integer p, q, g;
198 };
199 
201 
202 #endif
Classes for working with NameValuePairs.
CRYPTOPP_DLL bool CRYPTOPP_API FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
Finds a random prime of special form.
Definition: nbtheory.cpp:381
CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest(RandomNumberGenerator &rng, const Integer &w, unsigned int rounds)
Definition: nbtheory.cpp:140
unsigned short word16
Definition: config.h:230
static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n)
greatest common divisor
Definition: integer.cpp:4365
CRYPTOPP_DLL Integer CRYPTOPP_API MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
Definition: nbtheory.cpp:472
#define NAMESPACE_BEGIN(x)
Definition: config.h:200
CRYPTOPP_DLL Integer CRYPTOPP_API ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Definition: nbtheory.cpp:648
Abstract base classes that provide a uniform interface to this library.
CRYPTOPP_DLL bool CRYPTOPP_API IsPrime(const Integer &p)
Verifies a prime number.
Definition: nbtheory.cpp:239
#define g(i)
Definition: sha.cpp:735
#define c(i)
Interface for random number generators.
Definition: cryptlib.h:1188
PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits)
Construct a PrimeAndGenerator.
Definition: nbtheory.h:162
Generator of prime numbers of special forms.
Definition: nbtheory.h:148
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition: integer.cpp:3035
Integer ModularExponentiation(const Integer &a, const Integer &e, const Integer &m)
Definition: nbtheory.h:126
CRYPTOPP_DLL Integer CRYPTOPP_API MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
Definition: nbtheory.cpp:512
Integer GCD(const Integer &a, const Integer &b)
Definition: nbtheory.h:105
#define a(i)
#define r1(i)
CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime(const Integer &n)
Definition: nbtheory.cpp:157
const Integer & Generator() const
Retrieve the generator.
Definition: nbtheory.h:194
CRYPTOPP_DLL AlgorithmParameters CRYPTOPP_API MakeParametersForTwoPrimesOfEqualSize(unsigned int productBitLength)
Definition: nbtheory.cpp:267
CRYPTOPP_DLL Integer CRYPTOPP_API ModularSquareRoot(const Integer &a, const Integer &p)
Definition: nbtheory.cpp:574
ExecStats::duration max
Definition: ExecStats.cpp:36
#define r2(i)
Application callback to signal suitability of a cabdidate prime.
Definition: nbtheory.h:80
Multiple precision integer with arithmetic operations.
Definition: integer.h:43
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime(const Integer &n)
Definition: nbtheory.cpp:184
#define CRYPTOPP_API
Definition: config.h:705
Integer LCM(const Integer &a, const Integer &b)
Definition: nbtheory.h:109
CRYPTOPP_DLL bool CRYPTOPP_API SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
Definition: nbtheory.cpp:623
PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Construct a PrimeAndGenerator.
Definition: nbtheory.h:173
CRYPTOPP_DLL Integer CRYPTOPP_API InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
Definition: nbtheory.cpp:1000
#define b(i, j)
CRYPTOPP_DLL bool CRYPTOPP_API IsFermatProbablePrime(const Integer &n, const Integer &b)
Definition: nbtheory.cpp:98
CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision(const Integer &p, unsigned bound)
Definition: nbtheory.cpp:73
CRYPTOPP_DLL unsigned int CRYPTOPP_API PrimeSearchInterval(const Integer &max)
Definition: nbtheory.cpp:257
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Definition: nbtheory.h:111
CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor(unsigned int bitlength)
Definition: nbtheory.cpp:1021
uint8_t const size_t const size
Definition: sha3.h:20
CRYPTOPP_DLL Integer CRYPTOPP_API Lucas(const Integer &e, const Integer &p, const Integer &n)
Definition: nbtheory.cpp:814
bool RelativelyPrime(const Integer &a, const Integer &b)
Definition: nbtheory.h:107
An object that implements NameValuePairs.
Definition: algparam.h:433
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:4370
CRYPTOPP_DLL bool CRYPTOPP_API IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
Definition: nbtheory.cpp:62
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongProbablePrime(const Integer &n, const Integer &b)
Definition: nbtheory.cpp:107
Multiple precision integer with arithmetic operations.
#define NAMESPACE_END
Definition: config.h:201
CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Definition: nbtheory.cpp:249
#define e(i)
Definition: sha.cpp:733
Integer a_exp_b_mod_c(const Integer &x, const Integer &e, const Integer &m)
Definition: integer.cpp:4359
const Integer & Prime() const
Retrieve first prime.
Definition: nbtheory.h:186
CRYPTOPP_DLL Integer CRYPTOPP_API CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
Definition: nbtheory.cpp:555
#define CRYPTOPP_DLL
Definition: config.h:704
PrimeAndGenerator()
Construct a PrimeAndGenerator.
Definition: nbtheory.h:152
const PrimeSelector * GetSelectorPointer() const
Definition: nbtheory.h:83
CRYPTOPP_DLL const word16 *CRYPTOPP_API GetPrimeTable(unsigned int &size)
Definition: nbtheory.cpp:55
CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor(unsigned int bitlength)
Definition: nbtheory.cpp:1029
const Integer & SubPrime() const
Retrieve second prime.
Definition: nbtheory.h:190
CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b)
Definition: nbtheory.cpp:787
CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest(const Integer &p)
Definition: nbtheory.cpp:91