Crate libbgs_util

Various number theory utility methods used throughout the libbgs crate.

Functions

• carrying_add
  Returns the sum of a and b as two 128-bit words. The first element of the tuple is the high word (guaranteed to be either 0 or 1) and the second is the low word.
• carrying_mul
  Returns the product of a and b, as two 128-bit words. The first element of the tuple is the high word, and the second is the low word.
• find_nonresidue
  Returns a quadratic non-residue modulo p. That is, it returns an integer $a \in \mathbb{Z} / p\mathbb{Z}$ such that there is no $x$ satisfying $x^2 = a \mod p$.
• intpow
  Returns x to the power of n, modulo m.
• long_multiply
  Returns the product of a and b modulo m. This function will panic if m >= 2^127. Otherwise, it is guarenteed that there will not be integer overflow.
• shrd
  Shifts dst to the right n bits, filling in from the left with the least significant bits of src.
• standard_affine_shift
  Returns a pseudo-random integer modulo q, unique for every i between 0 and q. This acts suitably well as a random number generator for several modular arithmetic operations, including randomly searching for quadratic (non) residues.