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

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

Include dependency graph for nbtheory.h:

This graph shows which files directly or indirectly include 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)

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)

CRYPTOPP_DLL bool CRYPTOPP_API	SmallDivisorsTest (const Integer &p)

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

CRYPTOPP_DLL bool CRYPTOPP_API	IsLucasProbablePrime (const Integer &n)

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

CRYPTOPP_DLL bool CRYPTOPP_API	IsStrongLucasProbablePrime (const Integer &n)

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

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

CRYPTOPP_DLL bool CRYPTOPP_API	VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
	Verifies a prime number. 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)

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

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

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

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

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

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

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

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

CRYPTOPP_DLL Integer CRYPTOPP_API	ModularRoot (const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)

CRYPTOPP_DLL bool CRYPTOPP_API	SolveModularQuadraticEquation (Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)

CRYPTOPP_DLL unsigned int CRYPTOPP_API	DiscreteLogWorkFactor (unsigned int bitlength)

CRYPTOPP_DLL unsigned int CRYPTOPP_API	FactoringWorkFactor (unsigned int bitlength)

Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

Function Documentation

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

Definition at line 555 of file nbtheory.cpp.

Here is the caller graph for this function:

CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor ( unsigned int bitlength )

Definition at line 1029 of file nbtheory.cpp.

Here is the caller graph for this function:

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

inline

Definition at line 111 of file nbtheory.h.

Here is the call graph for this function:

Here is the caller graph for this function:

CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor ( unsigned int bitlength )

Definition at line 1021 of file nbtheory.cpp.

Here is the caller graph for this function:

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

inline

Definition at line 105 of file nbtheory.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 55 of file nbtheory.cpp.

Here is the caller graph for this function:

CRYPTOPP_DLL Integer CRYPTOPP_API InverseLucas	(	const Integer &	e,
		const Integer &	m,
		const Integer &	p,
		const Integer &	q,
		const Integer &	u
	)

Definition at line 1000 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 98 of file nbtheory.cpp.

Here is the call graph for this function:

CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime ( const Integer & n )

Definition at line 157 of file nbtheory.cpp.

Here is the call graph for this function:

CRYPTOPP_DLL bool CRYPTOPP_API IsPrime ( const Integer & p )

Verifies a prime number.

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Here is the call graph for this function:

Here is the caller graph for this function:

CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime ( const Integer & n )

Definition at line 184 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 107 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 787 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

inline

Definition at line 109 of file nbtheory.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 814 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

CRYPTOPP_DLL AlgorithmParameters CRYPTOPP_API MakeParametersForTwoPrimesOfEqualSize ( unsigned int productBitLength )

Definition at line 267 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Generates a provable prime.

Parameters

rng	a RandomNumberGenerator to produce keying material
bits	the number of bits in the prime number

Returns: Integer() meeting Maurer's tests for primality

Definition at line 512 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Generates a provable prime.

Parameters

rng	a RandomNumberGenerator to produce keying 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 472 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Integer ModularExponentiation	(	const Integer &	a,
		const Integer &	e,
		const Integer &	m
	)

inline

Definition at line 126 of file nbtheory.h.

Here is the call graph for this function:

Here is the caller graph for this function:

CRYPTOPP_DLL Integer CRYPTOPP_API ModularRoot	(	const Integer &	a,
		const Integer &	dp,
		const Integer &	dq,
		const Integer &	p,
		const Integer &	q,
		const Integer &	u
	)

Definition at line 648 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 574 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

CRYPTOPP_DLL unsigned int CRYPTOPP_API PrimeSearchInterval ( const Integer & max )

Definition at line 257 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 140 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

inline

Definition at line 107 of file nbtheory.h.

Here is the call graph for this function:

Here is the caller graph for this function:

CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest ( const Integer & p )

Definition at line 91 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

CRYPTOPP_DLL bool CRYPTOPP_API SolveModularQuadraticEquation	(	Integer &	r1,
		Integer &	r2,
		const Integer &	a,
		const Integer &	b,
		const Integer &	c,
		const Integer &	p
	)

Definition at line 623 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Verifies a prime number.

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

Definition at line 249 of file nbtheory.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Classes

Functions

Detailed Description

Function Documentation