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

CRYPTOPP_DLL const word16 * | GetPrimeTable (unsigned int &size)
| The Small Prime table.
CRYPTOPP_DLL Integer | MaurerProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
| Generates a provable prime.
CRYPTOPP_DLL Integer | MihailescuProvablePrime (RandomNumberGenerator &rng, unsigned int bits)
| Generates a provable prime.
CRYPTOPP_DLL bool | IsSmallPrime (const Integer &p)
| Tests whether a number is a small prime.
CRYPTOPP_DLL bool | TrialDivision (const Integer &p, unsigned bound)
| Tests whether a number is divisible by a small prime.
CRYPTOPP_DLL bool | SmallDivisorsTest (const Integer &p)
| Tests whether a number is divisible by a small prime.
CRYPTOPP_DLL bool | IsFermatProbablePrime (const Integer &n, const Integer &b)
| Determine if a number is probably prime.
CRYPTOPP_DLL bool | IsLucasProbablePrime (const Integer &n)
| Determine if a number is probably prime.
CRYPTOPP_DLL bool | IsStrongProbablePrime (const Integer &n, const Integer &b)
| Determine if a number is probably prime.
CRYPTOPP_DLL bool | IsStrongLucasProbablePrime (const Integer &n)
| Determine if a number is probably prime.
CRYPTOPP_DLL bool | RabinMillerTest (RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
| Determine if a number is probably prime.
CRYPTOPP_DLL bool | IsPrime (const Integer &p)
| Verifies a number is probably prime.
CRYPTOPP_DLL bool | VerifyPrime (RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
| Verifies a number is probably prime.
CRYPTOPP_DLL bool | FirstPrime (Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
| Finds a random prime of special form.
CRYPTOPP_DLL unsigned int | PrimeSearchInterval (const Integer &max)
CRYPTOPP_DLL AlgorithmParameters | MakeParametersForTwoPrimesOfEqualSize (unsigned int productBitLength)
Integer | GCD (const Integer &a, const Integer &b)
| Calculate the greatest common divisor.
bool | RelativelyPrime (const Integer &a, const Integer &b)
| Determine relative primality.
Integer | LCM (const Integer &a, const Integer &b)
| Calculate the least common multiple.
Integer | EuclideanMultiplicativeInverse (const Integer &a, const Integer &b)
| Calculate multiplicative inverse.
CRYPTOPP_DLL Integer | CRT (const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
| Chinese Remainder Theorem.
CRYPTOPP_DLL int | Jacobi (const Integer &a, const Integer &b)
| Calculate the Jacobi symbol.
CRYPTOPP_DLL Integer | Lucas (const Integer &e, const Integer &p, const Integer &n)
| Calculate the Lucas value.
CRYPTOPP_DLL Integer | InverseLucas (const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
| Calculate the inverse Lucas value.
Integer | ModularMultiplication (const Integer &x, const Integer &y, const Integer &m)
| Modular multiplication.
Integer | ModularExponentiation (const Integer &x, const Integer &e, const Integer &m)
| Modular exponentiation.
CRYPTOPP_DLL Integer | ModularSquareRoot (const Integer &a, const Integer &p)
| Extract a modular square root.
CRYPTOPP_DLL Integer | ModularRoot (const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
| Extract a modular root.
CRYPTOPP_DLL bool | SolveModularQuadraticEquation (Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
| Solve a Modular Quadratic Equation.
CRYPTOPP_DLL unsigned int | DiscreteLogWorkFactor (unsigned int bitlength)
| Estimate work factor.
CRYPTOPP_DLL unsigned int | FactoringWorkFactor (unsigned int bitlength)
| Estimate work factor.

## Detailed Description

Classes and functions for number theoretic operations.

Definition in file nbtheory.h.

## Function Documentation

## GetPrimeTable()

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

The Small Prime table.

Parameters

  size | number of elements in the table

Returns
  prime table with /p size elements

GetPrimeTable() obtains pointer to small prime table and provides the size of the table. /p size is an out parameter.

## MaurerProvablePrime()

CRYPTOPP_DLL 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

## MihailescuProvablePrime()

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

## IsSmallPrime()

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

## TrialDivision()

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

## SmallDivisorsTest()

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

## IsFermatProbablePrime()

CRYPTOPP_DLL 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

## IsLucasProbablePrime()

CRYPTOPP_DLL 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

## IsStrongProbablePrime()

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

## IsStrongLucasProbablePrime()

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

## RabinMillerTest()

CRYPTOPP_DLL 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

## IsPrime()

CRYPTOPP_DLL 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().

## VerifyPrime()

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

## FirstPrime()

CRYPTOPP_DLL 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}`

## 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 146 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 153 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 160 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 169 of file nbtheory.h.

## CRT()

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

## Jacobi()

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

Calculate the Jacobi symbol.

Parameters

  a | the first term
  b | the second term

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

## Lucas()

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

## InverseLucas()

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

## 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 211 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 219 of file nbtheory.h.

## ModularSquareRoot()

CRYPTOPP_DLL 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

## ModularRoot()

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

## SolveModularQuadraticEquation()

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

## DiscreteLogWorkFactor()

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

## FactoringWorkFactor()

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