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
xwhich is fully reduced (floor(x / modulus) = 0). - We build an array of
powerswhich are produced by multiplying the previous power byx, so for each powerfloor(power / modulus) <= 1. - Then we take turns squaring the accumulator
z(bringingfloor(z / modulus)to 1 regardless of the previous reduction level) and multiplying by a power ofx(bringingfloor(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).