Security Scol plugin
nbtheory.h
Go to the documentation of this file.
1// nbtheory.h - originally 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
13NAMESPACE_BEGIN(CryptoPP)
14
15
17CRYPTOPP_DLL const word16 * CRYPTOPP_API GetPrimeTable(unsigned int &size);
18
19// ************ primality testing ****************
20
25CRYPTOPP_DLL Integer CRYPTOPP_API MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits);
26
32CRYPTOPP_DLL Integer CRYPTOPP_API MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits);
33
40CRYPTOPP_DLL bool CRYPTOPP_API IsSmallPrime(const Integer &p);
41
47CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision(const Integer &p, unsigned bound);
48
53CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest(const Integer &p);
54
64CRYPTOPP_DLL bool CRYPTOPP_API IsFermatProbablePrime(const Integer &n, const Integer &b);
65
72CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime(const Integer &n);
73
78CRYPTOPP_DLL bool CRYPTOPP_API IsStrongProbablePrime(const Integer &n, const Integer &b);
79
83CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime(const Integer &n);
84
93CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest(RandomNumberGenerator &rng, const Integer &n, unsigned int rounds);
94
100CRYPTOPP_DLL bool CRYPTOPP_API IsPrime(const Integer &p);
101
110CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level = 1);
111
113class CRYPTOPP_DLL PrimeSelector
114{
115public:
116 virtual ~PrimeSelector() {}
117 const PrimeSelector *GetSelectorPointer() const {return this;}
118 virtual bool IsAcceptable(const Integer &candidate) const =0;
119};
120
131CRYPTOPP_DLL bool CRYPTOPP_API FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector);
132
133CRYPTOPP_DLL unsigned int CRYPTOPP_API PrimeSearchInterval(const Integer &max);
134
135CRYPTOPP_DLL AlgorithmParameters CRYPTOPP_API MakeParametersForTwoPrimesOfEqualSize(unsigned int productBitLength);
136
137// ********** other number theoretic functions ************
138
143inline Integer GCD(const Integer &a, const Integer &b)
144 {return Integer::Gcd(a,b);}
145
150inline bool RelativelyPrime(const Integer &a, const Integer &b)
151 {return Integer::Gcd(a,b) == Integer::One();}
152
157inline Integer LCM(const Integer &a, const Integer &b)
158 {return a/Integer::Gcd(a,b)*b;}
159
167 {return a.InverseMod(b);}
168
169
179CRYPTOPP_DLL Integer CRYPTOPP_API CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u);
180
190CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b);
191
195CRYPTOPP_DLL Integer CRYPTOPP_API Lucas(const Integer &e, const Integer &p, const Integer &n);
196
201CRYPTOPP_DLL Integer CRYPTOPP_API InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u);
202
208inline Integer ModularMultiplication(const Integer &x, const Integer &y, const Integer &m)
209 {return a_times_b_mod_c(x, y, m);}
210
216inline Integer ModularExponentiation(const Integer &x, const Integer &e, const Integer &m)
217 {return a_exp_b_mod_c(x, e, m);}
218
224CRYPTOPP_DLL Integer CRYPTOPP_API ModularSquareRoot(const Integer &a, const Integer &p);
225
232CRYPTOPP_DLL Integer CRYPTOPP_API ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u);
233
244CRYPTOPP_DLL bool CRYPTOPP_API SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p);
245
251CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor(unsigned int bitlength);
252
258CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor(unsigned int bitlength);
259
260// ********************************************************
261
263class CRYPTOPP_DLL PrimeAndGenerator
264{
265public:
268
277 PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits)
278 {Generate(delta, rng, pbits, pbits-1);}
279
288 PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
289 {Generate(delta, rng, pbits, qbits);}
290
297 void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits);
298
301 const Integer& Prime() const {return p;}
302
305 const Integer& SubPrime() const {return q;}
306
309 const Integer& Generator() const {return g;}
310
311private:
312 Integer p, q, g;
313};
314
315NAMESPACE_END
316
317#endif
Classes for working with NameValuePairs.
An object that implements NameValuePairs.
Definition algparam.h:426
Multiple precision integer with arithmetic operations.
Definition integer.h:50
static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n)
Calculate greatest common divisor.
Definition integer.cpp:4468
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition integer.cpp:4920
Generator of prime numbers of special forms.
Definition nbtheory.h:264
const Integer & SubPrime() const
Retrieve second prime.
Definition nbtheory.h:305
PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits)
Construct a PrimeAndGenerator.
Definition nbtheory.h:277
PrimeAndGenerator()
Construct a PrimeAndGenerator.
Definition nbtheory.h:267
const Integer & Generator() const
Retrieve the generator.
Definition nbtheory.h:309
const Integer & Prime() const
Retrieve first prime.
Definition nbtheory.h:301
PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Construct a PrimeAndGenerator.
Definition nbtheory.h:288
Application callback to signal suitability of a cabdidate prime.
Definition nbtheory.h:114
Interface for random number generators.
Definition cryptlib.h:1435
unsigned short word16
16-bit unsigned datatype
Definition config_int.h:59
Abstract base classes that provide a uniform interface to this library.
Multiple precision integer with arithmetic operations.
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
Definition nbtheory.cpp:182
bool RelativelyPrime(const Integer &a, const Integer &b)
Determine relative primality.
Definition nbtheory.h:150
Integer ModularMultiplication(const Integer &x, const Integer &y, const Integer &m)
Modular multiplication.
Definition nbtheory.h:208
CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest(RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
Determine if a number is probably prime.
Definition nbtheory.cpp:138
CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor(unsigned int bitlength)
Estimate work factor.
CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor(unsigned int bitlength)
Estimate work factor.
CRYPTOPP_DLL Integer CRYPTOPP_API ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
Definition nbtheory.cpp:572
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongProbablePrime(const Integer &n, const Integer &b)
Determine if a number is probably prime.
Definition nbtheory.cpp:105
Integer ModularExponentiation(const Integer &x, const Integer &e, const Integer &m)
Modular exponentiation.
Definition nbtheory.h:216
CRYPTOPP_DLL Integer CRYPTOPP_API InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
Calculate the inverse Lucas value.
CRYPTOPP_DLL Integer CRYPTOPP_API Lucas(const Integer &e, const Integer &p, const Integer &n)
Calculate the Lucas value.
Definition nbtheory.cpp:819
CRYPTOPP_DLL bool CRYPTOPP_API SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
Solve a Modular Quadratic Equation.
Definition nbtheory.cpp:621
CRYPTOPP_DLL Integer CRYPTOPP_API CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
Chinese Remainder Theorem.
Definition nbtheory.cpp:553
CRYPTOPP_DLL bool CRYPTOPP_API IsPrime(const Integer &p)
Verifies a number is probably prime.
Definition nbtheory.cpp:237
CRYPTOPP_DLL bool CRYPTOPP_API IsFermatProbablePrime(const Integer &n, const Integer &b)
Determine if a number is probably prime.
Definition nbtheory.cpp:96
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:379
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Calculate multiplicative inverse.
Definition nbtheory.h:166
CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Definition nbtheory.cpp:247
CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
Definition nbtheory.cpp:155
CRYPTOPP_DLL Integer CRYPTOPP_API MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
Definition nbtheory.cpp:470
CRYPTOPP_DLL bool CRYPTOPP_API IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
Definition nbtheory.cpp:60
CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision(const Integer &p, unsigned bound)
Tests whether a number is divisible by a small prime.
Definition nbtheory.cpp:71
CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Definition nbtheory.cpp:792
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
Definition nbtheory.h:143
CRYPTOPP_DLL Integer CRYPTOPP_API MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
Definition nbtheory.cpp:510
CRYPTOPP_DLL const word16 *CRYPTOPP_API GetPrimeTable(unsigned int &size)
The Small Prime table.
Definition nbtheory.cpp:53
CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest(const Integer &p)
Tests whether a number is divisible by a small prime.
Definition nbtheory.cpp:89
Integer LCM(const Integer &a, const Integer &b)
Calculate the least common multiple.
Definition nbtheory.h:157
CRYPTOPP_DLL Integer CRYPTOPP_API ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Extract a modular root.
Definition nbtheory.cpp:646