Crypto++
5.6.3
Free C++ class library of cryptographic schemes
|
Classes and functions for number theoretic operations. More...
Go to the source code of this file.
Classes | |
class | PrimeSelector |
Application callback to signal suitability of a cabdidate prime. More... | |
class | PrimeAndGenerator |
generator of prime numbers of special forms More... | |
Functions | |
const word16 * | GetPrimeTable (unsigned int &size) |
Integer | MaurerProvablePrime (RandomNumberGenerator &rng, unsigned int bits) |
Generates a provable prime. More... | |
Integer | MihailescuProvablePrime (RandomNumberGenerator &rng, unsigned int bits) |
Generates a provable prime. More... | |
bool | IsSmallPrime (const Integer &p) |
Tests whether a number is a small prime. More... | |
bool | TrialDivision (const Integer &p, unsigned bound) |
bool | SmallDivisorsTest (const Integer &p) |
bool | IsFermatProbablePrime (const Integer &n, const Integer &b) |
bool | IsLucasProbablePrime (const Integer &n) |
bool | IsStrongProbablePrime (const Integer &n, const Integer &b) |
bool | IsStrongLucasProbablePrime (const Integer &n) |
bool | RabinMillerTest (RandomNumberGenerator &rng, const Integer &w, unsigned int rounds) |
bool | IsPrime (const Integer &p) |
Verifies a prime number. More... | |
bool | VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1) |
Verifies a prime number. More... | |
bool | FirstPrime (Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector) |
Finds a random prime of special form. More... | |
unsigned int | PrimeSearchInterval (const Integer &max) |
AlgorithmParameters | MakeParametersForTwoPrimesOfEqualSize (unsigned int productBitLength) |
Integer | GCD (const Integer &a, const Integer &b) |
bool | RelativelyPrime (const Integer &a, const Integer &b) |
Integer | LCM (const Integer &a, const Integer &b) |
Integer | EuclideanMultiplicativeInverse (const Integer &a, const Integer &b) |
Integer | CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u) |
int | Jacobi (const Integer &a, const Integer &b) |
Integer | Lucas (const Integer &e, const Integer &p, const Integer &n) |
Integer | InverseLucas (const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u) |
Integer | ModularExponentiation (const Integer &a, const Integer &e, const Integer &m) |
Integer | ModularSquareRoot (const Integer &a, const Integer &p) |
Integer | ModularRoot (const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u) |
bool | SolveModularQuadraticEquation (Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p) |
unsigned int | DiscreteLogWorkFactor (unsigned int bitlength) |
unsigned int | FactoringWorkFactor (unsigned int bitlength) |
Classes and functions for number theoretic operations.
Definition in file nbtheory.h.
Integer MaurerProvablePrime | ( | RandomNumberGenerator & | rng, |
unsigned int | bits | ||
) |
Generates a provable prime.
rng | a RandomNumberGenerator to produce keying material |
bits | the number of bits in the prime number |
Definition at line 512 of file nbtheory.cpp.
References Integer::ANY, Integer::BitCount(), RandomNumberGenerator::GenerateWord32(), Integer::GetBit(), IsPrime(), IsSmallPrime(), Integer::Power2(), Integer::PRIME, Integer::Randomize(), Integer::Squared(), STDMIN(), TrialDivision(), Integer::Two(), and Integer::Zero().
Integer MihailescuProvablePrime | ( | RandomNumberGenerator & | rng, |
unsigned int | bits | ||
) |
Generates a provable prime.
rng | a RandomNumberGenerator to produce keying material |
bits | the number of bits in the prime number |
Mihailescu's methods performs a search using algorithmic progressions.
Definition at line 472 of file nbtheory.cpp.
References Integer::ANY, RandomNumberGenerator::GenerateWord32(), Integer::Power2(), Integer::PRIME, Integer::Randomize(), and STDMIN().
bool IsSmallPrime | ( | const Integer & | p | ) |
Tests whether a number is a small prime.
p | a candidate prime to test |
Internally, the library maintains a table fo the first 32719 prime numbers in sorted order. IsSmallPrime() searches the table and returns true if p is in the table.
Definition at line 62 of file nbtheory.cpp.
References Integer::ConvertToLong().
Referenced by IsPrime(), and MaurerProvablePrime().
bool TrialDivision | ( | const Integer & | p, |
unsigned | bound | ||
) |
TrialDivision() true if p is divisible by some prime less than bound. bound not be greater than the largest entry in the prime table, which is 32719.
Definition at line 73 of file nbtheory.cpp.
References Integer::GetBit(), Integer::IsSquare(), Integer::Randomize(), and Integer::Squared().
Referenced by MaurerProvablePrime().
bool IsPrime | ( | const Integer & | p | ) |
Verifies a prime number.
p | a candidate prime to test |
IsPrime() is suitable for testing candidate primes when creating them. Internally, IsPrime() utilizes SmallDivisorsTest(), IsStrongProbablePrime() and IsStrongLucasProbablePrime().
Definition at line 239 of file nbtheory.cpp.
References IsSmallPrime().
Referenced by FirstPrime(), MaurerProvablePrime(), and VerifyPrime().
bool VerifyPrime | ( | RandomNumberGenerator & | rng, |
const Integer & | p, | ||
unsigned int | level = 1 |
||
) |
Verifies a prime number.
rng | a RandomNumberGenerator for randomized testing |
p | a candidate prime to test |
level | the level of thoroughness of testing |
VerifyPrime() is suitable for testing candidate primes created by others. Internally, VerifyPrime() utilizes IsPrime() and one-round RabinMillerTest(). If the candiate passes and level is greater than 1, then 10 round RabinMillerTest() primality testing is performed.
Definition at line 249 of file nbtheory.cpp.
References Integer::BitCount(), IsPrime(), MakeParameters(), Integer::Power2(), and Integer::PRIME.
Referenced by DL_GroupParameters_EC< EC >::GenerateRandom(), XTR_DH::Validate(), InvertibleRabinFunction::Validate(), InvertibleESIGNFunction::Validate(), InvertibleRWFunction::Validate(), InvertibleLUCFunction::Validate(), InvertibleRSAFunction::Validate(), and DL_GroupParameters_DSA::ValidateGroup().
bool FirstPrime | ( | Integer & | p, |
const Integer & | max, | ||
const Integer & | equiv, | ||
const Integer & | mod, | ||
const PrimeSelector * | pSelector | ||
) |
Finds a random prime of special form.
p | an Integer reference to receive the prime |
max | the maximum value |
equiv | the equivalence class based on the parameter mod |
mod | the modulus used to reduce the equivalence class |
pSelector | pointer to a PrimeSelector function for the application to signal suitability |
FirstPrime() uses a fast sieve to find the first probable prime in {x | p<=x<=max and xmod==equiv}
Definition at line 381 of file nbtheory.cpp.
References Integer::ConvertToLong(), IsPrime(), and Integer::One().
Referenced by KDF2_RNG::GenerateBlock().