Better b^e mod m
Niels Möller
nisse at lysator.liu.se
Tue Oct 16 15:49:29 CEST 2012
Torbjorn Granlund <tg at gmplib.org> writes:
> nisse at lysator.liu.se (Niels Möller) writes:
>
> (I've also been considering if we could also use single-limb hensel
> reduction, doing b multiplies as
>
> (x' b) B^{-1}
>
> Then we get a factor of B error (which is going to be amplified while
> squaring).
>
> I am afraid I don't follow you. Specifically, what does B^{-1} denote?
> Do you compute this inverse modulo something, do you intend to form
> either (x' b)/B or floor((x' b)/B)?
Everything mod m, division by B (mod m) is one iteration redc_1. So here
I'm suggesting that multiplying the accumulator x by the single-limb
base b is done as
tp[n] = mpn_mul_1 (tp, xp, n, b);
q = -tp[0] * minv; /* Inverse of m mod B */
tp[n] += mpn_addmul_1 (tp, mp, n, q); /* FIXME: Handle any carry */
MPN_COPY (xp, tp + 1, n);
This actually computes x <-- x * (b / B) (mod m). So we need to deal
with the gratuitous factor of B somewhere else.
Not sure if this is useful, but in the cases where the extra power of B
can be handled for free, I'd expect it to be slightly faster than using
Euclidean reduction.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list