Crypto++ 8.9
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 candidate prime. More...
 
class  PrimeAndGenerator
 Generator of prime numbers of special forms. More...
 

Functions

CRYPTOPP_DLL const word16GetPrimeTable (unsigned int &size)
 The Small Prime table.
 
CRYPTOPP_DLL Integer MaurerProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
 Generates a provable prime.
 
CRYPTOPP_DLL Integer MihailescuProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
 Generates a provable prime.
 
CRYPTOPP_DLL bool IsSmallPrime (const Integer &p)
 Tests whether a number is a small prime.
 
CRYPTOPP_DLL bool TrialDivision (const Integer &p, unsigned bound)
 Tests whether a number is divisible by a small prime.
 
CRYPTOPP_DLL bool SmallDivisorsTest (const Integer &p)
 Tests whether a number is divisible by a small prime.
 
CRYPTOPP_DLL bool IsFermatProbablePrime (const Integer &n, const Integer &b)
 Determine if a number is probably prime.
 
CRYPTOPP_DLL bool IsLucasProbablePrime (const Integer &n)
 Determine if a number is probably prime.
 
CRYPTOPP_DLL bool IsStrongProbablePrime (const Integer &n, const Integer &b)
 Determine if a number is probably prime.
 
CRYPTOPP_DLL bool IsStrongLucasProbablePrime (const Integer &n)
 Determine if a number is probably prime.
 
CRYPTOPP_DLL bool RabinMillerTest (RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
 Determine if a number is probably prime.
 
CRYPTOPP_DLL bool IsPrime (const Integer &p)
 Verifies a number is probably prime.
 
CRYPTOPP_DLL bool VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
 Verifies a number is probably prime.
 
CRYPTOPP_DLL bool FirstPrime (Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
 Finds a random prime of special form.
 
CRYPTOPP_DLL unsigned int PrimeSearchInterval (const Integer &max)
 
CRYPTOPP_DLL AlgorithmParameters MakeParametersForTwoPrimesOfEqualSize (unsigned int productBitLength)
 
Integer GCD (const Integer &a, const Integer &b)
 Calculate the greatest common divisor.
 
bool RelativelyPrime (const Integer &a, const Integer &b)
 Determine relative primality.
 
Integer LCM (const Integer &a, const Integer &b)
 Calculate the least common multiple.
 
Integer EuclideanMultiplicativeInverse (const Integer &a, const Integer &b)
 Calculate multiplicative inverse.
 
CRYPTOPP_DLL Integer CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
 Chinese Remainder Theorem.
 
CRYPTOPP_DLL int Jacobi (const Integer &a, const Integer &b)
 Calculate the Jacobi symbol.
 
CRYPTOPP_DLL Integer Lucas (const Integer &e, const Integer &p, const Integer &n)
 Calculate the Lucas value.
 
CRYPTOPP_DLL Integer InverseLucas (const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
 Calculate the inverse Lucas value.
 
Integer ModularMultiplication (const Integer &x, const Integer &y, const Integer &m)
 Modular multiplication.
 
Integer ModularExponentiation (const Integer &x, const Integer &e, const Integer &m)
 Modular exponentiation.
 
CRYPTOPP_DLL Integer ModularSquareRoot (const Integer &a, const Integer &p)
 Extract a modular square root.
 
CRYPTOPP_DLL Integer ModularRoot (const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
 Extract a modular root.
 
CRYPTOPP_DLL bool SolveModularQuadraticEquation (Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
 Solve a Modular Quadratic Equation.
 
CRYPTOPP_DLL unsigned int DiscreteLogWorkFactor (unsigned int bitlength)
 Estimate work factor.
 
CRYPTOPP_DLL unsigned int FactoringWorkFactor (unsigned int bitlength)
 Estimate work factor.
 

Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

Function Documentation

◆ GetPrimeTable()

CRYPTOPP_DLL const word16 * GetPrimeTable ( unsigned int & size)

The Small Prime table.

Parameters
sizenumber of elements in the table
Returns
prime table with /p size elements

GetPrimeTable() obtains pointer to small prime table and provides the size of the table. /p size is an out parameter.

◆ MaurerProvablePrime()

CRYPTOPP_DLL Integer 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

◆ MihailescuProvablePrime()

CRYPTOPP_DLL Integer 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.

◆ IsSmallPrime()

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

◆ TrialDivision()

CRYPTOPP_DLL bool 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.

◆ SmallDivisorsTest()

CRYPTOPP_DLL bool 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.

◆ IsFermatProbablePrime()

CRYPTOPP_DLL bool 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

◆ IsLucasProbablePrime()

CRYPTOPP_DLL bool 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

◆ IsStrongProbablePrime()

CRYPTOPP_DLL bool 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.

◆ IsStrongLucasProbablePrime()

CRYPTOPP_DLL bool 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.

◆ RabinMillerTest()

CRYPTOPP_DLL bool 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

◆ IsPrime()

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

◆ VerifyPrime()

CRYPTOPP_DLL bool 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 candidate passes and level is greater than 1, then 10 round RabinMillerTest() primality testing is performed.

◆ FirstPrime()

CRYPTOPP_DLL 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}

◆ 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 146 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 153 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 160 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 169 of file nbtheory.h.

◆ CRT()

CRYPTOPP_DLL Integer 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.

◆ Jacobi()

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

Calculate the Jacobi symbol.

Parameters
athe first term
bthe second term
Returns
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.

◆ Lucas()

CRYPTOPP_DLL Integer 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.

◆ InverseLucas()

CRYPTOPP_DLL Integer 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.

◆ 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 211 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 219 of file nbtheory.h.

◆ ModularSquareRoot()

CRYPTOPP_DLL Integer 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

◆ ModularRoot()

CRYPTOPP_DLL Integer 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.

◆ SolveModularQuadraticEquation()

CRYPTOPP_DLL bool 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.

◆ DiscreteLogWorkFactor()

CRYPTOPP_DLL unsigned int 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.

◆ FactoringWorkFactor()

CRYPTOPP_DLL unsigned int 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.