Mod operation
Niels Möller
nisse at lysator.liu.se
Fri Nov 27 10:24:05 CET 2009
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
More information about the gmp-devel
mailing list