Better b^e mod m

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> 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.

Looks nice, but in the case that the mul_1 is done, the result will
still be either a limb too large (if bdiv_r reduces it by n limbs)
or a factor of B off (if it reduces n+1 limbs). Since we get 2n+1 limbs
after the sqr + mul_1, and we want to reduce it to n. Do you agree?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.