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.