Classes and functions for number theoretic operations. More...

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 *	GetPrimeTable (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

size	number 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

rng	a RandomNumberGenerator to produce random material
bits	the 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

rng	a RandomNumberGenerator to produce random material
bits	the 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

p	a 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

n	the number to test
b	the 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

n	the 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

n	the number to test
b	the 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

n	the 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

rng	a RandomNumberGenerator to produce random material
n	the number to test
rounds	the 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

p	a 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

rng	a RandomNumberGenerator for randomized testing
p	a candidate prime to test
level	the 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

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

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

a	the first term
b	the 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

a	the first term
b	the 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

a	the first term
b	the 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

a	the number to test
b	the 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

xp	the first number, mod p
p	the first prime modulus
xq	the second number, mod q
q	the second prime modulus
u	inverse 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

a	the first term
b	the second term

Returns: the Jacobi symbol.

Jacobi symbols are calculated using the following rules:

if b is prime, then Jacobi(a, b), then return 0
if ab==0 AND a is quadratic residue mod b, then return 1
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

x	the first term
y	the second term
m	the 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

x	the base
e	the exponent
m	the 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

a	the number to extract square root
p	the 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

r1	the first residue
r2	the second residue
a	the first coefficient
b	the second coefficient
c	the third constant
p	the 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

bitlength the 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

bitlength the 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.

Classes

Functions

Detailed Description

Function Documentation

◆ GetPrimeTable()

◆ MaurerProvablePrime()

◆ MihailescuProvablePrime()

◆ IsSmallPrime()

◆ TrialDivision()

◆ SmallDivisorsTest()

◆ IsFermatProbablePrime()

◆ IsLucasProbablePrime()

◆ IsStrongProbablePrime()

◆ IsStrongLucasProbablePrime()

◆ RabinMillerTest()

◆ IsPrime()

◆ VerifyPrime()

◆ FirstPrime()

◆ GCD()

◆ RelativelyPrime()

◆ LCM()

◆ EuclideanMultiplicativeInverse()

◆ CRT()

◆ Jacobi()

◆ Lucas()

◆ InverseLucas()

◆ ModularMultiplication()

◆ ModularExponentiation()

◆ ModularSquareRoot()

◆ ModularRoot()

◆ SolveModularQuadraticEquation()

◆ DiscreteLogWorkFactor()

◆ FactoringWorkFactor()