Mod operation

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> I'd expect that one could also cook up an algorithm which combines the
> same x0 * m3 recuction with a 2^k-1 reduction for the second step.
> I.e., an algorithm which takes x of size 4n and computes x / (B-1) mod
> m of size 2n.

I'm continuing to speak aloud here. Assume that gcd(m, B-1) = 1 (this
is not totally unreasonable, e.g., for the powm that is part of rsa
operations, B-1 is smaller than the smallest factor of m, and hence
there can be no common factor. And this is clearly an important
application).

Anyway, as before inputs are x0 + x1B + x2 B^2 + x3 B^3 which is to be
reduced mod m0 + B m1.

Precompute m3 = m mod B^3, and m' = -m^{-1} mod (B-1). Step one is the
same, compute

  y = y0 + y1B + y2 B = x0 + x1 B + x2 B + x3 * m3

Step two, compute

  q = y * m' mod (B-1)

Step three, compute
  
  (y + q*m) / (B-1)

where the division is exact and O(n). The total cost (ignoring O(n)
operations) is then two 2nxn and one multiply mod B-1. This looks
pretty good to me.

If g = gcd(m, B-1) > 1, I'm not sure if the algorithm can be saved in
some way by taking out the common factor. If g is small, one could
maybe replace B-1 by (B-1) / g. E.g., exact division is still fairly
cheap as a multiply by g followed by exact division by B-1. In the
general case, I don't know; maybe it would be enlightning to consider
the extreme case that B-1 is a factor of m.

Regards,
/Niels