Crypto++ 8.1 Free C++ class library of cryptographic schemes

Classes | Functions
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)
| The Small Prime table. More...
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)
| Tests whether a number is divisible by a small prime. More...
bool | SmallDivisorsTest (const Integer &p)
| Tests whether a number is divisible by a small prime. More...
bool | IsFermatProbablePrime (const Integer &n, const Integer &b)
| Determine if a number is probably prime. More...
bool | IsLucasProbablePrime (const Integer &n)
| Determine if a number is probably prime. More...
bool | IsStrongProbablePrime (const Integer &n, const Integer &b)
| Determine if a number is probably prime. More...
bool | IsStrongLucasProbablePrime (const Integer &n)
| Determine if a number is probably prime. More...
bool | RabinMillerTest (RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
| Determine if a number is probably prime. More...
bool | IsPrime (const Integer &p)
| Verifies a number is probably prime. More...
bool | VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
| Verifies a number is probably prime. 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)
| Calculate the greatest common divisor. More...
bool | RelativelyPrime (const Integer &a, const Integer &b)
| Determine relative primality. More...
Integer | LCM (const Integer &a, const Integer &b)
| Calculate the least common multiple. More...
Integer | EuclideanMultiplicativeInverse (const Integer &a, const Integer &b)
| Calculate multiplicative inverse. More...
Integer | CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
| Chinese Remainder Theorem. More...
int | Jacobi (const Integer &a, const Integer &b)
| Calculate the Jacobi symbol. More...
Integer | Lucas (const Integer &e, const Integer &p, const Integer &n)
| Calculate the Lucas value. More...
Integer | InverseLucas (const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
| Calculate the inverse Lucas value. More...
Integer | ModularMultiplication (const Integer &x, const Integer &y, const Integer &m)
| Modular multiplication. More...
Integer | ModularExponentiation (const Integer &x, const Integer &e, const Integer &m)
| Modular exponentiation. More...
Integer | ModularSquareRoot (const Integer &a, const Integer &p)
| Extract a modular square root. More...
Integer | ModularRoot (const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
| Extract a modular root. More...
bool | SolveModularQuadraticEquation (Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
| Solve a Modular Quadratic Equation. More...
unsigned int | DiscreteLogWorkFactor (unsigned int bitlength)
| Estimate work factor. More...
unsigned int | FactoringWorkFactor (unsigned int bitlength)
| Estimate work factor. More...

## Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

## Function Documentation

## ◆ GetPrimeTable()

const word16* 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.

## ◆ MaurerProvablePrime()

Integer 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()

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

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

## ◆ TrialDivision()

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

## ◆ SmallDivisorsTest()

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

## ◆ IsFermatProbablePrime()

bool 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()

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

## ◆ IsStrongProbablePrime()

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

## ◆ IsStrongLucasProbablePrime()

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

## ◆ RabinMillerTest()

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

## ◆ IsPrime()

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

## ◆ VerifyPrime()

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

Definition at line 247 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 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 142 of file nbtheory.h.

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

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

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

## ◆ CRT()

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

## ◆ Jacobi()

int Jacobi | ( | const Integer & | a,
|  | const Integer & | b
| ) |  |

Calculate the Jacobi symbol.

Parameters

  a | the first term
  b | the second term

Returns
  the the Jacobi symbol.

Jacobi symbols are calculated using the following rules:

1. if `b` is prime, then `Jacobi(a, b)`, then return 0
2. if `ab`==0 AND `a` is quadratic residue `mod b`, then return 1
3. return -1 otherwise

Refer to a number theory book for what Jacobi symbol means when `b` is not prime.

Definition at line 785 of file nbtheory.cpp.

## ◆ Lucas()

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

## ◆ InverseLucas()

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

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

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

## ◆ ModularSquareRoot()

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

## ◆ ModularRoot()

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

## ◆ SolveModularQuadraticEquation()

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

## ◆ DiscreteLogWorkFactor()

unsigned int 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 1027 of file nbtheory.cpp.

## ◆ FactoringWorkFactor()

unsigned int 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 1019 of file nbtheory.cpp.