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

#include "cryptlib.h"
#include "integer.h"
#include "algparam.h"

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.

CRYPTOPP_DLL Integer CRYPTOPP_API	MaurerProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
	Generates a provable prime.

CRYPTOPP_DLL Integer CRYPTOPP_API	MihailescuProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
	Generates a provable prime.

CRYPTOPP_DLL bool CRYPTOPP_API	IsSmallPrime (const Integer &p)
	Tests whether a number is a small prime.

CRYPTOPP_DLL bool CRYPTOPP_API	TrialDivision (const Integer &p, unsigned bound)
	Tests whether a number is divisible by a small prime.

CRYPTOPP_DLL bool CRYPTOPP_API	SmallDivisorsTest (const Integer &p)
	Tests whether a number is divisible by a small prime.

CRYPTOPP_DLL bool CRYPTOPP_API	IsFermatProbablePrime (const Integer &n, const Integer &b)
	Determine if a number is probably prime.

CRYPTOPP_DLL bool CRYPTOPP_API	IsLucasProbablePrime (const Integer &n)
	Determine if a number is probably prime.

CRYPTOPP_DLL bool CRYPTOPP_API	IsStrongProbablePrime (const Integer &n, const Integer &b)
	Determine if a number is probably prime.

CRYPTOPP_DLL bool CRYPTOPP_API	IsStrongLucasProbablePrime (const Integer &n)
	Determine if a number is probably prime.

CRYPTOPP_DLL bool CRYPTOPP_API	RabinMillerTest (RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
	Determine if a number is probably prime.

CRYPTOPP_DLL bool CRYPTOPP_API	IsPrime (const Integer &p)
	Verifies a number is probably prime.

CRYPTOPP_DLL bool CRYPTOPP_API	VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
	Verifies a number is probably prime.

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.

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.

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 CRYPTOPP_API	CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
	Chinese Remainder Theorem.

CRYPTOPP_DLL int CRYPTOPP_API	Jacobi (const Integer &a, const Integer &b)
	Calculate the Jacobi symbol.

CRYPTOPP_DLL Integer CRYPTOPP_API	Lucas (const Integer &e, const Integer &p, const Integer &n)
	Calculate the Lucas value.

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.

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 CRYPTOPP_API	ModularSquareRoot (const Integer &a, const Integer &p)
	Extract a modular square root.

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.

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.

CRYPTOPP_DLL unsigned int CRYPTOPP_API	DiscreteLogWorkFactor (unsigned int bitlength)
	Estimate work factor.

CRYPTOPP_DLL unsigned int CRYPTOPP_API	FactoringWorkFactor (unsigned int bitlength)
	Estimate work factor.

Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

Function Documentation

◆ 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

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.

Definition at line 553 of file nbtheory.cpp.

◆ DiscreteLogWorkFactor()

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

Definition at line 1045 of file nbtheory.cpp.

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

◆ FactoringWorkFactor()

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

Definition at line 1037 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

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}

Definition at line 379 of file nbtheory.cpp.

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

◆ 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.

◆ 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.

◆ IsFermatProbablePrime()

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

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

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

Definition at line 155 of file nbtheory.cpp.

◆ IsPrime()

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

Definition at line 237 of file nbtheory.cpp.

◆ IsSmallPrime()

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

Definition at line 60 of file nbtheory.cpp.

◆ IsStrongLucasProbablePrime()

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

Definition at line 182 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

n	the number to test
b	the base to exponentiate

Returns: true if the number n is probably prime, false otherwise.

Definition at line 105 of file nbtheory.cpp.

◆ Jacobi()

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

Definition at line 792 of file nbtheory.cpp.

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

◆ 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.

◆ MakeParametersForTwoPrimesOfEqualSize()

CRYPTOPP_DLL AlgorithmParameters CRYPTOPP_API MakeParametersForTwoPrimesOfEqualSize ( unsigned int productBitLength )

Definition at line 265 of file nbtheory.cpp.

◆ MaurerProvablePrime()

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

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

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.

Definition at line 470 of file nbtheory.cpp.

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

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

◆ 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.

◆ ModularSquareRoot()

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

Definition at line 572 of file nbtheory.cpp.

◆ PrimeSearchInterval()

CRYPTOPP_DLL unsigned int CRYPTOPP_API PrimeSearchInterval ( const Integer & max )

Definition at line 255 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

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

Definition at line 138 of file nbtheory.cpp.

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

◆ 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.

◆ 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

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.

Definition at line 621 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.

◆ VerifyPrime()

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

Definition at line 247 of file nbtheory.cpp.

Classes

Functions

Detailed Description

Function Documentation

◆ CRT()

◆ DiscreteLogWorkFactor()

◆ EuclideanMultiplicativeInverse()

◆ FactoringWorkFactor()

◆ FirstPrime()

◆ GCD()

◆ GetPrimeTable()

◆ InverseLucas()

◆ IsFermatProbablePrime()

◆ IsLucasProbablePrime()

◆ IsPrime()

◆ IsSmallPrime()

◆ IsStrongLucasProbablePrime()

◆ IsStrongProbablePrime()

◆ Jacobi()

◆ LCM()

◆ Lucas()

◆ MakeParametersForTwoPrimesOfEqualSize()

◆ MaurerProvablePrime()

◆ MihailescuProvablePrime()

◆ ModularExponentiation()

◆ ModularMultiplication()

◆ ModularRoot()

◆ ModularSquareRoot()

◆ PrimeSearchInterval()

◆ RabinMillerTest()

◆ RelativelyPrime()

◆ SmallDivisorsTest()

◆ SolveModularQuadraticEquation()

◆ TrialDivision()

◆ VerifyPrime()