# Better b^e mod m

Torbjorn Granlund tg at gmplib.org
Thu Oct 18 20:40:36 CEST 2012

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

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.

Should be, yes.

Another alternative might be to simply not reduce after the squaring:

loop
mpn_sqr (...)
if (next-exp_bit-set)
mpn_mul_1 (...)
mpn_bdiv_r (...)

The intermediate result should be in redc form, the base argument should
be in plain form.

--
Torbjörn
```