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
const word16 *	GetPrimeTable (unsigned int &size)
Integer	MaurerProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
	Generates a provable prime. More...
Integer	MihailescuProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
	Generates a provable prime. More...
bool	IsSmallPrime (const Integer &p)
	Tests whether a number is a small prime. More...
bool	TrialDivision (const Integer &p, unsigned bound)
bool	SmallDivisorsTest (const Integer &p)
bool	IsFermatProbablePrime (const Integer &n, const Integer &b)
bool	IsLucasProbablePrime (const Integer &n)
bool	IsStrongProbablePrime (const Integer &n, const Integer &b)
bool	IsStrongLucasProbablePrime (const Integer &n)
bool	RabinMillerTest (RandomNumberGenerator &rng, const Integer &w, unsigned int rounds)
bool	IsPrime (const Integer &p)
	Verifies a prime number. More...
bool	VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
	Verifies a prime number. More...
bool	FirstPrime (Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
	Finds a random prime of special form. More...
unsigned int	PrimeSearchInterval (const Integer &max)
AlgorithmParameters	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)
Integer	CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
int	Jacobi (const Integer &a, const Integer &b)
Integer	Lucas (const Integer &e, const Integer &p, const Integer &n)
Integer	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)
Integer	ModularSquareRoot (const Integer &a, const Integer &p)
Integer	ModularRoot (const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
bool	SolveModularQuadraticEquation (Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
unsigned int	DiscreteLogWorkFactor (unsigned int bitlength)
unsigned int	FactoringWorkFactor (unsigned int bitlength)

Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

Function Documentation

MaurerProvablePrime()

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

MihailescuProvablePrime()

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

IsSmallPrime()

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

TrialDivision()

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

IsPrime()

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

VerifyPrime()

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

FirstPrime()

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}

Definition at line 381 of file nbtheory.cpp.