Module ring::arithmetic::bigint

Multi-precision integers.

Modular Arithmetic.

Modular arithmetic is done in finite commutative rings ℤ/mℤ for some modulus m. We work in finite commutative rings instead of finite fields because the RSA public modulus n is not prime, which means ℤ/nℤ contains nonzero elements that have no multiplicative inverse, so ℤ/nℤ is not a finite field.

In some calculations we need to deal with multiple rings at once. For example, RSA private key operations operate in the rings ℤ/nℤ, ℤ/pℤ, and ℤ/qℤ. Types and functions dealing with such rings are all parameterized over a type M to ensure that we don’t wrongly mix up the math, e.g. by multiplying an element of ℤ/pℤ by an element of ℤ/qℤ modulo q. This follows the “unit” pattern described in Static checking of units in Servo.

Elem also uses the static unit checking pattern to statically track the Montgomery factors that need to be canceled out in each value using it’s E parameter.

Modules

• boxed_limbs 🔒
• modulus 🔒
• private_exponent 🔒

Structs

• Elem
  Elements of ℤ/mℤ for some modulus m.
• One

Traits

• PublicModulus

Functions

• elem_add
• elem_double 🔒
• elem_exp_consttime
• elem_exp_vartime 🔒
  Calculates base**exponent (mod m).
• elem_mul
• elem_reduced
• elem_reduced_once
• elem_squared 🔒
• elem_sub
• elem_verify_equal_consttime
• elem_widen
• from_montgomery_amm 🔒
  Does a Montgomery reduction on limbs assuming they are Montgomery-encoded (‘R’) and assuming they are the same size as m, but perhaps not reduced mod m. The result will be fully reduced mod m.
• verify_inverses_consttime
  Verified a == b**-1 (mod m), i.e. a**-1 == b (mod m).