Better b^e mod m

[Niels Möller]

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.