Crypto++  8.2
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

CRYPTOPP_DLL const word16 *CRYPTOPP_API GetPrimeTable (unsigned int &size)
 The Small Prime table. More...
 
CRYPTOPP_DLL Integer CRYPTOPP_API MaurerProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
 Generates a provable prime. More...
 
CRYPTOPP_DLL Integer CRYPTOPP_API MihailescuProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
 Generates a provable prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API IsSmallPrime (const Integer &p)
 Tests whether a number is a small prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision (const Integer &p, unsigned bound)
 Tests whether a number is divisible by a small prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest (const Integer &p)
 Tests whether a number is divisible by a small prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API IsFermatProbablePrime (const Integer &n, const Integer &b)
 Determine if a number is probably prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime (const Integer &n)
 Determine if a number is probably prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongProbablePrime (const Integer &n, const Integer &b)
 Determine if a number is probably prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime (const Integer &n)
 Determine if a number is probably prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest (RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
 Determine if a number is probably prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API IsPrime (const Integer &p)
 Verifies a number is probably prime. More...
 
CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
 Verifies a number is probably prime. More...
 
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. More...
 
CRYPTOPP_DLL unsigned int CRYPTOPP_API PrimeSearchInterval (const Integer &max)
 
CRYPTOPP_DLL AlgorithmParameters CRYPTOPP_API MakeParametersForTwoPrimesOfEqualSize (unsigned int productBitLength)
 
Integer GCD (const Integer &a, const Integer &b)
 Calculate the greatest common divisor. More...
 
bool RelativelyPrime (const Integer &a, const Integer &b)
 Determine relative primality. More...
 
Integer LCM (const Integer &a, const Integer &b)
 Calculate the least common multiple. More...
 
Integer EuclideanMultiplicativeInverse (const Integer &a, const Integer &b)
 Calculate multiplicative inverse. More...
 
CRYPTOPP_DLL Integer CRYPTOPP_API CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
 Chinese Remainder Theorem. More...
 
CRYPTOPP_DLL int CRYPTOPP_API Jacobi (const Integer &a, const Integer &b)
 Calculate the Jacobi symbol. More...
 
CRYPTOPP_DLL Integer CRYPTOPP_API Lucas (const Integer &e, const Integer &p, const Integer &n)
 Calculate the Lucas value. More...
 
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. More...
 
Integer ModularMultiplication (const Integer &x, const Integer &y, const Integer &m)
 Modular multiplication. More...
 
Integer ModularExponentiation (const Integer &x, const Integer &e, const Integer &m)
 Modular exponentiation. More...
 
CRYPTOPP_DLL Integer CRYPTOPP_API ModularSquareRoot (const Integer &a, const Integer &p)
 Extract a modular square root. More...
 
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. More...
 
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. More...
 
CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor (unsigned int bitlength)
 Estimate work factor. More...
 
CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor (unsigned int bitlength)
 Estimate work factor. More...
 

Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

Function Documentation

◆ GetPrimeTable()

CRYPTOPP_DLL const word16* CRYPTOPP_API GetPrimeTable ( unsigned int &  size)

The Small Prime table.

GetPrimeTable obtains pointer to small prime table and provides the size of the table.

Definition at line 53 of file nbtheory.cpp.

◆ MaurerProvablePrime()

CRYPTOPP_DLL Integer CRYPTOPP_API MaurerProvablePrime ( RandomNumberGenerator rng,
unsigned int  bits 
)

Generates a provable prime.

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

Definition at line 510 of file nbtheory.cpp.

◆ MihailescuProvablePrime()

CRYPTOPP_DLL Integer CRYPTOPP_API MihailescuProvablePrime ( RandomNumberGenerator rng,
unsigned int  bits 
)

Generates a provable prime.

Parameters
rnga RandomNumberGenerator to produce random 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 470 of file nbtheory.cpp.

◆ IsSmallPrime()

CRYPTOPP_DLL bool CRYPTOPP_API 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 of the first 32719 prime numbers in sorted order. IsSmallPrime searches the table and returns true if p is in the table.

Definition at line 60 of file nbtheory.cpp.

◆ TrialDivision()

CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision ( const Integer p,
unsigned  bound 
)

Tests whether a number is divisible by a small prime.

Returns
true if p is divisible by some prime less than bound.

TrialDivision() returns true if p is divisible by some prime less than bound. bound should not be greater than the largest entry in the prime table, which is 32719.

Definition at line 71 of file nbtheory.cpp.

◆ SmallDivisorsTest()

CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest ( const Integer p)

Tests whether a number is divisible by a small prime.

Returns
true if p is NOT divisible by small primes.

SmallDivisorsTest() returns true if p is NOT divisible by some prime less than 32719.

Definition at line 89 of file nbtheory.cpp.

◆ IsFermatProbablePrime()

CRYPTOPP_DLL bool CRYPTOPP_API IsFermatProbablePrime ( const Integer n,
const Integer b 
)

Determine if a number is probably prime.

Parameters
nthe number to test
bthe base to exponentiate
Returns
true if the number n is probably prime, false otherwise.

IsFermatProbablePrime raises b to the n-1 power and checks if the result is congruent to 1 modulo n.

These is no reason to use IsFermatProbablePrime, use IsStrongProbablePrime or IsStrongLucasProbablePrime instead.

See also
IsStrongProbablePrime, IsStrongLucasProbablePrime

Definition at line 96 of file nbtheory.cpp.

◆ IsLucasProbablePrime()

CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime ( const Integer n)

Determine if a number is probably prime.

Parameters
nthe number to test
Returns
true if the number n is probably prime, false otherwise.

These is no reason to use IsLucasProbablePrime, use IsStrongProbablePrime or IsStrongLucasProbablePrime instead.

See also
IsStrongProbablePrime, IsStrongLucasProbablePrime

Definition at line 155 of file nbtheory.cpp.

◆ IsStrongProbablePrime()

CRYPTOPP_DLL bool CRYPTOPP_API IsStrongProbablePrime ( const Integer n,
const Integer b 
)

Determine if a number is probably prime.

Parameters
nthe number to test
bthe base to exponentiate
Returns
true if the number n is probably prime, false otherwise.

Definition at line 105 of file nbtheory.cpp.

◆ IsStrongLucasProbablePrime()

CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime ( const Integer n)

Determine if a number is probably prime.

Parameters
nthe number to test
Returns
true if the number n is probably prime, false otherwise.

Definition at line 182 of file nbtheory.cpp.

◆ RabinMillerTest()

CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest ( RandomNumberGenerator rng,
const Integer n,
unsigned int  rounds 
)

Determine if a number is probably prime.

Parameters
rnga RandomNumberGenerator to produce random material
nthe number to test
roundsthe number of tests to perform

This is the Rabin-Miller primality test, i.e. repeating the strong probable prime test for several rounds with random bases

See also
Trial divisions before Miller-Rabin checks? on Crypto Stack Exchange

Definition at line 138 of file nbtheory.cpp.

◆ IsPrime()

CRYPTOPP_DLL bool CRYPTOPP_API IsPrime ( const Integer p)

Verifies a number is probably prime.

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 237 of file nbtheory.cpp.

◆ VerifyPrime()

CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime ( RandomNumberGenerator rng,
const Integer p,
unsigned int  level = 1 
)

Verifies a number is probably prime.

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 247 of file nbtheory.cpp.

◆ FirstPrime()

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.

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 379 of file nbtheory.cpp.

◆ GCD()

Integer GCD ( const Integer a,
const Integer b 
)
inline

Calculate the greatest common divisor.

Parameters
athe first term
bthe second term
Returns
the greatest common divisor if one exists, 0 otherwise.

Definition at line 143 of file nbtheory.h.

◆ RelativelyPrime()

bool RelativelyPrime ( const Integer a,
const Integer b 
)
inline

Determine relative primality.

Parameters
athe first term
bthe second term
Returns
true if a and b are relatively prime, false otherwise.

Definition at line 150 of file nbtheory.h.

◆ LCM()

Integer LCM ( const Integer a,
const Integer b 
)
inline

Calculate the least common multiple.

Parameters
athe first term
bthe second term
Returns
the least common multiple of a and b.

Definition at line 157 of file nbtheory.h.

◆ EuclideanMultiplicativeInverse()

Integer EuclideanMultiplicativeInverse ( const Integer a,
const Integer b 
)
inline

Calculate multiplicative inverse.

Parameters
athe number to test
bthe modulus
Returns
an Integer (a ^ -1) % n or 0 if none exists.

EuclideanMultiplicativeInverse returns the multiplicative inverse of the Integer *a modulo the Integer b. If no Integer exists then Integer 0 is returned.

Definition at line 166 of file nbtheory.h.

◆ CRT()

CRYPTOPP_DLL Integer CRYPTOPP_API CRT ( const Integer xp,
const Integer p,
const Integer xq,
const Integer q,
const Integer u 
)

Chinese Remainder Theorem.

Parameters
xpthe first number, mod p
pthe first prime modulus
xqthe second number, mod q
qthe second prime modulus
uinverse of p mod q
Returns
the CRT value of the parameters

CRT uses the Chinese Remainder Theorem to calculate x given x mod p and x mod q, and u the inverse of p mod q.

Definition at line 553 of file nbtheory.cpp.

◆ Jacobi()

CRYPTOPP_DLL int CRYPTOPP_API Jacobi ( const Integer a,
const Integer b 
)

Calculate the Jacobi symbol.

Parameters
athe first term
bthe second term
Returns
the the Jacobi symbol.

Jacobi symbols are calculated using the following rules:

  1. if b is prime, then Jacobi(a, b), then return 0
  2. if ab==0 AND a is quadratic residue mod b, then return 1
  3. return -1 otherwise

Refer to a number theory book for what Jacobi symbol means when b is not prime.

Definition at line 792 of file nbtheory.cpp.

◆ Lucas()

CRYPTOPP_DLL Integer CRYPTOPP_API Lucas ( const Integer e,
const Integer p,
const Integer n 
)

Calculate the Lucas value.

Returns
the Lucas value

Lucas() calculates the Lucas function V_e(p, 1) mod n.

Definition at line 819 of file nbtheory.cpp.

◆ InverseLucas()

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.

Returns
the inverse Lucas value

InverseLucas() calculates x such that m==Lucas(e, x, p*q), p q primes, u is inverse of p mod q.

Definition at line 1005 of file nbtheory.cpp.

◆ ModularMultiplication()

Integer ModularMultiplication ( const Integer x,
const Integer y,
const Integer m 
)
inline

Modular multiplication.

Parameters
xthe first term
ythe second term
mthe modulus
Returns
an Integer (x * y) % m.

Definition at line 208 of file nbtheory.h.

◆ ModularExponentiation()

Integer ModularExponentiation ( const Integer x,
const Integer e,
const Integer m 
)
inline

Modular exponentiation.

Parameters
xthe base
ethe exponent
mthe modulus
Returns
an Integer (a ^ b) % m.

Definition at line 216 of file nbtheory.h.

◆ ModularSquareRoot()

CRYPTOPP_DLL Integer CRYPTOPP_API ModularSquareRoot ( const Integer a,
const Integer p 
)

Extract a modular square root.

Parameters
athe number to extract square root
pthe prime modulus
Returns
the modular square root if it exists

ModularSquareRoot returns x such that x*xp == a, p prime

Definition at line 572 of file nbtheory.cpp.

◆ ModularRoot()

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.

Returns
a modular root if it exists

ModularRoot returns x such that a==ModularExponentiation(x, e, p*q), p q primes, and e relatively prime to (p-1)*(q-1), dp=d%(p-1), dq=d%(q-1), (d is inverse of e mod (p-1)*(q-1)) and u=inverse of p mod q.

Definition at line 646 of file nbtheory.cpp.

◆ SolveModularQuadraticEquation()

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.

Parameters
r1the first residue
r2the second residue
athe first coefficient
bthe second coefficient
cthe third constant
pthe prime modulus
Returns
true if solutions exist

SolveModularQuadraticEquation() finds r1 and r2 such that ax^2 + bx + c == 0 (mod p) for x in {r1, r2}, p prime.

Definition at line 621 of file nbtheory.cpp.

◆ DiscreteLogWorkFactor()

CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor ( unsigned int  bitlength)

Estimate work factor.

Parameters
bitlengththe size of the number, in bits
Returns
the estimated work factor, in operations

DiscreteLogWorkFactor returns log base 2 of estimated number of operations to calculate discrete log or factor a number.

Definition at line 1045 of file nbtheory.cpp.

◆ FactoringWorkFactor()

CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor ( unsigned int  bitlength)

Estimate work factor.

Parameters
bitlengththe size of the number, in bits
Returns
the estimated work factor, in operations

FactoringWorkFactor returns log base 2 of estimated number of operations to calculate discrete log or factor a number.

Definition at line 1037 of file nbtheory.cpp.