Crypto++  5.6.3
Free C++ class library of cryptographic schemes
Classes | Functions
nbtheory.h File Reference

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)
 

Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

Function Documentation

Integer MaurerProvablePrime ( RandomNumberGenerator rng,
unsigned int  bits 
)

Generates a provable prime.

Parameters
rnga RandomNumberGenerator to produce keying material
bitsthe number of bits in the prime number
Returns
Integer() meeting Maurer's tests for primality

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.

Parameters
rnga RandomNumberGenerator to produce keying material
bitsthe number of bits in the prime number
Returns
Integer() meeting Mihailescu's tests for primality

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.

Parameters
pa candidate prime to test
Returns
true if p is a small prime, false otherwise

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 
)
Returns
true if p is divisible by some prime less than 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.

Parameters
pa candidate prime to test
Returns
true if p is a probable prime, false otherwise

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.

Parameters
rnga RandomNumberGenerator for randomized testing
pa candidate prime to test
levelthe level of thoroughness of testing
Returns
true if p is a strong probable prime, false otherwise

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.

Parameters
pan Integer reference to receive the prime
maxthe maximum value
equivthe equivalence class based on the parameter mod
modthe modulus used to reduce the equivalence class
pSelectorpointer to a PrimeSelector function for the application to signal suitability
Returns
true if and only if FirstPrime() finds a prime and returns the prime through p. If FirstPrime() returns false, then no such prime exists and the value of p is undefined

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().