Skip to main content

almost_montgomery_reduce

Function almost_montgomery_reduce 

Source
pub(crate) fn almost_montgomery_reduce(z: &mut UintRef, modulus: &UintRef)
Expand description

Ensure the output of an “almost” Montgomery multiplication is properly reduced.

Using the properties of almost_montgomery_mul() (see its documentation):

  • We have an incoming x which is fully reduced (floor(x / modulus) = 0).
  • We build an array of powers which are produced by multiplying the previous power by x, so for each power floor(power / modulus) <= 1.
  • Then we take turns squaring the accumulator z (bringing floor(z / modulus) to 1 regardless of the previous reduction level) and multiplying by a power of x (bringing floor(z / modulus) to at most 2).
  • Then we either exit the loop, or square again, which brings floor(z / modulus) back to 1.

We now need to reduce z at most twice to bring it within [0, modulus).