Small-base modexp (was: Re: mpz_nextprime)

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> Moreover one may avoid the windowing on the exponent (we currently
> pre-compute b^3, b^5, b^7... so that we need fewer products) and use a
> shift by a single bit every time a multiplication times the base is
> needed.

And in the bit more general small-base case, that shift would be an
mpn_mul_1. And I think the difference in speed between shift and mul_1
is negligible, since in either case, almost all the cycles will be spent
on the modular squarings.

It's not clear to me either how this interacts with montgomery
representation, but I hope that's not too hard to sort out. The thing is
to avoid converting the base in montgomery representation, because if we
do, it's no longer small.

Regards,
/Niels

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