nbtheory.cpp File Reference

#include "pch.h"
#include "nbtheory.h"
#include "integer.h"
#include "modarith.h"
#include "algparam.h"
#include "smartptr.h"
#include "misc.h"
#include <math.h>
#include <vector>

Include dependency graph for nbtheory.cpp:

Go to the source code of this file.

Classes
struct	NewPrimeTable
struct	NewLastSmallPrimeSquared
class	PrimeSieve

Functions
const word16 *	GetPrimeTable (unsigned int &size)
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	IsStrongProbablePrime (const Integer &n, const Integer &b)
bool	RabinMillerTest (RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
bool	IsLucasProbablePrime (const Integer &n)
bool	IsStrongLucasProbablePrime (const Integer &n)
bool	IsPrime (const Integer &p)
	Verifies a prime number. More...
bool	VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level)
	Verifies a prime number. More...
unsigned int	PrimeSearchInterval (const Integer &max)
AlgorithmParameters	MakeParametersForTwoPrimesOfEqualSize (unsigned int productBitLength)
bool	FirstPrime (Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
	Finds a random prime of special form. More...
Integer	MihailescuProvablePrime (RandomNumberGenerator &rng, unsigned int pbits)
	Generates a provable prime. More...
Integer	MaurerProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
	Generates a provable prime. More...
Integer	CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
Integer	ModularSquareRoot (const Integer &a, const Integer &p)
bool	SolveModularQuadraticEquation (Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
Integer	ModularRoot (const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Integer	ModularRoot (const Integer &a, const Integer &e, const Integer &p, const Integer &q)
int	Jacobi (const Integer &aIn, const Integer &bIn)
Integer	Lucas (const Integer &e, const Integer &pIn, const Integer &n)
Integer	InverseLucas (const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
unsigned int	FactoringWorkFactor (unsigned int n)
unsigned int	DiscreteLogWorkFactor (unsigned int n)

Variables
const word	s_lastSmallPrime = 32719

Function Documentation

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

unsigned int DiscreteLogWorkFactor

(

unsigned int

n

)

Definition at line 1029 of file nbtheory.cpp.

Here is the caller graph for this function:

unsigned int FactoringWorkFactor

(

unsigned int

n

)

Definition at line 1021 of file nbtheory.cpp.

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

const word16* GetPrimeTable

(

unsigned int &

size

)

Definition at line 55 of file nbtheory.cpp.

Here is the caller graph for this function:

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

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

Definition at line 98 of file nbtheory.cpp.

Here is the call graph for this function:

bool IsLucasProbablePrime

(

const Integer &

n

)

Definition at line 157 of file nbtheory.cpp.

Here is the call graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

int Jacobi	(	const Integer &	aIn,
		const Integer &	bIn
	)

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 Lucas	(	const Integer &	e,
		const Integer &	pIn,
		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:

AlgorithmParameters 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:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Integer ModularRoot	(	const Integer &	a,
		const Integer &	e,
		const Integer &	p,
		const Integer &	q
	)

Definition at line 663 of file nbtheory.cpp.

Here is the call graph for this function:

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

unsigned int 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:

bool RabinMillerTest	(	RandomNumberGenerator &	rng,
		const Integer &	n,
		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 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:

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

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.

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

const word s_lastSmallPrime = 32719

Definition at line 23 of file nbtheory.cpp.