Better b^e mod m

Niels Möller nisse at
Thu Oct 18 21:08:04 CEST 2012

Torbjorn Granlund <tg at> 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?


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