Better b^e mod m
Niels Möller
nisse at lysator.liu.se
Thu Oct 18 21:08:04 CEST 2012
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.
More information about the gmp-devel
mailing list